Randomized Low-Memory Singular Value Projection

Abstract

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.

13 pages. This version has a revised theorem and new numerical experiments

Cited by in corpus (6)

• Dropping Convexity for Faster Semi-definite Optimization
• Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
• Fast Low-Rank Matrix Estimation without the Condition Number
• Alternating Strategies Are Good For Low-Rank Matrix Reconstruction
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction