Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation
This work addresses sparse signal recovery in transformed domains, offering theoretical improvements for applications like fused LASSO and graph-based models, but it is incremental as it builds on existing LASSO frameworks.
The paper tackles the problem of recovering a signal that is sparse under a linear transformation from noisy measurements, providing theoretical guarantees for a convex optimization method. It shows that with sufficient measurements and bounded condition numbers, the method achieves exact recovery in noiseless cases and error convergence in noisy cases, improving on prior analysis.
We consider the following signal recovery problem: given a measurement matrix $Φ\in \mathbb{R}^{n\times p}$ and a noisy observation vector $c\in \mathbb{R}^{n}$ constructed from $c = Φθ^* + ε$ where $ε\in \mathbb{R}^{n}$ is the noise vector whose entries follow i.i.d. centered sub-Gaussian distribution, how to recover the signal $θ^*$ if $Dθ^*$ 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_θ {1\over 2}\|Φθ- c\|^2 + λ\|Dθ\|_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 $Φ$ 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\geq Ω(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=\bold{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 $m\over p$ (i.e., $#text{edge}\over #text{vertex}$) is larger than a certain constant. Numerical simulations are consistent with our theoretical results.