Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2011 | public
Journal Article

Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements

Abstract

This paper presents several novel theoretical results regarding the recovery of a low-rank matrix from just a few measurements consisting of linear combinations of the matrix entries. We show that properly constrained nuclear-norm minimization stably recovers a low-rank matrix from a constant number of noisy measurements per degree of freedom; this seems to be the first result of this nature. Further, with high probability, the recovery error from noisy data is within a constant of three targets: 1) the minimax risk, 2) an "oracle" error that would be available if the column space of the matrix were known, and 3) a more adaptive "oracle" error which would be available with the knowledge of the column space corresponding to the part of the matrix that stands above the noise. Lastly, the error bounds regarding low-rank matrices are extended to provide an error bound when the matrix has full rank with decaying singular values. The analysis in this paper is based on the restricted isometry property (RIP).

Additional Information

© 2011 IEEE. Manuscript received January 06, 2010; revised October 06, 2010; accepted October 07, 2010. Date of current version March 16, 2011. This work was supported in part by ONR Grants N00014-09-1-0469 and N00014-08-1-0749, in part by the NSF grant CNS-0911041, and in part by the Waterman Award also from NSF.

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023