TY - GEN
T1 - Optimal sample complexity for stable matrix recovery
AU - Li, Yanjun
AU - Lee, Kiryung
AU - Bresler, Yoram
N1 - Funding Information:
This work was supported in part by the National Science Foundation (NSF) under Grant IIS 14-47879
Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper establishes (near) optimal sample complexities for stable matrix recovery without constants or log factors. We treat sparsity, low-rankness, and other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions, which include notoriously challenging cases such as simultaneously sparse and low-rank matrices. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental achievability result - the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.
AB - Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper establishes (near) optimal sample complexities for stable matrix recovery without constants or log factors. We treat sparsity, low-rankness, and other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions, which include notoriously challenging cases such as simultaneously sparse and low-rank matrices. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental achievability result - the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.
UR - http://www.scopus.com/inward/record.url?scp=84985897986&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84985897986&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2016.7541265
DO - 10.1109/ISIT.2016.7541265
M3 - Conference contribution
AN - SCOPUS:84985897986
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 81
EP - 85
BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016
Y2 - 10 July 2016 through 15 July 2016
ER -