This article is part of the series Frames and Overcomplete Representations in Signal Processing, Communications, and Information Theory.

Open Access Research Article

Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion Theory

Alyson K Fletcher1*, Sundeep Rangan2, Vivek K Goyal3 and Kannan Ramchandran4

  • * Corresponding author: Alyson K Fletcher

Author Affiliations

1 Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720-1770, USA

2 Flarion Technologies Inc., Bedminster, NJ 07921, USA

3 Department of Electrical Engineering and Computer Science and Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA 02139-4307, USA

4 Department of Electrical Engineering and Computer Sciences, College of Engineering, University of California, Berkeley, CA 94720-1770, USA

For all author emails, please log on.

EURASIP Journal on Advances in Signal Processing 2006, 2006:026318  doi:10.1155/ASP/2006/26318


The electronic version of this article is the complete one and can be found online at: http://asp.eurasipjournals.com/content/2006/1/026318


Received:9 September 2004
Revisions received:6 June 2005
Accepted:30 June 2005
Published:8 March 2006

© 2006 Fletcher et al.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

If a signal is known to have a sparse representation with respect to a frame, it can be estimated from a noise-corrupted observation by finding the best sparse approximation to . Removing noise in this manner depends on the frame efficiently representing the signal while it inefficiently represents the noise. The mean-squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal are analyzed. First an MSE bound that depends on a new bound on approximating a Gaussian signal as a linear combination of elements of an overcomplete dictionary is given. Further analyses are for dictionaries generated randomly according to a spherically-symmetric distribution and signals expressible with single dictionary elements. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. Asymptotic expressions reveal a critical input signal-to-noise ratio for signal recovery.

