2012 OptimalExactLeastSquaresRankMin

• (Xiang et al., 2012) ⇒ Shuo Xiang, Yunzhang Zhu, Xiaotong Shen, and Jieping Ye. (2012). “Optimal Exact Least Squares Rank Minimization.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339609

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Optimal+Exact+Least+Squares+Rank+Minimization
• http://dl.acm.org/citation.cfm?id=2339530.2339609&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; global optimality; nonconvex; 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 OptimalExactLeastSquaresRankMin	Jieping Ye Shuo Xiang Yunzhang Zhu Xiaotong Shen			Optimal Exact Least Squares Rank Minimization				10.1145/2339530.2339609		2012