Nonconvex Approach for Sparse and Low-Rank Constrained Models with Dual Momentum

Cho-Ying Wu, Jian-Jiun DingarXiv 2019 · arXiv

Abstract

Low-rank and sparse matrix models are fundamental to modern data science, underpinning applications from video background subtraction to facial recognition. While convex surrogates like the nuclear norm are widely used due to their computational ease, they often introduce significant bias by penalizing all singular values equally. This paper introduces a more sophisticated approach: a multilevel piecewise nonconvex surrogate for the rank function combined with a "dual momentum" optimization technique for the Alternating Direction Method of Multipliers (ADMM). This framework enables more accurate recovery of low-rank structures while maintaining the fast, linear convergence rates typically associated with simpler convex methods.

Introduction: The Challenge of Rank Minimization

Extracting low-rank structures from noisy or corrupted data is a core task in Robust Principal Component Analysis (RPCA) and Low-Rank Representation (LRR). Mathematically, the ideal objective is to minimize the rank of a matrix. However, rank minimization is an NP-hard problem. To circumvent this, researchers traditionally employ the nuclear norm as a convex surrogate.

While effective, the nuclear norm is a "blunt instrument" because it applies a uniform penalty to all singular values. In practice, large singular values represent the essential structure of the data and should be preserved, whereas small singular values typically represent noise and should be aggressively suppressed. Nonconvex surrogates, such as the Minimax Concave Penalty (MCP) or Smoothly Clipped Absolute Deviation (SCAD), attempt to address this by varying the penalty based on the magnitude of the singular value. However, these methods often create complex mathematical landscapes that are difficult to optimize, frequently leading to sub-optimal local minima.

A Finer-Grained Piecewise Regularizer

The authors propose a novel nonconvex surrogate characterized by a four-segment piecewise linear supergradient. This "multilevel" structure provides a more nuanced approach to penalizing singular values compared to existing methods.

The proposed piecewise regularizer's supergradient, showing the four distinct segments ($l_1$ to $l_4$) and thresholds ($p_1$ to $p_3$) for fine-grained singular value control.

As shown in Figure 1, the supergradient allows the model to treat singular values differently across four distinct regions. This design essentially implements a strategy of "ignoring the giants" (preserving the largest singular values), "gently nudging" middle-sized values, and "aggressively pruning" the smallest ones. This level of control is significantly more delicate than the single-slope or flat-line penalties found in standard nonconvex models.

To solve the resulting nonconvex optimization problem, the authors enhance the standard ADMM algorithm with a "dual momentum" mechanism. Inspired by the momentum techniques used in Stochastic Gradient Descent (SGD) for training neural networks, dual momentum adds a weighted difference of the Lagrange multipliers (dual variables) from previous iterations to the current update.

This addition provides the algorithm with "inertia," helping it navigate past local minima and accelerating convergence in regions where updates might otherwise become sluggish. Crucially, the authors provide a rigorous mathematical proof that their algorithm maintains a linear convergence rate despite the added complexity of the nonconvex penalty and the momentum term.

Comparison with State-of-the-Art Surrogates

To appreciate the novelty of the proposed piecewise regularizer, it is helpful to compare it with existing nonconvex surrogates. Table 1 outlines several common penalties used in the literature.

Comparison of common nonconvex regularizers, their functions $\lambda g(\sigma_i)$, and their corresponding supergradients $\lambda \partial g(\sigma_i)$.

While methods like SCAD and MCP offer improvements over the nuclear norm, they typically rely on simpler, two- or three-segment structures. The proposed four-segment approach allows for a more tailored response to the distribution of singular values found in real-world datasets.

Experimental Results and Performance

The researchers evaluated their approach across several standard benchmarks, including synthetic data, the AR Face Database, and the Extended Yale Database B. The results consistently demonstrated the superiority of the dual momentum nonconvex approach:

  • Image Completion: The proposed regularizer achieved a relative error of 1.03E-13, outperforming SCAD (1.50E-13) while also reducing computational time.
  • Face Denoising: On the AR Database, the method achieved an average Peak Signal-to-Noise Ratio (PSNR) of 37.30 dB, a significant improvement over the 33.56 dB achieved by standard convex RPCA.
  • Spectral Clustering: In tasks involving outliers and corrupted data, the proposed method reached 91.72% accuracy, surpassing both standard LRR (89.02%) and other advanced variants.

Conclusion

By combining a nuanced piecewise regularizer with a dual momentum optimization strategy, the authors have developed a powerful tool for low-rank and sparse recovery. This approach bridges the gap between the theoretical advantages of nonconvex models and the practical efficiency of convex ones. Future work may involve refining the heuristic methods for setting the regularizer's thresholds and exploring the application of dual momentum ADMM to broader machine learning challenges, such as regularizing deep neural networks.

Summary updated

Abstract

In this manuscript, we research on the behaviors of surrogates for the rank function on different image processing problems and their optimization algorithms. We first propose a novel nonconvex rank surrogate on the general rank minimization problem and apply this to the corrupted image completion problem. Then, we propose that nonconvex rank surrogates can be introduced into two well-known sparse and low-rank models: Robust Principal Component Analysis (RPCA) and Low-Rank Representation (LRR). For optimization, we use alternating direction method of multipliers (ADMM) and propose a trick, which is called the dual momentum. We add the difference of the dual variable between the current and the last iteration with a weight. This trick can avoid the local minimum problem and make the algorithm converge to a solution with smaller recovery error in the nonconvex optimization problem. Also, it can boost the convergence when the variable updates too slowly. We also give a severe proof and verify that the proposed algorithms are convergent. Then, several experiments are conducted, including image completion, denoising, and spectral clustering with outlier detection. These experiments show that the proposed methods are effective in image and signal processing applications, and have the best performance compared with state-of-the-art methods.
BibTeX
@misc{wu2019nonconvex,
  author = {Cho-Ying Wu and Jian-Jiun Ding},
  title = {{Nonconvex Approach for Sparse and Low-Rank Constrained Models with Dual Momentum}},
  year = {2019},
  eprint = {1906.02433},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.02433},
}
Figure