Randomized Low-Memory Singular Value Projection Journal Article uri icon



  • 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.

publication date

  • March 1, 2013

Date in CU Experts

  • October 15, 2014 2:04 AM

Full Author List

  • Becker S; Cevher V; Kyrillidis A

author count

  • 3