References

  1. RJ Duffin, AC Schaeffer, A class of nonharmonic Fourier series. Transactions of the American Mathematical Society 72, 341–366 ( March 1952). Publisher Full Text OpenURL

  2. I Daubechies, Ten Lectures on Wavelets (SIAM, Philadelphia, Pa, USA, 1992)

  3. JW Demmel, Applied Numerical Linear Algebra (SIAM, Philadelphia, Pa, USA, 1997)

  4. DL Donoho, M Vetterli, RA DeVore, I Daubechies, Data compression and harmonic analysis. IEEE Transactions on Information Theory 44(6), 2435–2476 (1998). Publisher Full Text OpenURL

  5. IF Gorodnitsky, BD Rao, Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm. IEEE Transactions on Signal Processing 45(3), 600–616 (1997). Publisher Full Text OpenURL

  6. D Malioutov, M Çetin, AS Willsky, A sparse signal reconstruction perspective for source localization with sensor arrays. IEEE Transactions on Signal Processing 53(8, Part 2), 3010–3022 (2005)

  7. DL Donoho, M Elad, V Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory 52(1), 6–18 (2006)

  8. M Elad, AM Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Transactions on Information Theory 48(9), 2558–2567 (2002). Publisher Full Text OpenURL

  9. DL Donoho, M Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via minimization. Proceedings of the National Academy of Sciences 100(5), 2197–2202 (2003). Publisher Full Text OpenURL

  10. R Gribonval, M Nielsen, Sparse representations in unions of bases. IEEE Transactions on Information Theory 49(12), 3320–3325 (2003). Publisher Full Text OpenURL

  11. J-J Fuchs, On sparse representations in arbitrary redundant bases. IEEE Transactions on Information Theory 50(6), 1341–1344 (2004). Publisher Full Text OpenURL

  12. JA Tropp, Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information Theory 50(10), 2231–2242 (2004). Publisher Full Text OpenURL

  13. DL Donoho, M Elad, On the stability of basis pursuit in the presence of noise submitted to EURASIP Journal on Applied Signal Processing, October 2004

  14. JA Tropp, Just relax: Convex programming methods for subset selection and sparse approximation. ICES Report 0404 (University of Texas at Austin, Austin, Tex, USA, February 2004)

  15. EJ Candès, J Romberg, T Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory 52(2), 489–509 (2006)

  16. EJ Candès, T Tao, Near optimal signal recovery from random projections: Universal encoding strategies? submitted to IEEE Transactions on Information Theory, October 2004

  17. EJ Candès, J Romberg, T Tao, Stable signal recovery from incomplete and inaccurate measurements. in Comput, ed. by . & Appl. Math. Report 05-12 (University of California, Los Angeles, Calif, USA, March 2005) PubMed Abstract | Publisher Full Text OpenURL

  18. AK Fletcher, K Ramchandran, Estimation error bounds for frame denoising. Wavelets: Applications in Signal and Image Processing X, August 2003, San Diego, Calif, USA, Proceedings of SPIE 5207, 40–46

  19. AK Fletcher, S Rangan, VK Goyal, K Ramchandran, Denoising by sparse approximation: Error bounds based on rate-distortion theory. in Electron, ed. by . Res. Lab. Memo M05/5 (University of California, Berkeley, Calif, USA, September 2004)

  20. AK Fletcher, in Estimation via sparse approximation: Error bounds and random frame analysis, M, ed. by . A. thesis (University of California, Berkeley, Calif, USA, May 2005)

  21. M Elad, M Zibulevsky, A probabilistic study of the average performance of basis pursuit sumitted to in IEEE Transactions on Information Theory, December 2004

  22. A Cohen, J-P D'Ales, Nonlinear approximation of random functions. SIAM Journal on Applied Mathematics 57(2), 518–540 (1997). Publisher Full Text OpenURL

  23. RA DeVore, Nonlinear approximation. Acta Numerica 7, 51–150 (1998)

  24. MM Goodwin, Adaptive Signal Models: Theory, Algorithms, and Audio Applications (Kluwer Academic, Boston, Mass, USA, 1998)

  25. K Engan, SO Aase, JH Husoy, Designing frames for matching pursuit algorithms. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '98), May 1998, Seattle, Wash, USA 3, 1817–1820

  26. JA Tropp, IS Dhillon, RW Heath Jr.., T Strohmer, Designing structured tight frames via an alternating projection method. IEEE Transactions on Information Theory 51(1), 188–209 (2005)

  27. G Davis, in Adaptive nonlinear approximations, M, ed. by . S. thesis (New York University, New York, NY, USA, September 1994)

  28. BK Natarajan, Sparse approximate solutions to linear systems. SIAM Journal on Computing 24(2), 227–234 (1995). Publisher Full Text OpenURL

  29. GH Golub, CF Van Loan, Matrix Computations, 2nd edn. (Johns Hopkins University Press, Baltimore, Md, USA, 1989)

  30. SG Mallat, Z Zhang, Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing 41(12), 3397–3415 (1993). Publisher Full Text OpenURL

  31. SS Chen, DL Donoho, MA Saunders, Atomic decomposition by basis pursuit. SIAM Review 43(1), 129–159 (2001). Publisher Full Text OpenURL

  32. R Gribonval, M Nielsen, Highly sparse representations from dictionaries are unique and independent of the sparseness measure. in Tech, ed. by . Rep. R-2003-16 (Department of Mathematical Sciences, Aalborg University, Aalborg, Denmark, October 2003)

  33. R Gribonval, P Vandergheynst, On the exponential convergence of matching pursuits in quasi-incoherent dictionaries. in Tech, ed. by . Rep. 1619 (Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes, France, April 2004)

  34. R Gribonval, M Nielsen, Beyond sparsity: Recovering structured representations by minimization and greedy algorithms—Application to the analysis of sparse underdetermined ICA. in Tech, ed. by . Rep. 1684 (Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes, France, January 2005)

  35. N Saito, Simultaneous noise suppression and signal compression using a library of orthonormal bases and the minimum description length criterion. in Wavelets in Geophysics, ed. by Foufoula-Georgiou E, Kumar P (Academic Press, San Diego, Calif, USA, 1994), pp. 299–324 chapter XI OpenURL

  36. BK Natarajan, Filtering random noise from deterministic signals via data compression. IEEE Transactions on Signal Processing 43(11), 2595–2605 (1995). Publisher Full Text OpenURL

  37. H Krim, D Tucker, S Mallat, DL Donoho, On denoising and best signal representation. IEEE Transactions on Information Theory 45(7), 2225–2238 (1999). Publisher Full Text OpenURL

  38. SG Chang, B Yu, M Vetterli, Adaptive wavelet thresholding for image denoising and compression. IEEE Transactions on Image Processing 9(9), 1532–1546 (2000). PubMed Abstract | Publisher Full Text OpenURL

  39. J Liu, P Moulin, Complexity-regularized image denoising. IEEE Transactions on Image Processing 10(6), 841–851 (2001). Publisher Full Text OpenURL

  40. F Bergeaud, S Mallat, Matching pursuit of images. Proceedings of International Conference on Image Processing (ICIP '95), October 1995, Washington, DC, USA 1, 53–56

  41. R Neff, A Zakhor, Very low bit-rate video coding based on matching pursuits. IEEE Transactions on Circuits and Systems for Video Technology 7(1), 158–171 (1997). Publisher Full Text OpenURL

  42. VK Goyal, M Vetterli, NT Thao, Quantized overcomplete expansions in : Analysis, synthesis, and algorithms. IEEE Transactions on Information Theory 44(1), 16–31 (1998). Publisher Full Text OpenURL

  43. OK Al-Shaykh, E Miloslavsky, T Nomura, R Neff, A Zakhor, Video compression using matching pursuits. IEEE Transactions on Circuits and Systems for Video Technology 9(1), 123–143 (1999). Publisher Full Text OpenURL

  44. F Moschetti, L Granai, P Vandergheynst, P Frossard, New dictionary and fast atom searching method for matching pursuit representation of displaced frame difference. Proceedings of International Conference on Image Processing (ICIP '02), September 2002, Rochester, NY, USA 3, 685–688

  45. JH Conway, RH Hardin, NJA Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces. Experimental Mathematics 5(2), 139–159 (1996)

  46. T Strohmer, RW Heath Jr.., Grassmannian frames with applications to coding and communication. Applied and Computational Harmonic Analysis 14(3), 257–275 (2003). Publisher Full Text OpenURL

  47. NJA Sloane, RH Hardin, WD Smith, et al. A library of putatively optimal spherical codes, together with other arrangements which may not be optimal but are especially interesting for some reason (http://www), . research.att.com/~ njas/packings webcite

  48. RG Gallager, Information Theory and Reliable Communication (John Wiley & Sons, New York, NY, USA, 1968)

  49. GE Andrews, R Askey, R Roy, Special Functions, Encyclopedia of Mathematics and Its Applications (Cambridge University Press, Cambridge, Mass, USA, 1999) 71

  50. T Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression, Information and System Sciences Series (Prentice-Hall, Englewood Cliffs, NJ, USA, 1971)

  51. TM Cover, JA Thomas, Elements of Information Theory (John Wiley & Sons, New York, NY, USA, 1991)

  52. RM Gray, Source Coding Theory (Kluwer Academic, Boston, Mass, USA, 1990)

  53. GR Grimmett, DR Stirzaker, Probability and Random Processes, 2nd edn. (Oxford University Press, Oxford, UK, 1992)

  54. JH Conway, RH Hardin, NJA Sloane, Packing lines, planes, etc.: Packings in Grassmannian spaces. Experimental Mathematics 6(2), 175 (1997) editors' note OpenURL