Fast Guaranteed Robust Local-Smooth Principal Component Separation

Leveraging intrinsic data priors is critical for effective data recovery. However, existing approaches often struggle to simultaneously achieve theoretical guarantees, strong performance, and computational efficiency. In this paper, we introduce a novel \emph{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 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 (RCCTV-RPCA), 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 RCCTV-RPCA achieves state-of-the-art accuracy with significantly reduced runtime.