title: Optimal Exact Least Squares Rank Minimization.
abstract: In multivariate analysis, rank minimization emerges when a low-rank structure of matrices is desired as well as a small estimation error. Rank minimization is nonconvex and generally NP-hard, imposing one major challenge. In this paper, we consider a nonconvex least squares formulation, which seeks to minimize the least squares loss function with the rank constraint. Computationally, we develop efficient algorithms to compute a global solution as well as an entire regularization solution path. Theoretically, we show that our method reconstructs the oracle estimator exactly from noisy data. As a result, it recovers the true rank optimally against any method and leads to sharper parameter estimation over its counterpart. Finally, the utility of the proposed method is demonstrated by simulations and image reconstruction from noisy background.
authors.affiliation: Department of Computer Science and Engineering, Arizona State University, AZ 85287 ; Center for Evolutionary Medicine and Informatics, The Biodesign Institute, Arizona State University, AZ 85287.
authors.forename: Shuo
authors.initials: S
authors.lastname: Xiang
authors.affiliation: School of Statistics, University of Minnesota, Minneapolis, MN 55455.
authors.forename: Yunzhang
authors.initials: Y
authors.lastname: Zhu
authors.affiliation: School of Statistics, University of Minnesota, Minneapolis, MN 55455.
authors.forename: Xiaotong
authors.initials: X
authors.lastname: Shen
authors.affiliation: Department of Computer Science and Engineering, Arizona State University, AZ 85287 ; Center for Evolutionary Medicine and Informatics, The Biodesign Institute, Arizona State University, AZ 85287.
authors.forename: Jieping
authors.initials: J
authors.lastname: Ye
keywords: Algorithms; Nonconvex; global optimality; rank minimization