Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint

Abstract

The rank minimization problem is to find the lowest-rank matrix in a given set. Nuclear norm minimization has been proposed as an convex relaxation of rank minimization. Recht, Fazel, and Parrilo have shown that nuclear norm minimization subject to an affine constraint is equivalent to rank minimization under a certain condition given in terms of the rank-restricted isometry property. However, in the presence of measurement noise, or with only approximately low rank generative model, the appropriate constraint set is an ellipsoid rather than an affine space. There exist polynomial-time algorithms to solve the nuclear norm minimization with an ellipsoidal constraint, but no performance guarantee has been shown for these algorithms. In this paper, we derive such an explicit performance guarantee, bounding the error in the approximate solution provided by nuclear norm minimization with an ellipsoidal constraint.

References in corpus (2)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Singular Value Thresholding Algorithm for Matrix Completion

Cited by in corpus (10)

• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Provable Inductive Matrix Completion
• Guaranteed Rank Minimization via Singular Value Projection
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• Low-rank Approximation of Linear Maps
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• State-Of-The-Art Algorithms For Low-Rank Dynamic Mode Decomposition
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing