Randomized Low-Memory Singular Value Projection | CU Experts

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.

VIVO