Low-Rank Matrix Recovery With Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number

Tian Tong, Cong Ma, Yuejie Chi

TL;DR

This paper introduces "scaled subgradient methods" for efficiently recovering low-rank matrices from incomplete and potentially corrupted data. These new methods achieve faster and more robust convergence than existing approaches, crucially without being hindered by the matrix's condition number, a common bottleneck.

What Problem Does This Paper Address?

Many real-world problems, from image processing to signal analysis, involve reconstructing a large matrix that is known to have a low intrinsic rank. This is often done by observing only a small subset of the matrix's entries, and these observations can also be corrupted by noise or outliers. A common approach is to formulate this as an optimization problem: find the low-rank matrix that best explains the observed data.

A popular method involves factorizing the unknown matrix into two smaller matrices and optimizing these factors. However, standard optimization techniques like gradient descent applied to smooth loss functions (e.g., minimizing squared errors) suffer from two major issues:

  1. Ill-conditioning: The convergence speed slows down significantly with the matrix's dimension and its "condition number" (a measure of how "stretched" the data is).
  2. Lack of robustness: These methods are sensitive to outliers or corrupted data points.

While some methods have addressed one of these issues, none have simultaneously tackled both while guaranteeing fast convergence. This paper aims to fill that gap by developing methods that are fast, robust to corruptions, and independent of the condition number.

Methods

The core contribution is a novel optimization algorithm called Scaled Subgradient Method (ScaledSM). It tackles a nonsmooth and nonconvex formulation of the low-rank matrix recovery problem, specifically minimizing the residual sum of absolute errors. This choice of loss function is inherently more robust to outliers than the sum of squared errors.

The ScaledSM algorithm updates the low-rank matrix factors (L and R, where the matrix X is approximated as LR) using a scaled subgradient. The key innovation lies in how it scales the update direction: it pre-multiplies the subgradient by the inverse of (RᵀR) and (LᵀL) for the respective updates. This "scaling" or "preconditioning" step is inspired by similar techniques for smooth optimization problems but is adapted here for the nonsmooth setting.

The paper also analyzes two stepsize schedules for the algorithm:

  • Polyak's stepsize: Applicable when the noise-free target value of the loss function is known.
  • Geometrically decaying stepsize: A more general approach suitable for noisy and corrupted data.

The theoretical analysis leverages geometric properties of the loss function, such as restricted Lipschitz continuity and restricted sharpness, which are shown to hold under certain conditions on the observation operator (specifically, mixed-norm Restricted Isometry Property - RIP).

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated according to standard models for:

  • Matrix Sensing: Where observations are linear measurements of the target matrix.
  • Quadratic Sampling: Where observations are quadratic functions of the target matrix.

These synthetic datasets are designed to test the algorithms under various conditions, including different condition numbers, levels of noise, and fractions of outliers.

Key Insights and Ideas

  • Nonsmoothness for Robustness: Using the sum of absolute errors (L1 loss) as the objective function is a key enabler for robustness against outliers, as it penalizes large errors less severely than squared errors.
  • Scaling for Speed: The "scaling" or "preconditioning" of the subgradient directions is crucial for achieving fast convergence, particularly by mitigating the ill-conditioning associated with the matrix's condition number.
  • Dimension-Free and Condition-Number-Free Convergence: The theoretical analysis demonstrates that ScaledSM achieves convergence rates that are independent of the matrix dimension and its condition number, a significant improvement over many existing methods.
  • Unified Framework: The proposed method and its analysis provide a unified way to handle both noise-free and noisy/corrupted scenarios, as well as different types of observation operators (matrix sensing, quadratic sampling) under a common theoretical framework.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees for ScaledSM, showing linear convergence rates. These rates are almost dimension-free and independent of the condition number of the true low-rank matrix.
  • State-of-the-Art Performance: For robust low-rank matrix sensing and quadratic sampling, the paper derives state-of-the-art computational guarantees.
  • Empirical Validation: Numerical experiments (Figures 1-6) demonstrate that ScaledSM significantly outperforms the vanilla subgradient method (VanillaSM) in terms of convergence speed, especially when the condition number is high or when outliers are present. ScaledSM shows insensitivity to the condition number, while VanillaSM's performance degrades substantially. The method also shows robustness to noise.

Limitations and Future Work

  • Initialization: The theoretical guarantees often assume a "good" initialization. While standard spectral methods can be used for initialization in noise-free cases, the presence of outliers might require more sophisticated techniques (e.g., truncated spectral methods), which can be cumbersome to tune.
  • Parameter Tuning: While the paper provides theoretical parameters for the geometrically decaying stepsize, practical performance might still benefit from careful tuning. The paper notes that Polyak's stepsize, when applicable and tuned, often yields the fastest convergence in experiments.
  • Future Work: The authors suggest exploring the performance of scaled subgradient methods for other signal estimation and statistical inference tasks, such as training student-teacher neural networks and using random initializations.

Summary updated

BibTeX
@article{tong2021low,
  author = {Tian Tong and Cong Ma and Yuejie Chi},
  title = {{Low-Rank Matrix Recovery With Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=gighxJQycoz},
}
Figure