Sparse approximation, denoising, and large random frames

Alyson K. Fletcher, Sundeep Rangan, Vivek K. Goyal

Research output: Contribution to journalConference articlepeer-review


If a signal x is known to have a sparse representation with respect to a frame, the signal can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. The ability to remove noise in this manner depends on the frame being designed to efficiently represent the signal while it inefficiently represents the noise. This paper analyzes the mean squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal. Analyses are for dictionaries generated randomly according to a spherically-symmetric distribution. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. In the limit of large dimension, these approximations have simple forms. The asymptotic expressions reveal a critical input signal-to-noise ratio (SNR) for signal recovery.

Original languageEnglish (US)
Article number59140M
Pages (from-to)1-10
Number of pages10
JournalProceedings of SPIE - The International Society for Optical Engineering
StatePublished - 2005
EventWavelets XI - San Diego, CA, United States
Duration: Jul 31 2005Aug 3 2005


  • Dictionary-based representations
  • Estimation
  • Isotropic random matrices
  • Nonlinear approximation
  • Stable signal recovery
  • Subspace fitting

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Sparse approximation, denoising, and large random frames'. Together they form a unique fingerprint.

Cite this