Fast Guaranteed Robust Local-Smooth Principal Component Separation

Abstract

Leveraging intrinsic data priors is critical for effective data recovery. However, existing approaches often struggle to achieve theoretical guarantees, strong performance, and computational efficiency simultaneously. In this paper, we introduce a novel Representative Coefficient Correlated Total Variation (RCCTV) regularizer that captures the recently observed low-rank and local smoothness properties of the representative coefficient tensor derived from a low-rank decomposition. RCCTV regularizer offers three key advantages: (1) it operates on a compact representative coefficient image significantly smaller than the original data, enabling highly efficient optimization; (2) it jointly enforces low-rankness and spatial smoothness through a single regularizer, eliminating the need for trade-off parameters; and (3) when integrated into a robust PCA framework (i.e., RCCTV-RPCA model), it admits provable exact recovery under mild conditions. To solve the resulting model, we develop an efficient ADMM-based algorithm accelerated via fast Fourier transform. Extensive experiments on both synthetic and real-world datasets demonstrate that the RCCTV-RPCA model achieves state-of-the-art accuracy while running significantly faster. Our code and Supplementary Material are available at https://github.com/mendy-2013/RCCTV.