A Caltech Library Service

A Simplified Approach to Recovery Conditions for Low Rank Matrices

Oymak, Samet and Mohan, Karthik and Fazel, Maryam and Hassibi, Babak (2011) A Simplified Approach to Recovery Conditions for Low Rank Matrices. In: 2011 IEEE International Symposium on Information Theory Proceedings. IEEE , Piscataway, NJ, pp. 2318-2322. ISBN 978-1-4577-0596-0.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Recovering sparse vectors and low-rank matrices from noisy linear measurements has been the focus of much recent research. Various reconstruction algorithms have been studied, including ℓ_1 and nuclear norm minimization as well as ℓ_p minimization with p < 1. These algorithms are known to succeed if certain conditions on the measurement map are satisfied. Proofs for the recovery of matrices have so far been much more involved than in the vector case. In this paper, we show how several classes of recovery conditions can be extended from vectors to matrices in a simple and transparent way, leading to the best known restricted isometry and nullspace conditions for matrix recovery. Our results rely on the ability to “vectorize” matrices through the use of a key singular value inequality.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 IEEE. Date of Current Version: 03 October 2011. This work is supported in part by the National Science Foundation under CCF-0729203, CNS-0932428 and CCF-1018927 and supported in part by NSF CAREER grant ECCS-0847077.
Funding AgencyGrant Number
Subject Keywords:rank minimization, sparse recovery
Record Number:CaltechAUTHORS:20120406-112117384
Persistent URL:
Official Citation:Oymak, S.; Mohan, K.; Fazel, M.; Hassibi, B.; , "A simplified approach to recovery conditions for low rank matrices," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.2318-2322, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6033976 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30015
Deposited By: Ruth Sustaita
Deposited On:06 Apr 2012 18:35
Last Modified:03 Oct 2019 03:46

Repository Staff Only: item control page