Detection thresholds in very sparse matrix completion

DOI10.1007/s10208-022-09568-6zbMath1523.60017arXiv2005.06062MaRDI QIDQ6072328

Raj Rao Nadakuditi, Simon Coste, Charles Bordenave

Publication date: 13 October 2023

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

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

zbMATH Keywords

eigenvaluesmatrix completionnon-Hermitian matricesspectral algorithmssparse random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Algebraic statistics (62R01)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Belief propagation, robust reconstruction and optimal recovery of block models
• Around the circular law
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Norms and exclusion theorems
• Games of fixed rank: a hierarchy of bimatrix games
• Separable and low-rank continuous games
• The eigenvalues of random symmetric matrices
• The ubiquitous Kronecker product
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Extremal eigenvalues of critical Erdős-Rényi graphs
• The spectral gap of sparse random digraphs
• Spectral radii of sparse random matrices
• The circular law for sparse non-Hermitian matrices
• Matrix estimation by universal singular value thresholding
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Exact matrix completion via convex optimization
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Non-backtracking spectra of weighted inhomogeneous random graphs
• A literature survey of low-rank tensor approximation techniques
• Spectral redemption in clustering sparse networks
• OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Fast computation of low-rank matrix approximations
• The Largest Eigenvalue of Sparse Random Graphs
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The non-backtracking spectrum of the universal cover of a graph
• A useful variant of the Davis–Kahan theorem for statisticians
• Community detection thresholds and the weak Ramanujan property
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Spectral techniques applied to sparse random graphs
• Spectral theory of sparse non-Hermitian random matrices
• Spectral gap in random bipartite biregular graphs and applications

This page was built for publication: Detection thresholds in very sparse matrix completion