On RIC bounds of Compressed Sensing Matrices for Approximating Sparse Solutions Using ${\ell }_q$ Quasi Norms

Abstract

This paper follows the recent discussion on the sparse solution recovery with quasi-norms ${\ell }_q,q\in (0,1)$ when the sensing matrix possesses a Restricted Isometry Constant ${\delta }_{2k}$ (RIC). Our key tool is an improvement on a version of "the converse of a generalized Cauchy-Schwarz inequality" extended to the setting of quasi-norm. We show that, if ${\delta }_{2k}\le 1/2$, any minimizer of the $l_q$ minimization, at least for those $q\in (0,0.9181]$, is the sparse solution of the corresponding underdetermined linear system. Moreover, if ${\delta }_{2k}\le 0.4931$, the sparse solution can be recovered by any $l_q,q\in (0,1)$ minimization. The values $0.9181$ and $0.4931$ improves those reported previously in the literature.

16pages