Solve-Select-Scale: A Three Step Process For Sparse Signal Estimation

In the theory of compressed sensing (CS), the sparsity $\mathrm{\parallel }x{\mathrm{\parallel }}_0$ of the unknown signal $\mathbf{x}\in {\mathcal{R}}^n$ is of prime importance and the focus of reconstruction algorithms has mainly been either $\mathrm{\parallel }x{\mathrm{\parallel }}_0$ or its convex relaxation (via $\mathrm{\parallel }x{\mathrm{\parallel }}_1$). However, it is typically unknown in practice and has remained a challenge when nothing about the size of the support is known. As pointed recently, $\mathrm{\parallel }x{\mathrm{\parallel }}_0$ might not be the best metric to minimize directly, both due to its inherent complexity as well as its noise performance. Recently a novel stable measure of sparsity $s($\mathbf{x}$) := |$\mathbf{x}$|_1^2/|$\mathbf{x}$|_2^2$ has been investigated by Lopes \cite{Lopes2012}, which is a sharp lower bound on $\mathrm{\parallel }\mathbf{x}{\mathrm{\parallel }}_0$. The estimation procedure for this measure uses only a small number of linear measurements, does not rely on any sparsity assumptions, and requires very little computation. The usage of the quantity $s(\mathbf{x})$ in sparse signal estimation problems has not received much importance yet. We develop the idea of incorporating $s(\mathbf{x})$ into the signal estimation framework. We also provide a three step algorithm to solve problems of the form $\mathbf{A}\mathbf{x}=\mathbf{b}$ with no additional assumptions on the original signal $\mathbf{x}$.