Generalized Unitarily Invariant Gauge Regularization for Fast Low-Rank Matrix Recovery

Spectral regularization is a widely used approach for low-rank matrix recovery (LRMR) by regularizing matrix singular values. Most of the existing LRMR solvers iteratively compute the singular values via applying singular value decomposition (SVD) on a dense matrix, which is computationally expensive and severely limits their applications to large-scale problems. To address this issue, we present a generalized unitarily invariant gauge (GUIG) function for LRMR. The proposed GUIG function does not act on the singular values; however, we show that it generalizes the well-known spectral functions, including the rank function, the Schatten- p quasi-norm, and logsum of singular values. The proposed GUIG regularization model can be formulated as a bilinear variational problem, which can be efficiently solved without computing SVD. Such a property makes it well suited for large-scale LRMR problems. We apply the proposed GUIG model to matrix completion and robust principal component analysis and prove the convergence of the algorithms. Experimental results demonstrate that the proposed GUIG method is not only more accurate but also much faster than the state-of-the-art algorithms, especially on large-scale problems.