Abstract: In this paper, we present a nonconvex alternating minimization optimization algorithm for low-rank and sparse structure pursuit. Compared with convex relaxation based methods, the proposed algorithm is computationally more efficient for large scale problems. In our study, we define a notion of bounded difference of gradients, based on which we rigorously prove that with suitable initialization, the proposed nonconvex optimization algorithm enjoys linear convergence to the global optima and exactly recovers the underlying low rank and sparse matrices under standard conditions such as incoherence and sparsity conditions. For a wide range of statistical models such as multi-task learning and robust principal component analysis (RPCA), our algorithm provides a principled approach to learning the low rank and sparse structures with provable guarantee. Thorough experiments on both synthetic and real datasets backup our theory.
Problem Context
Modern machine learning frequently encounters data matrices that are "low-rank" (living in a low-dimensional subspace) but corrupted by "sparse" noise or outliers. This structure is central to two major applications:
- Robust Principal Component Analysis (RPCA): Separating a static background (low-rank) from moving foreground objects (sparse) in video surveillance.
- Multi-task Learning: Sharing core information across different tasks while accounting for task-specific variations.
Traditionally, these problems are solved via convex relaxation using nuclear and $\ell_1$ norms. However, these methods are computationally prohibitive for large-scale data because they require a full Singular Value Decomposition (SVD) at every iteration. This research bridges the gap between the speed of nonconvex heuristics and the rigorous guarantees of convex optimization.
The Proposed Approach
The authors introduce a nonconvex Alternating Minimization algorithm designed for efficiency. The method relies on several key innovations:
- Matrix Factorization: Instead of optimizing a full $d_1 \times d_2$ matrix $L$, the algorithm reparameterizes it as $L = UV^\top$. By working with smaller factor matrices $U$ and $V$, the algorithm bypasses expensive full-matrix SVDs.
- Truncation for Sparsity: To isolate the sparse component $S$, the algorithm employs a hard thresholding step, retaining only the top $s$ largest elements in each iteration.
- Alternating Updates: The variables $U$, $V$, and $S$ are updated iteratively while keeping others fixed, ensuring a steady descent toward the solution.
Theoretical Foundations
The core contribution is the introduction of the "bounded difference of gradients" framework. This allows the authors to prove that, despite the nonconvex landscape, the algorithm will converge exponentially fast (linear convergence) to the global optimum. This guarantee holds under standard conditions like incoherence (ensuring the matrix isn't overly "spiky") and the Restricted Isometry Property (RIP), provided there is a suitable initialization.
Empirical Performance
The algorithm was tested on synthetic data (up to $d=5000$) and a real-world surveillance dataset ("Hall of a business building").
- Computational Speed: In video background subtraction, the proposed algorithm completed the task in just 22 seconds. For comparison, the standard convex ADMM approach took 18 minutes, and a competing nonconvex method took 1 minute.
- Convergence and Accuracy: Experiments confirmed the theoretical prediction of linear convergence. As shown in the performance plots, the error drops exponentially with the number of iterations across various problem scales.
Conclusion
By moving from full matrix space to factorized space, the per-iteration complexity is reduced from $O(d_1 d_2 \cdot \min(d_1, d_2))$ to $O(r d_1 d_2)$, where $r$ is the rank. This work demonstrates that nonconvex alternating minimization is not just a fast heuristic but a principled, mathematically sound approach for large-scale structure pursuit, offering significant speedups without sacrificing the precision of global recovery.
Summary updated