Optimal exact least squares rank minimization

Shuo Xiang, Yunzhang Zhu, Xiaotong T Shen, Jieping Ye

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationKDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Pages480-488
Number of pages9
DOIs
StatePublished - Sep 14 2012
Event18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012 - Beijing, China
Duration: Aug 12 2012Aug 16 2012

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012
CountryChina
CityBeijing
Period8/12/128/16/12

    Fingerprint

Keywords

  • global optimality
  • nonconvex
  • rank minimization

Cite this

Xiang, S., Zhu, Y., Shen, X. T., & Ye, J. (2012). Optimal exact least squares rank minimization. In KDD'12 - 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 480-488). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). https://doi.org/10.1145/2339530.2339609