Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization
This work provides a more efficient solver for matrix recovery problems in machine learning and data analysis, but it is incremental as it extends an existing method to handle more complex formulations.
The authors tackled the problem of solving joint low-rank and sparse matrix minimization problems, which are essential for many tasks, by generalizing the Iteratively Reweighted Least Squares (IRLS) method to handle multiple non-smooth terms, and demonstrated through experiments that their approach is much more efficient than previous methods.
This work presents a general framework for solving the low rank and/or sparse matrix minimization problems, which may involve multiple non-smooth terms. The Iteratively Reweighted Least Squares (IRLS) method is a fast solver, which smooths the objective function and minimizes it by alternately updating the variables and their weights. However, the traditional IRLS can only solve a sparse only or low rank only minimization problem with squared loss or an affine constraint. This work generalizes IRLS to solve joint/mixed low rank and sparse minimization problems, which are essential formulations for many tasks. As a concrete example, we solve the Schatten-$p$ norm and $\ell_{2,q}$-norm regularized Low-Rank Representation (LRR) problem by IRLS, and theoretically prove that the derived solution is a stationary point (globally optimal if $p,q\geq1$). Our convergence proof of IRLS is more general than previous one which depends on the special properties of the Schatten-$p$ norm and $\ell_{2,q}$-norm. Extensive experiments on both synthetic and real data sets demonstrate that our IRLS is much more efficient.