Phase transitions in semidefinite relaxations

DOI10.1073/pnas.1523097113zbMath1359.62188arXiv1511.08769OpenAlexW2174754147WikidataQ36831458 ScholiaQ36831458MaRDI QIDQ2962328

Federico Ricci-Tersenghi, Adel Javanmard, Andrea Montanari

Publication date: 16 February 2017

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08769

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Related Items

Optimal Bipartite Network Clustering, Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions, Estimation of low-rank matrices via approximate message passing, An information-percolation bound for spin synchronization on general graphs, Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks, Optimal rates of estimation for multi-reference alignment, Universal completability, least eigenvalue frameworks, and vector colorings, Rate optimal Chernoff bound and application to community detection in the stochastic block models, The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables, A unified approach to synchronization problems over subgroups of the orthogonal group, Unnamed Item, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, Entrywise eigenvector analysis of random matrices with low expected rank, Local laws for multiplication of random matrices, Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization, Notes on computational-to-statistical gaps: predictions using statistical physics, TAP free energy, spin glasses and variational inference, Optimal couplings between sparse block models, Typical performance of approximation algorithms for NP-hard problems, Near-Optimal Bounds for Phase Synchronization, Unnamed Item, On semidefinite relaxations for the block model, Community Detection and Stochastic Block Models, Convex relaxation methods for community detection, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Optimality and sub-optimality of PCA. I: Spiked random matrix models, The random fractional matching problem, Nonconvex Phase Synchronization, Group synchronization on grids, Partial recovery bounds for clustering with the relaxed \(K\)-means, Unnamed Item, Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs, Precise statistical analysis of classification accuracies for adversarial training, Edge of spiked beta ensembles, stochastic Airy semigroups and reflected Brownian motions, Graph Powering and Spectral Robustness

Cites Work

• Belief propagation, robust reconstruction and optimal recovery of block models
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• A survey of max-type recursive distributional equations
• Angular synchronization by eigenvectors and semidefinite programming
• Community detection in sparse networks via Grothendieck's inequality
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Heuristics for semirandom graph problems
• Bayesian model selection and model averaging
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Phase recovery, MaxCut and complex semidefinite programming
• Phase Retrieval with Polarization
• Grothendieck-Type Inequalities in Combinatorial Optimization
• Spectral redemption in clustering sparse networks
• Three-Dimensional Structure Determination from Common Lines in Cryo-EM by Eigenvectors and Semidefinite Programming
• Information, Physics, and Computation
• Atomic Decomposition by Basis Pursuit
• Semidefinite relaxation and nonconvex quadratic optimization
• Community structure in social and biological networks
• Asymptotic mutual information for the balanced binary stochastic block model
• Community detection thresholds and the weak Ramanujan property
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Semidefinite programs on sparse random graphs and their application to community detection
• How robust are reconstruction thresholds for community detection?
• Neighborliness of randomly projected simplices in high dimensions
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Phase Retrieval via Matrix Completion
• Unnamed Item
• Unnamed Item