The generalized matrix separation problem: algorithms

Abstract When given a generalized matrix separation problem, which aims to recover a low rank matrix $$L_0$$ L 0 and a sparse matrix $$S_0$$ S 0 from $$M_0=L_0+HS_0$$ M 0 = L 0 + H S 0 , the work [1] proposes a novel convex optimization problem whose objective function is the sum of the $$\ell _1$$ ℓ 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 preprocessing 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 preprocessing strategy. Numerical results demonstrate the effectiveness of the proposed approach.