Challenging Restricted Isometry Constants with Greedy Pursuit

Abstract—This paper proposes greedy numerical schemes to compute lower bounds of the restricted isometry constants that are central in compressed sensing theory. Matrices with small restricted isometry constants enable stable recovery from a small set of random linear measurements. We challenge this compressed sampling recovery using greedy pursuit algorithms that detect ill-conditionned sub-matrices. It turns out that these sub-matrices have large isometry constants and hinder the performance of compressed sensing recovery. I. COMPRESSED SAMPLING RECOVERY Compressed sampling paradigm consists in acquiring a small number of linear measurements y = Ax, where x ∈ RN is the high resolution signal to recover, and y ∈ RP is the vector of measurements with P N. Using the underdeter-mined sensing matrix A that is drawn from a proper rando