Abstract

The $\ell_1$ tail-minimization approach to compressed sensing is seen in an earlier report to be more effective than that of the standard basis pursuit. A measure theoretical uniqueness of the sparsest solution was established when sparsity $m/2 < s < m$, where $m$ is the spark of the sensing matrix $A$. A necessary and sufficient condition, tail null space property (tail-NSP), is further established ensuring the unique solution of the $\ell_1$ tail-minimization problem. The tail-NSP offers an insight about the advantage of the tail-minimization approach over the standard basis-pursuit when a reasonable initial estimate of the support index set $T$ is provided. One can see that when an estimate of the solution index set $T$ reasonably intersects with the correct solution index set $S$, the tail-NSP is much more likely to hold than that of the traditional NSP.  Several recovery stability results ensuring the correctness of the tail-minimization solution under noisy measurements are derived. If time permits, the tail-minimization approach applied to sparse frame representations will also be presented. A necessary and sufficient tail dictionary NSP (tail-DNSP) has also been established offering the mathematical guarantee of the unique recovery of the associated tail-min sparse frame recovery problem. Stability results (recovery error bounds) are also obtained in general cases of noisy measurements.