Guaranteed sparse recovery under linear transformation

Ji Liu, Lei Yuan, Jieping Ye

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


We consider the following signal recovery problem: given a measurement matrix Φ ∈ ℝnxp and a noisy observation vector c ∈ ℝnconstructed from c = Φθ*+ ε where ε ∈ ℝn is the noise vector whose entries follow i.i.d. centered sub-Gaussian distribution, how to recover the signal θ&z,ast; if Dθ*is sparse under a linear transformation D ∈ ℝmxp? One natural method using convex optimization is to solve the following problem:(Equation Presented) 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 ≥ Ω(slog(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 slog(p), that is, slog(p) = o(n), the estimate error converges to zero with probability 1 when p and s go to infinity. Our resuits are consistent with those for the special case D = Ipxp (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/p (i.e., #edge/#vertex) is larger than a certain constant. Numerical simulations are consistent with our theoretical results.

Original languageEnglish (US)
Title of host publication30th International Conference on Machine Learning, ICML 2013
PublisherInternational Machine Learning Society (IMLS)
Number of pages9
EditionPART 2
StatePublished - 2013
Event30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, United States
Duration: Jun 16 2013Jun 21 2013


Other30th International Conference on Machine Learning, ICML 2013
Country/TerritoryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Sociology and Political Science


Dive into the research topics of 'Guaranteed sparse recovery under linear transformation'. Together they form a unique fingerprint.

Cite this