Contents Online
Methods and Applications of Analysis
Volume 20 (2013)
Number 4
Special issue dedicated to the 70th birthday of Stanley Osher: Part I
Guest Editor: Chi-Wang Shu, Brown University
Fast singular value thresholding without singular value decomposition
Pages: 335 – 352
DOI: https://dx.doi.org/10.4310/MAA.2013.v20.n4.a2
Authors
Abstract
Singular value thresholding (SVT) is a basic subroutine in many popular numerical schemes for solving nuclear norm minimization that arises from low-rank matrix recovery problems such as matrix completion. The conventional approach for SVT is first to find the singular value decomposition (SVD) and then to shrink the singular values. However, such an approach is time-consuming under some circumstances, especially when the rank of the resulting matrix is not significantly low compared to its dimension. In this paper, we propose a fast algorithm for directly computing SVT for general dense matrices without using SVDs. Our algorithm is based on matrix Newton iteration for matrix functions, and the convergence is theoretically guaranteed. Numerical experiments show that our proposed algorithm is more efficient than the SVD-based approaches for general dense matrices.
Keywords
low rank matrix, nuclear norm minimization, matrix Newton iteration
2010 Mathematics Subject Classification
65F30, 65Kxx
Published 16 April 2014