A Numerical Study of Low-Rank Matrix Completion under Noise and Non-Uniform Sampling

Abstract

We explore low-rank matrix completion as a controlled model problem in this thesis to understand the results of conventional recovery algorithms outside the ideal environment of noise-free and uniformly sampled data. The reviewed methods include accelerated Vandenberghe proximal gradient, its structured variant Soft-Impute, classic singular value thresholding (Uzawa-SVT), and a randomized-SVD variant of Uzawa-SVT. All these techniques achieve comparable reconstruction quality in the noise-free uniform setting. However, when noise is present and sampling follows a highly non-uniform pattern, their recovery becomes much less reliable. Specifically, methods that enforce exact agreement with the observed data through hard constraints are less effective with noisy data, and non-uniform sampling concentrates observations in certain regions while undersampling others. To develop insight into these effects, we present diagnostic analysis demonstrating that exact interpolation of noisy observations creates a noise floor and that non-uniform sampling alters the expected least squares loss by weighting errors according to the probability of sampling. Based on this analysis, a residual-reweighting approach has been evaluated. The differences observed were small, suggesting that residual weighting provides a mild correction rather than a solution, and that more problem-specific priors may be needed for more difficult inverse problems.