Sparse Signal Reconstruction: Sequential Convex Relaxation, Restricted Null Space Property, and Error Bounds

For (nearly) sparse signal reconstruction problems, we propose an inexact sequential convex relaxation algorithm (iSCRA-TL1) by constructing the working index set iteratively with a simple and adaptive strategy, and solving inexactly a sequence of truncated <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-norm minimization subproblems. A toy example is provided to demonstrate that the exact version of iSCRA-TL1 can successfully reconstruct the true sparse signal, but almost all the present sequential convex relaxation algorithms starting from an optimal solution of the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-norm minimization fail to recover it. To provide theoretical guarantees for iSCRA-TL1, we introduce two new types of null space properties, restricted null space property (RNSP) and sequential restricted null space property (SRNSP), and prove that they are both weaker than the common stable NSP, while their robust versions are not stronger than the existing robust NSP. Then, we justify that under a suitable (robust) SRNSP, iSCRA-TL1 can identify the support of the true r-sparse signal or the index set of the first r largest (in modulus) entries of the true nearly r-sparse signal via at most r truncated <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-norm minimization, and the error bound of its final output from the true (nearly) r-sparse signal is also quantified. To the best of our knowledge, this is the first sequential convex relaxation algorithm to recover the support of the true (nearly) sparse signal under a weaker NSP condition within a specific number of steps, provided that the classical <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-norm minimization problem lacks the good robustness.