Van Vu

We show that exact recovery in the noisy Matrix Completion problem can be achieved under the basic assumptions without the need for a small condition number or large singular value gaps, using novel techniques that can be of independent interest.

We derive sharp spectral-norm bounds for noisy low-rank approximation, improving prior results by up to $\sqrt{n}$. Applied to DP-PCA, our method resolves an open problem and matches empirical error via a novel contour bootstrapping technique.