Abstract
We introduce a new convex formulation for stable principal component pursuit (SPCP) to decompose noisy signals into low-rank and sparse representations. For numerical solutions of our SPCP formulation, we first develop a convex variational framework and then accelerate it with quasi-Newton methods. We show, via synthetic and real data experiments, that our approach offers advantages over the classical SPCP formulations in scalability and practical parameter selection.
Introduction: The Challenge of Noisy Data Decomposition
Robust Principal Component Analysis (RPCA) is a fundamental tool in data science, used to decompose a matrix into a low-rank "background" and a sparse "foreground." However, real-world signals are rarely clean; they typically contain additive noise. This necessitates Stable Principal Component Pursuit (SPCP).
The traditional $SPCP_{sum}$ formulation requires balancing the nuclear norm (for rank) and the $L_1$ norm (for sparsity) against a noise constraint $\epsilon$. Tuning these parameters is notoriously difficult because they are deeply coupled. Moreover, as data dimensions increase, standard solvers become computationally prohibitive due to the need for repeated, expensive Singular Value Decompositions (SVDs).
Methodology: The Max-SPCP Formulation and Variational Framework
To address these challenges, we propose a new "max-SPCP" formulation. Instead of minimizing the sum of penalties, we minimize their maximum: $$\text{minimize } \max(\|L\|_*, \lambda_{max}\|S\|_1) \text{ subject to } \|L+S-Y\|_F \le \epsilon$$
This approach decouples the parameters, making $\lambda_{max}$ easier to estimate based on the expected ratio between low-rank and sparse components.
Variational Optimization and Quasi-Newton Acceleration
We solve this constrained problem using a variational "root-finding" framework. We transform the original problem into a sequence of "flipped" problems that minimize noise subject to a total penalty budget $\tau$. We then use Newton’s method to iteratively update $\tau$ until the noise level matches $\epsilon$.
To accelerate the sub-problems, we developed a specialized quasi-Newton method. By using a Gauss-Seidel-like approximation of the Hessian, we can take larger steps and achieve faster convergence than standard first-order methods.
Experimental Evaluation
We benchmarked our approach against state-of-the-art solvers using both synthetic and real-world datasets.
Synthetic Benchmarks
On large-scale $1500 \times 1500$ synthetic matrices, our quasi-Newton solvers demonstrated superior speed and accuracy.
As shown in the figure above, the proposed methods (labeled "this paper*") reach low error levels in a fraction of the time required by competing methods like ASALM or PSPG.
Real-World Application: MODIS Cloud Removal
We applied the algorithm to a dataset of 15 MODIS satellite images ($300 \times 300$ pixels). The goal was to separate the static landscape (low-rank) from transient clouds and sensor artifacts (sparse).
The algorithm successfully performed this decomposition in just 5 seconds on a standard laptop, highlighting its practical utility for high-resolution remote sensing tasks.
Discussion and Conclusion
Our "max-SPCP" formulation simplifies parameter tuning by providing more "orthogonal" control over the low-rank and sparse components. Combined with a variational framework and quasi-Newton acceleration, it offers a highly scalable solution for noisy matrix decomposition.
While the "max" variant is exceptionally fast, the "sum" variant in our current implementation still relies on dense SVDs, which is a target for future optimization. Additionally, extending this high-speed acceleration to more complex linear operators remains an active area of research.
Summary updated