2017/12/05 by Yanjun Li, Kiryung Lee, Li, Yanjun +3
Engineering · Medicine · #Sparse and Compressive Sensing Techniques #Advanced MRI Techniques and Applications #Medical Imaging Techniques and Applications
paper · pdf · doi:10.48550/arxiv.1712.01915
Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper fills a theoretical gap in matrix recovery: the optimal sample complexity for stable recovery without constants or log factors. We treat sparsity, low-rankness, and potentially other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions. 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 result -- the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.