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

Jian-Feng Cai (Department of Mathematics, University of Iowa, Iowa City, Ia., U.S.A.)

Stanley Osher (Department of Mathematics, University of California at Los Angeles)

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