Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation

Ji Liu, Lei Yuan, Jieping YearXiv 2013 · DOI · arXiv

Abstract

This paper establishes the first comprehensive theoretical guarantees for the "Dictionary LASSO," a generalized recovery method for signals that are sparse under a linear transformation $D$. While the standard LASSO assumes sparsity in the signal itself, many real-world applications—such as image processing or network analysis—involve signals that are sparse in a transformed domain (e.g., gradients or graph edges). By identifying the condition number of the transformation matrix $D$ as a critical factor, the authors prove that the Dictionary LASSO achieves consistent recovery in both noiseless and noisy settings. Specifically, for Gaussian measurement matrices, the signal can be recovered with high probability when the number of measurements $n$ scales with $s \log(p)$, where $s$ is the sparsity level and $p$ is the signal dimension. These results provide a unified framework that encompasses and improves upon existing analyses for specific cases like the Fused LASSO.

Introduction

In high-dimensional statistics and compressed sensing, the LASSO (Least Absolute Shrinkage and Selection Operator) has become the standard tool for signal recovery under the assumption of sparsity. However, the assumption that a signal $\theta^*$ is sparse in its raw form is often too restrictive. In practice, we frequently encounter signals that are sparse under a linear transformation $D \in \mathbb{R}^{m \times p}$. Examples include the Fused LASSO, where the differences between adjacent elements are sparse, and the Edge LASSO, where differences across edges in a graph are sparse.

The optimization problem for this scenario, known as the Dictionary LASSO, is defined as: $$\min_\theta \frac{1}{2}\|\Phi\theta - c\|^2 + \lambda\|D\theta\|_1$$ Where $\Phi$ is the measurement matrix and $c$ is the noisy observation vector. Despite its widespread use, the general theoretical properties of this method—particularly regarding the number of measurements required for consistency—remained under-explored for arbitrary transformation matrices $D$. This paper fills that gap by providing a rigorous analysis of the estimation error and recovery conditions.

Methodology

The authors propose a unified analysis framework centered on the interaction between the measurement matrix $\Phi$ and the transformation matrix $D$. The key technical innovation involves a decomposition of the signal space using the Singular Value Decomposition (SVD) of $D$. This allows the signal $\theta$ to be partitioned into a "sparse part" (associated with the non-zero singular values) and a "free part" (the null space of $D$).

By assuming $\Phi$ is a Gaussian random matrix, the authors utilize random matrix theory to derive a new upper bound for the estimation error $\|\hat{\theta} - \theta^*\|$. A pivotal discovery in this analysis is the role of the condition number ($\kappa$) of $D$, defined as the ratio of the largest to the smallest non-zero singular values. This value effectively determines how much the transformation $D$ distorts the geometry of the signal space, directly impacting the difficulty of recovery.

Theoretical Guarantees

The paper provides two primary theoretical results regarding the performance of the Dictionary LASSO:

  1. Noiseless Recovery: In the absence of noise, if the condition number of $D$ is bounded and the number of measurements $n \geq \Omega(s \log p)$, the true signal $\theta^*$ can be recovered exactly with high probability.
  2. Noisy Consistency: In the presence of sub-Gaussian noise, the method is statistically consistent. If the condition number of $D$ is bounded and the number of measurements grows faster than the sparsity-log-dimension product ($s \log p = o(n)$), the estimation error converges to zero with probability 1 as the problem size $(p, s)$ tends toward infinity.

These results align the Dictionary LASSO with the well-established performance bounds of the standard LASSO (where $D = I$), while extending the theory to more complex, structured sparsity models.

Case Studies: Fused LASSO and Random Graphs

To demonstrate the utility of their framework, the authors analyze the condition numbers for two common structures:

  • Fused LASSO: The authors prove that for the 1D fused LASSO (total variation minimization), the condition number $\kappa$ is bounded by a constant (specifically $\kappa \leq 3$). This explains the inherent stability and success of the fused LASSO in practical applications.
  • Random Graphs: For signals defined on graphs where $D$ represents the edge-difference matrix, the authors show that $\kappa$ is bounded with high probability, provided the graph is sufficiently dense (i.e., the ratio of edges to vertices exceeds a certain threshold).

Numerical simulations conducted by the authors confirm these findings, showing that relative error increases as the condition number of $D$ grows and decreases as the number of measurements $n$ increases, exactly as the theoretical bounds predict.

Conclusion and Future Work

This work provides a rigorous foundation for the Dictionary LASSO, proving that transformed sparsity can be leveraged for signal recovery with the same efficiency as standard sparsity, provided the transformation is well-conditioned.

Future research directions include relaxing the assumption of Gaussian measurement matrices to accommodate more structured matrices found in medical imaging (MRI) or geophysics. Additionally, the authors suggest extending this analysis to non-squared loss functions that satisfy "restricted strong convexity," which would broaden the applicability of these guarantees to a wider range of statistical models.

Summary updated

Abstract

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.
BibTeX
@misc{liu2013dictionary,
  author = {Ji Liu and Lei Yuan and Jieping Ye},
  title = {{Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation}},
  year = {2013},
  eprint = {1305.0047},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1305.0047},
}
Figure