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}\le0.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.