  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 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 $d \asymp \log n$ for matrix completion found in
the literature.
