• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Understanding Alternating Minimization for Matrix Completion
【24h】

Understanding Alternating Minimization for Matrix Completion

机译：了解矩阵完成的交替最小化

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Alternating minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for alternating minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on alternating minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the alternating minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of alternating minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here.
机译：交替最小化是矩阵完成和相关的低秩优化问题广泛使用的且凭经验获得成功的启发式方法。交替最小化的理论保证一直很难获得，并且仍然知之甚少。这部分是因为启发式方法本质上是迭代的并且是非凸的。我们给出了一种基于交替最小化的新算法，该算法可在标准不相干假设下从其条目的随机子样本中可恢复地恢复未知的低秩矩阵。我们的结果通过未知矩阵的秩和条件数的至少四次因子减少了交替最小化方法的样本大小要求。即使矩阵在Frobenius范数中仅接近低秩，也可以应用这些改进。我们的算法在矩阵维度上以几乎线性的时间运行，并在广泛的参数范围内提供了我们所知道的所有次二次时间算法中最强的样本边界。我们的工作基础是对著名的幂方法的新的鲁棒收敛分析，该幂方法用于计算矩阵的显性奇异向量。这种观点导致了概念上对交替最小化的简单理解。此外，我们基于QR分解的平滑分析，为控制迭代算法中出现的中间解决方案的一致性提供了一种新技术。这些技术可能超出了此处的应用范围。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号