BriefGPT.xyz
Mar, 2017
关于贪心低秩优化的近似保证
On Approximation Guarantees for Greedy Low Rank Optimization
HTML
PDF
Rajiv Khanna, Ethan Elenberg, Alexandros G. Dimakis, Sahand Negahban
TL;DR
本文提供了一种新的矩阵估算近似保证方法，其基于约束强凸性和平滑性的标准假设。同时，本文揭示了低秩估算和组合优化之间的新联系，并针对两个重要的现实问题提供了贪心估计与基准估计间的经验比较。
Abstract
We provide new approximation guarantees for greedy
low rank
matrix estimation
under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connecti
→