Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation

We consider the following signal recovery problem: given a measurement matrix $\mathrm{\Phi }\in {\mathbb{R}}^{n\times p}$ and a noisy observation vector $c\in $\mathbb{R}$^{n}$constructedfrom$c = \Phi\theta^* + \epsilon$where$\epsilon\in $\mathbb{R}$^{n}$ is the noise vector whose entries follow i.i.d. centered sub-Gaussian distribution, how to recover the signal ${\theta }^{\ast }$ if $D{\theta }^{\ast }$ is sparse {\rca under a linear transformation} $D\in {\mathbb{R}}^{m\times p}$? One natural method using convex optimization is to solve the following problem: $$\min_{\theta} {1\over 2}|\Phi\theta - c|^2

• \lambda|D\theta|_1.$$ This paper provides an upper bound of the estimate error and shows the consistency property of this method by assuming that the design matrix $\mathrm{\Phi }$ is a Gaussian random matrix. Specifically, we show 1) in the noiseless case, if the condition number of $D$ is bounded and the measurement number $n\ge \mathrm{\Omega }(s\log (p))$ where $s$ is the sparsity number, then the true solution can be recovered with high probability; and 2) in the noisy case, if the condition number of $D$ is bounded and the measurement increases faster than $s\log (p)$, that is, $s\log (p)=o(n)$, the estimate error converges to zero with probability 1 when $p$ and $s$ go to infinity. Our results are consistent with those for the special case $D={\mathbf{I}}_{p\times p}$ (equivalently LASSO) and improve the existing analysis. The condition number of $D$ plays a critical role in our analysis. We consider the condition numbers in two cases including the fused LASSO and the random graph: the condition number in the fused LASSO case is bounded by a constant, while the condition number in the random graph case is bounded with high probability if $\frac{m}{p}$ (i.e., #text{edge}\over #text{vertex}) is larger than a certain constant. Numerical simulations are consistent with our theoretical results.