图 书 馆
基于奇异值投影的保秩最小化Guaranteed Rank Minimization via Singular Value Projection |
|
| 课程网址: | http://videolectures.net/nips2010_jain_grm/ |
| 主讲教师: | Prateek Jain |
| 开课单位: | Nuance通讯公司 |
| 开课时间: | 2011-03-25 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Minimizing the rank of a matrix subject to affine constraints is a fundamental problem with many important applications in machine learning and statistics. In this paper we propose a simple and fast algorithm SVP (Singular Value Projection) for rank minimization under affine constraints ARMP and show that SVP recovers the minimum rank solution for affine constraints that satisfy a Restricted Isometry Property} (RIP). Our method guarantees geometric convergence rate even in the presence of noise and requires strictly weaker assumptions on the RIP constants than the existing methods. We also introduce a Newton-step for our SVP framework to speed-up the convergence with substantial empirical gains. Next, we address a practically important application of ARMP - the problem of low-rank matrix completion, for which the defining affine constraints do not directly obey RIP, hence the guarantees of SVP do not hold. However, we provide partial progress towards a proof of exact recovery for our algorithm by showing a more restricted isometry property and observe empirically that our algorithm recovers low-rank Incoherent matrices from an almost optimal number of uniformly sampled entries. We also demonstrate empirically that our algorithms outperform existing methods, such as those of \cite{CaiCS2008,LeeB2009b, KeshavanOM2009}, for ARMP and the matrix completion problem by an order of magnitude and are also more robust to noise and sampling schemes. In particular, results show that our SVP-Newton method is significantly robust to noise and performs impressively on a more realistic power-law sampling scheme for the matrix completion problem. |
| 关 键 词: | 机器学习; 受仿射约束; 奇异值投影 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-07-25：cwx |
| 阅读次数: | 127 |