Random Laplacian matrices and convex relaxations

DOI10.1007/s10208-016-9341-9zbMath1386.15065arXiv1504.03987OpenAlexW2963919656MaRDI QIDQ1750385

Afonso S. Bandeira

Publication date: 18 May 2018

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingrandom matrixLaplacian matrixconvex relaxation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (29)

Optimal Bipartite Network Clustering ⋮ Community detection with a subsampled semidefinite program ⋮ The Ratio-Cut Polytope and K-Means Clustering ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates ⋮ A unified approach to synchronization problems over subgroups of the orthogonal group ⋮ Unnamed Item ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ A strict complementarity approach to error bound and sensitivity of solution of conic programs ⋮ A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization ⋮ Spectrum of Lévy-Khintchine random Laplacian matrices ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Comparative analysis on Landsat image enhancement using fractional and integral differential operators ⋮ Near-Optimal Bounds for Phase Synchronization ⋮ On semidefinite relaxations for the block model ⋮ On the Simplicity and Conditioning of Low Rank Semidefinite Programs ⋮ Community Detection and Stochastic Block Models ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ Nonlinear network dynamics with consensus-dissensus bifurcation ⋮ Convex relaxation methods for community detection ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Spectral clustering revisited: information hidden in the Fiedler vector ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ Non-unique games over compact groups and orientation estimation in cryo-EM ⋮ Non-convex exact community recovery in stochastic block model ⋮ Robust group synchronization via cycle-edge message passing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consistency thresholds for the planted bisection model
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Belief propagation, robust reconstruction and optimal recovery of block models
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• Angular synchronization by eigenvectors and semidefinite programming
• User-friendly tail bounds for sums of random matrices
• Correlation clustering
• On the distribution of the roots of certain symmetric matrices
• The ellipsoid method and its consequences in combinatorial optimization
• Heuristics for semirandom graph problems
• A proof of the block model threshold conjecture
• Moment inequalities for functions of independent random variables
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Spectral measure of large random Hankel, Markov and Toeplitz matrices
• Information Recovery From Pairwise Measurements
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Exact Recovery in the Stochastic Block Model
• On the power of unique 2-prover 1-round games
• An Introduction to Random Matrices
• P-Complete Approximation Problems
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Synchronization overZ₂and community detection in signed multiplex networks with constraints
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Semidefinite Programming
• Community detection thresholds and the weak Ramanujan property
• A Cheeger Inequality for the Graph Connection Laplacian
• An Introduction to Matrix Concentration Inequalities

This page was built for publication: Random Laplacian matrices and convex relaxations