Author: Yin Zhang
Vol.1 (1) pp 79
Abstract: Compressive sensing (CS) is an emerging methodology in computational
signal processing that has recently attracted intensive research activities. At present,
the basic CS theory includes recoverability and stability: the former quantifies the
central fact that a sparse signal of length n can be exactly recovered from far fewer
than n measurements via _1-minimization or other recovery techniques, while the
latter specifies the stability of a recovery technique in the presence of measurement
errors and inexact sparsity. So far, most analyses in CS rely heavily on the Restricted
Isometry Property (RIP) for matrices.
In this paper, we present an alternative, non-RIP analysis for CS via _1-minimization.
Our purpose is three-fold: (a) to introduce an elementary and RIP-free treatment
of the basic CS theory; (b) to extend the current recoverability and stability results
so that prior knowledge can be utilized to enhance recovery via _1-minimization;
and (c) to substantiate a property called uniform recoverability of _1-minimization;
that is, for almost all random measurement matrices recoverability is asymptotically
identical. With the aid of two classic results, the non-RIP approach enables us to
quickly derive from scratch all basic results for the extended theory.
Keywords: Compressive sensing • _1-Minimization • Non-RIP analysis •
Recoverability and stability • Prior information • Uniform recoverability