Random Laplacian matrices and convex relaxations
From MaRDI portal
Publication:1750385
DOI10.1007/s10208-016-9341-9zbMath1386.15065arXiv1504.03987OpenAlexW2963919656MaRDI QIDQ1750385
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
Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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 overZ2and 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
