The Generalized Matrix Separation Problem: Algorithms
This work provides practical algorithmic implementations for a known convex formulation, offering incremental improvements for matrix separation problems.
The paper presents efficient iterative algorithms for solving a convex optimization problem that recovers low-rank and sparse matrices from linear measurements, with a preconditioning technique that improves efficiency, accuracy, and robustness.
When given a generalized matrix separation problem, which aims to recover a low rank matrix $L_0$ and a sparse matrix $S_0$ from $M_0=L_0+HS_0$, the work \cite{CW25} proposes a novel convex optimization problem whose objective function is the sum of the $\ell_1$-norm and nuclear norm. In this paper we detail the iterative algorithms and its associated computations for solving this convex optimization problem. We present various efficient implementation strategies, with attention to practical cases where $H$ is circulant, separable, or block structured. Notably, we propose a preconditioning technique that drastically improved the performance of our algorithms in terms of efficiency, accuracy, and robustness. While this paper serves as an illustrative algorithm implementation manual, we also provide theoretical guarantee for our preconditioning strategy. Numerical results demonstrate the effectiveness of the proposed approach.