Can I read Detection Thresholds in Very Sparse Matrix Completion on EtoBox?

Detection Thresholds in Very Sparse Matrix Completion by Bordenave, Charles; Coste, Simon; Nadakuditi, Raj Rao is a scholarly article available to read on EtoBox.

What is Detection Thresholds in Very Sparse Matrix Completion about?

Let $A$ be a rectangular matrix of size $m\times n$ 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)^*$ and $(A-A_1)^*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^*$ and $A^* 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 impro

Author

Bordenave, Charles; Coste, Simon; Nadakuditi, Raj Rao

Published

2020

Language

EN