A Denoising View of Matrix Completion

Weiran Wang, Miguel Á. Carreira-Perpiñán, Zhengdong LuNeurIPS 2011 · OpenReview

TL;DR

This paper reimagines matrix completion not as a search for a low-rank linear subspace, but as an iterative denoising process. By using non-parametric mean-shift algorithms to nudge missing entries toward a latent curved manifold, the authors consistently improve reconstructions of complex data—like motion capture and images—that standard low-rank methods struggle to capture.

What Problem Does This Paper Address?

Matrix completion is the art of filling in the blanks. Given a table where most entries are missing (think of the famous Netflix prize where users only rate a few movies), how do we guess the rest?

The standard "go-to" assumption is that the data matrix is low-rank, meaning all data points live on a flat, linear subspace. While powerful, this is often too rigid. Real-world data, such as the joint positions in a human running sequence, often live on curved manifolds. If you force a curved shape into a flat box, you lose the "richness" of the data. The authors tackle this by moving beyond the linear assumption, proposing a framework that can handle non-linear, curved structures.

Methods

The authors propose a framework based on Manifold Blurring Mean-Shift (MBMS). Here is the high-level recipe:

  1. Initialize: Start with a rough guess of the missing values using a standard method like Singular Value Projection (SVP).
  2. Denoise: Treat the current matrix as a "noisy" version of the truth. Use a mean-shift algorithm where each data point moves toward the average of its neighbors.
  3. GBMS (Gaussian Blurring Mean-Shift): A general version that averages points in all directions.
  4. MBMS: A more sophisticated version that uses local PCA to find a "tangent space." It only denoises perpendicular to the manifold, preventing the data from shrinking or collapsing inward.
Pseudocode for the Local Tangent Projection step used in the denoising process.
  1. Refill: After the denoising step, the "known" entries will have moved slightly. The algorithm forcibly resets them to their original, true values.
  2. Iterate: Repeat until a validation error (calculated on a small "held-out" set of known entries) starts to increase.

The "magic" here is that the "noise" being removed isn't just sensor error—it's the inaccuracy of the current completion itself.

Key Insights and Ideas

  • Noise as Inaccuracy: The most profound "aha" moment is viewing the error in missing entries as a form of noise that can be filtered out by looking at neighboring data points.
  • Beyond Flatness: By using local averaging instead of global matrix factorization, the model naturally adapts to the local geometry of the data. If the manifold is curved, the algorithm follows the curve.
  • The "Refilling" Constraint: The authors show that their algorithmic "denoise-then-refill" approach can actually be derived from a formal constrained optimization problem. This bridges the gap between intuitive "data cleaning" and rigorous math.
  • Stopping is Key: Unlike many optimization problems that want to reach a global minimum, denoising must be stopped early. If you denoise forever, all points collapse into a single dot. Using cross-validation to find the "sweet spot" of denoising is a practical, effective strategy.
Error curves over iterations for different initializations and denoising methods. Notice how the error drops initially but rises if denoising continues too long, highlighting the need for early stopping.

Datasets and Key Results

The authors evaluated their approach on three distinct types of data, showing that the denoising approach consistently acted as a "booster" for existing methods:

  • 100D Swissroll: A synthetic 3D "spiral" dataset lifted into 100 dimensions with added noise. MBMS reduced the Root Sum of Squared Errors (RSSE) from 156.8 (standard low-rank) to 151.8. Visually, it successfully "unmixed" points that had strayed between the layers of the spiral.
  • CMU Motion Capture (Mocap): Data from a human running. In scenarios where 90% of the data was missing, the denoising methods significantly outperformed standard Gaussian and low-rank models, which often failed to produce a recognizable human skeleton.
  • MNIST Digit '7': On a digit completion task with simulated occlusions, MBMS achieved an RSSE of 6.03, outperforming both non-linear PCA (7.77) and standard low-rank completion (6.99). It was particularly good at removing the "ghosting" artifacts left behind by other methods.

Limitations and Future Work

While powerful, the method has a few hurdles:

  • Parameter Sensitivity: The user must choose the number of neighbors ($k$), the denoising scale ($\sigma$), and the local dimensionality ($L$). While the authors use cross-validation to find these, it adds computational overhead.
  • Computational Cost: For very large datasets, calculating neighbors for every point can be expensive ($O(N^2D)$ for a full graph), though the authors mitigate this using $k$-nearest neighbor graphs.
  • Initialization Dependence: The algorithm is a post-processing step. If the initial completion is extremely far off, the denoising might not be able to "find" the manifold.

The authors suggest that future work could explore using temporal neighborhoods (for video) or applying these ideas to discrete data by treating denoising as a form of "majority voting" among neighbors.

Summary updated

Abstract

In matrix completion, we are given a matrix where the values of only some of the entries are present, and we want to reconstruct the missing ones. Much work has focused on the assumption that the data matrix has low rank. We propose a more general assumption based on denoising, so that we expect that the value of a missing entry can be predicted from the values of neighboring points. We propose a nonparametric version of denoising based on local, iterated averaging with mean-shift, possibly constrained to preserve local low-rank manifold structure. The few user parameters required (the denoising scale, number of neighbors and local dimensionality) and the number of iterations can be estimated by cross-validating the reconstruction error. Using our algorithms as a postprocessing step on an initial reconstruction (provided by e.g. a low-rank method), we show consistent improvements with synthetic, image and motion-capture data.
BibTeX
@inproceedings{wang2011denoising,
  author = {Weiran Wang and Miguel Á. Carreira-Perpiñán and Zhengdong Lu},
  title = {{A Denoising View of Matrix Completion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2011},
  url = {https://openreview.net/forum?id=BJbiIuZuWS},
}
Figure