2018/06/07 by Ganzhao Yuan, Wei‐Shi Zheng, Yuan, Ganzhao +5
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Mathematics #Image and Signal Denoising Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1806.03165
openalex publication_date 2018/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Composite function minimization captures a wide spectrum of applications in both computer vision and machine learning. It includes bound constrained optimization, ℓ1 norm regularized optimization, and ℓ0 norm regularized optimization as special cases. This paper proposes and analyzes a new Generalized Matrix Splitting Algorithm (GMSA) for minimizing composite functions. It can be viewed as a generalization of the classical Gauss-Seidel method and the Successive Over-Relaxation method for solving linear systems in the literature. Our algorithm is derived from a novel triangle operator mapping, which can be computed exactly using a new generalized Gaussian elimination procedure. We establish the global convergence, convergence rate, and iteration complexity of GMSA for convex problems. In addition, we also discuss several important extensions of GMSA. Finally, we validate the performance of our proposed method on three particular applications: nonnegative matrix factorization, ℓ0 norm regularized sparse coding, and ℓ1 norm regularized Dantzig selector problem. Extensive experiments show that our method achieves state-of-the-art performance in term of both efficiency and efficacy.