The Generalized Matrix Separation Problem: Algorithms

2025/07/22 by Chen, Xuemei, Deen, Owen
#FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2507.17069

Abstract

When given a generalized matrix separation problem, which aims to recover a low rank matrix L₀ and a sparse matrix S₀ from M₀=L₀+HS₀, the work \citeCW25 proposes a novel convex optimization problem whose objective function is the sum of the ℓ₁-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.

Citations

• The Masked Matrix Separation Problem: A First Analysis
• Non-convex Robust PCA
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Robust Principal Component Analysis?
• Robust principal component analysis?
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• A Singular Value Thresholding Algorithm for Matrix Completion
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

Related

• The Masked Matrix Separation Problem: A First Analysis
• A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
• A Singular Value Thresholding Algorithm for Matrix Completion
• A Generalized Matrix Splitting Algorithm
• The Power of Convex Relaxation: Near-Optimal Matrix Completion