图 书 馆
基于凸优化的矩阵完成：理论与算法Matrix Completion via Convex Optimization: Theory and Algorithms |
|
| 课程网址: | http://videolectures.net/mlss09us_candes_mccota/ |
| 主讲教师: | Emmanuel Candes |
| 开课单位: | 斯坦福大学 |
| 开课时间: | 2009-07-30 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | This talk considers a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. In partially filled out surveys, for instance, we would like to infer the many missing entries. In the area of recommender systems, users submit ratings on a subset of entries in a database, and the vendor provides recommendations based on the user's preferences. Because users only rate a few items, we would like to infer their preference for unrated items (this is the famous Netflix problem). Formally, suppose that we observe m entries selected uniformly at random from a matrix. Can we complete the matrix and recover the entries that we have not seen? We show that perhaps surprisingly, one can recover low-rank matrices exactly from what appear to be highly incomplete sets of sampled entries; that is, from a minimally sampled set of entries. Further, perfect recovery is possible by solving a simple convex optimization program, namely, a convenient semidefinite program. A surprise is that our methods are optimal and succeed as soon as recovery is possible by any method whatsoever, no matter how intractable; this result hinges on powerful techniques in probability theory. Time permitting, we will also present a very efficient algorithm based on iterative singular value thresholding, which can complete matrices with about a billion entries in a matter of minutes on a personal computer. |
| 关 键 词: | 凸优化程序; 矩阵; 概率论 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-06-29：wuyq |
| 阅读次数: | 42 |