  Composite function minimization captures a wide spectrum of applications in
both computer vision and machine learning. It includes bound constrained
optimization and cardinality regularized optimization as special cases. This
paper proposes and analyzes a new Matrix Splitting Method (MSM) 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. Incorporating a new Gaussian elimination
procedure, the matrix splitting method achieves state-of-the-art performance.
For convex problems, we establish the global convergence, convergence rate, and
iteration complexity of MSM, while for non-convex problems, we prove its global
convergence. Finally, we validate the performance of our matrix splitting
method on two particular applications: nonnegative matrix factorization and
cardinality regularized sparse coding. Extensive experiments show that our
method outperforms existing composite function minimization techniques in term
of both efficiency and efficacy.
