图 书 馆
无条件数的快速矩阵完备Fast Matrix Completion Without the Condition Number |
|
| 课程网址: | http://videolectures.net/colt2014_wootters_matrix/ |
| 主讲教师: | Mary Wootters |
| 开课单位: | 万国商业机器公司 |
| 开课时间: | 2014-07-15 |
| 课程语种: | 英语 |
| 中文简介: |  我们给出了矩阵完成的第一个算法，该算法实现了运行时间和样本复杂度，该算法在未知目标矩阵的秩上是多项式，在矩阵的维数上是线性的，在矩阵的条件数上是对数的。据我们所知，所有先前的算法要么依赖于未知矩阵的条件数成二次依赖关系，要么依赖于矩阵的维数成二次依赖关系。我们的算法基于交替最小化的新扩展，我们证明即使在存在噪声的情况下，在标准假设下也具有理论上的保证。 |
| 课程简介: | We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise. |
| 关 键 词: | 矩阵算法; 交替最小化 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2020-12-30：zyk |
| 最后编审: | 2020-12-30：zyk |
| 阅读次数: | 46 |