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 (35)

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

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Phase transitions in semidefinite relaxations