Home Page





Editorial Board



Open Source Software



RSS Feed

Guaranteed Sparse Recovery under Linear Transformation

Ji Liu, Lei Yuan, Jieping Ye
JMLR W&CP 28 (3) : 91–99, 2013


We consider the following signal recovery problem: given a measurement matrix \(\Phi\in \mathbb{R}^{n\times p}\) and a noisy observation vector \(c\in \mathbb{R}^{n}\) constructed from \(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^*\) if \(D\theta^*\) is sparse 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 \(\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\geq \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=\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.

Related Material