Robust Principal Component Analysis via ℓ0 Alternating Minimization
Abstract
Robust principal component analysis concerns the recovery of a low-rank matrix Z and a sparse matrix S from their observed sum D = Z + S. In this paper, we study this recovery problem under an ℓ0 sparsity penalty and a rank constraint on the low-rank component. By exploiting the entrywise separable structure of the sparse subproblem, we obtain an exact closed-form solution via hard thresholding with box clipping, avoiding the shrinkage bias of ℓ1-based methods. The low-rank subproblem is solved by truncated SVD. We prove block-coordinate convergence of the resulting alternating minimization scheme, establish uniqueness of block minimizers under non-degeneracy and singular value gap conditions, establish local linear convergence under a contraction condition on the Fréchet derivative of the truncated SVD operator restricted to the sparse support, and provide a second-order optimality analysis via the Riemannian Hessian. Experiments on synthetic data, images, and video show that the proposed algorithm outperforms the existing convex and nonconvex algorithms, most notably in support recovery and in the accuracy-efficiency trade-off.
Related
- Robust Multi-Task Learning for Principal Component Analysis
- From proximal alternating minimization techniques to composite proximal gradient
- An Alternating Minimization Algorithm for Federated Sparse Orthogonal Nonnegative Matrix Factorization
- Principal component analysis for a mix of stationary and nonstationary variables
- Principal component analysis in Φ α-linear spaces
BibTeX
@misc{lyu2026robust,
title = {{Robust Principal Component Analysis via $\ell_0$ Alternating Minimization}},
author = {Ze-Kun Lyu and Xin Liu and Qian-Yu Shu and Lei Wang and Wei Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41492},
eprint = {2610.41492},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41492},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Robust Principal Component Analysis via ℓ_0 Alternating Minimization
AU - Ze-Kun Lyu
AU - Xin Liu
AU - Qian-Yu Shu
AU - Lei Wang
AU - Wei Zhang
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41492
UR - https://arxiv.org/abs/2610.41492
AB - Robust principal component analysis concerns the recovery of a low-rank matrix Z and a sparse matrix S from their observed sum D = Z + S. In this paper, we study this recovery problem under an ℓ_0 sparsity penalty and a rank constraint on the low-rank component. By exploiting the entrywise separable structure of the sparse subproblem, we obtain an exact closed-form solution via hard thresholding with box clipping, avoiding the shrinkage bias of ℓ_1-based methods. The low-rank subproblem is solved by truncated SVD. We prove block-coordinate convergence of the resulting alternating minimization scheme, establish uniqueness of block minimizers under non-degeneracy and singular value gap conditions, establish local linear convergence under a contraction condition on the Fréchet derivative of the truncated SVD operator restricted to the sparse support, and provide a second-order optimality analysis via the Riemannian Hessian. Experiments on synthetic data, images, and video show that the proposed algorithm outperforms the existing convex and nonconvex algorithms, most notably in support recovery and in the accuracy-efficiency trade-off.
ER -