Randomized Low-Memory Singular Value Projection
Randomized Low-Memory Singular Value Projection
复制标题
随机低内存奇异值投影
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Anastasios Kyrillidis
中科院分区：
文献类型：
--
作者：
Stephen Becker;V. Cevher;Anastasios Kyrillidis
仿射秩最小化算法通常依赖于计算数据误差的梯度，然后在每次迭代时进行奇异值分解。由于这两个步骤代价高昂，因此经常使用启发式近似来减少计算负担。为此，我们提出了一种恢复方案，将这两个步骤与随机近似相结合，结果是在与问题中的自由度成比例的空间上操作。我们从理论上证明了算法的估计保证是逼近容差的函数。虽然理论上的近似要求过于悲观，但我们证明了该算法在实际的量子层析成像恢复问题上表现良好。
Affine rank minimization algorithms typically rely on calculating the gradient of a data error followed by a singular value decomposition at every iteration. Because these two steps are expensive, heuristic approximations are often used to reduce computational burden. To this end, we propose a recovery scheme that merges the two steps with randomized approximations, and as a result, operates on space proportional to the degrees of freedom in the problem. We theoretically establish the estimation guarantees of the algorithm as a function of approximation tolerance. While the theoretical approximation requirements are overly pessimistic, we demonstrate that in practice the algorithm performs well on the quantum tomography recovery problem.