Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms.

Adrien Todeschini, François Caron, Marie ChaventNeurIPS 2013 · OpenReview

Abstract

We propose a novel class of algorithms for low rank matrix completion. Our approach builds on novel penalty functions on the singular values of the low rank matrix. By exploiting a mixture model representation of this penalty, we show that a suitably chosen set of latent variables enables to derive an Expectation-Maximization algorithm to obtain a Maximum A Posteriori estimate of the completed low rank matrix. The resulting algorithm is an iterative soft-thresholded algorithm which iteratively adapts the shrinkage coefficients associated to the singular values. The algorithm is simple to implement and can scale to large matrices. We provide numerical comparisons between our approach and recent alternatives showing the interest of the proposed approach for low rank matrix completion.

Introduction

Matrix completion—the task of filling in missing entries in a partially observed matrix—is a fundamental problem in machine learning, most famously encountered in recommender systems like the "Netflix Problem." To make this problem tractable, researchers typically assume the underlying matrix is low-rank. While the rank penalty is the ideal regularizer for this task, it is NP-hard to optimize. Most current methods rely on the nuclear norm as a convex proxy. However, the nuclear norm introduces a systematic bias by applying uniform shrinkage to all singular values, which can degrade prediction quality and lead to incorrect rank estimation.

Hierarchical Adaptive Spectral Penalty (HASP)

This paper introduces the Hierarchical Adaptive Spectral Penalty (HASP), a Bayesian framework that bridges the gap between the computationally efficient nuclear norm and the accurate rank penalty.

The core innovation lies in treating singular values as coming from a mixture of exponential distributions. Specifically, by assuming that the regularization parameters for each singular value follow a Gamma distribution, the authors derive a marginal Pareto distribution for the singular values. Unlike the exponential distribution (which corresponds to the nuclear norm), the Pareto distribution has heavier tails, meaning it penalizes large singular values much less than small ones.

Geometric visualization of the penalty functions, showing how HASP interpolates between the nuclear norm and the rank penalty.

As illustrated in Figure 3, HASP acts as a tunable bridge. By adjusting the hyperparameter $\beta$, the model can transition from the convex nuclear norm (a) to a non-convex shape that closely approximates the hard rank penalty (d). This allows for "adaptive shrinkage," where the model preserves the signal in large singular values while aggressively suppressing noise in smaller ones.

The HASI Algorithm

To solve the resulting non-convex optimization problem, the authors derive the Hierarchical Adaptive Soft Impute (HASI) algorithm using an Expectation-Maximization (EM) approach.

  • E-Step: The algorithm calculates weights for each singular value based on their current estimates.
  • M-Step: It performs a weighted soft-thresholding Singular Value Decomposition (SVD).

This iterative process is self-correcting: as the algorithm identifies a significant singular value, it reduces the penalty on that value in subsequent iterations, effectively "de-biasing" the reconstruction.

Experimental Evaluation

The authors evaluated HASI against several state-of-the-art methods, including Soft-Impute, Hard-Impute, and Maximum Margin Matrix Factorization (MMMF), using synthetic data and real-world datasets like Jester and MovieLens.

Comparison of test error across different ranks for HASI and competing methods.

Key Results

  • Superior Accuracy: HASI consistently achieved lower error rates (e.g., Normalized Mean Absolute Error) than its competitors on collaborative filtering benchmarks.
  • Improved Rank Recovery: Standard methods like Soft-Impute often overestimate the rank to compensate for shrinkage bias. As shown in Figure 5, HASI identifies the optimal low-rank representation more accurately, achieving its lowest test error at significantly lower ranks than competing methods.
  • Robustness to Noise: In high-noise simulations, HASI maintained stable performance while other methods' error rates or rank estimates became unstable.

Conclusion

The HASP framework and HASI algorithm offer a powerful alternative to standard matrix completion techniques. By adaptively regularizing singular values, the method reduces estimation bias and improves rank recovery without sacrificing the simplicity of iterative thresholding. Future work will explore extensions to binary data and fully Bayesian treatments for uncertainty quantification.

Summary updated

Abstract

We propose a novel class of algorithms for low rank matrix completion. Our approach builds on novel penalty functions on the singular values of the low rank matrix. By exploiting a mixture model representation of this penalty, we show that a suitably chosen set of latent variables enables to derive an Expectation-Maximization algorithm to obtain a Maximum A Posteriori estimate of the completed low rank matrix. The resulting algorithm is an iterative soft-thresholded algorithm which iteratively adapts the shrinkage coefficients associated to the singular values. The algorithm is simple to implement and can scale to large matrices. We provide numerical comparisons between our approach and recent alternatives showing the interest of the proposed approach for low rank matrix completion.
BibTeX
@inproceedings{todeschini2013probabilistic,
  author = {Adrien Todeschini and François Caron and Marie Chavent},
  title = {{Probabilistic Low-Rank Matrix Completion with Adaptive Spectral Regularization Algorithms.}},
  booktitle = {NeurIPS},
  year = {2013},
  url = {https://openreview.net/forum?id=S2zqcI0qyo},
}
Figure