Restricted Isometry Constants Where $\ell ^{p}$ Sparse Recovery Can Fail for $0≪ p \leq 1$

Abstract

This paper investigates conditions under which the solution of an underdetermined linear system with minimal lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sup> norm, 0 < p les 1, is guaranteed to be also the sparsest one. Matrices are constructed with restricted isometry constants (RIC) delta <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2m</sub> arbitrarily close to 1/radic2 ap 0.707 where sparse recovery with p = 1 fails for at least one m-sparse vector, as well as matrices with delta <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2m</sub> arbitrarily close to one where lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> minimization succeeds for any m-sparse vector. This highlights the pessimism of sparse recovery prediction based on the RIC, and indicates that there is limited room for improving over the best known positive results of Foucart and Lai, which guarantee that lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> minimization recovers all m-sparse vectors for any matrix with delta <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2m</sub> < 2(3 - radic2)/7 ap 0.4531. These constructions are a by-product of tight conditions for lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sup> recovery (0 les p les 1) with matrices of unit spectral norm, which are expressed in terms of the minimal singular values of 2m-column submatrices. Compared to lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> minimization, lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sup> minimization recovery failure is shown to be only slightly delayed in terms of the RIC values. Furthermore in this case the minimization is nonconvex and it is important to consider the specific minimization algorithm being used. It is shown that when lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sup> optimization is attempted using an iterative reweighted lscr <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> scheme, failure can still occur for delta <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2m</sub> arbitrarily close to 1/radic2.