Detection thresholds in very sparse matrix completion

DOI10.1007/S10208-022-09568-6MaRDI QIDQ6072328zbMATH OpenFDO

Authors Charles Bordenave, Simon Coste, Raj Rao Nadakuditi

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 matricessparse random graphsspectral algorithms

Mathematics Subject Classification ID

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

Abstract: Let $A$ be a rectangular matrix of size $mimesn$ and $A_1$ be the random matrix where each entry of $A$ is multiplied by an independent $0,1$-Bernoulli random variable with parameter $1/2$. This paper is about when, how and why the non-Hermitian eigen-spectra of the randomly induced asymmetric matrices $A_1(A-A_1{)}^{\ast }$ and $(A-A_1{)}^{\ast }{A}_1$ captures more of the relevant information about the principal component structure of $A$ than via its SVD or the eigen-spectra of $A{A}^{\ast }$ and $A^{\ast }A$, respectively. Hint: the asymmetry inducing randomness breaks the echo-chamber effect that cripples the SVD. We illustrate the application of this striking phenomenon on the low-rank matrix completion problem for the setting where each entry is observed with probability $d/n$, including the very sparse regime where $d$ is of order $1$, where matrix completion via the SVD of $A$ fails or produces unreliable recovery. We determine an asymptotically exact, matrix-dependent, non-universal detection threshold above which reliable, statistically optimal matrix recovery using a new, universal data-driven matrix-completion algorithm is possible. Averaging the left and right eigenvectors provably improves the recovered matrix but not the detection threshold. We define another variant of this asymmetric procedure that bypasses the randomization step and has a detection threshold that is smaller by a constant factor but with a computational cost that is larger by a polynomial factor of the number of observed entries. Both detection thresholds shatter the seeming barrier due to the well-known information theoretical limit $dasymplogn$ for matrix completion found in the literature.

Recommendations

• A simpler approach to matrix completion
• Exact matrix completion via convex optimization
• Asymptotic theory for estimating the singular vectors and values of a partially-observed low rank matrix with noise
• Matrix completion by singular value thresholding: sharp bounds
• Robust matrix completion

Cites work

• A literature survey of low-rank tensor approximation techniques
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• A useful variant of the Davis-Kahan theorem for statisticians
• Around the circular law
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Belief propagation, robust reconstruction and optimal recovery of block models
• Community detection thresholds and the weak Ramanujan property
• Concentration inequalities. A nonasymptotic theory of independence
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Exact matrix completion via convex optimization
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Fast computation of low-rank matrix approximations
• scientific article; zbMATH DE number 6474942 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 741107 (Why is no real title available?)
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Matrix Completion From a Few Entries
• Matrix estimation by universal singular value thresholding
• Non-backtracking spectra of weighted inhomogeneous random graphs
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Norms and exclusion theorems
• OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Separable and low-rank continuous games
• Spectral gap in random bipartite biregular graphs and applications
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Spectral radii of sparse random matrices
• Spectral redemption in clustering sparse networks
• Spectral techniques applied to sparse random graphs
• Spectral theory of sparse non-Hermitian random matrices
• The circular law for sparse non-Hermitian matrices
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The eigenvalues of random symmetric matrices
• The Largest Eigenvalue of Sparse Random Graphs
• The non-backtracking spectrum of the universal cover of a graph
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The spectral gap of sparse random digraphs
• The ubiquitous Kronecker product
• Unperturbed: spectral analysis beyond Davis-Kahan

Cited in

(8)

• Fundamental limits of symmetric low-rank matrix estimation
• Detection boundary in sparse regression
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Sparse random hypergraphs: non-backtracking spectra and community detection
• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Davis-Kahan theorem under a moderate gap condition

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072328)