Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion Theory
- PDF / 776,089 Bytes
- 19 Pages / 600.03 x 792 pts Page_size
- 0 Downloads / 224 Views
Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion Theory Alyson K. Fletcher,1 Sundeep Rangan,2 Vivek K Goyal,3 and Kannan Ramchandran4 1 Department
of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720-1770, USA 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 2 Flarion
Received 9 September 2004; Revised 6 June 2005; Accepted 30 June 2005 If a signal x is known to have a sparse representation with respect to a frame, it can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. 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. Copyright © 2006 Alyson K. 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.
1.
INTRODUCTION
Estimating a signal from a noise-corrupted observation of the signal is a recurring task in science and engineering. This paper explores the limits of estimation performance in the case where the only a priori structure on the signal x ∈ RN is that it has known sparsity K with respect to a given set of N vectors Φ = {ϕi }M i=1 ⊂ R . The set Φ is called a dictionary and is generally a frame [1, 2]. The sparsity of K with respect to Φ means that the signal x lies in the set
ΦK = v ∈ R | v = N
M
αi ϕi with at most K nonzero αi ’s .
i=1
(1) In many areas of computation, exploiting sparsity is motivated by reduction in complexity [3]; if K N, then certain computations may be more efficiently made on α than on x. In compression, representing a signal exactly or approximately by a member of ΦK is a common first step in efficiently representing the signal, though much more is known when Φ is a basis or union of wavelet bases than is known in the general case [4]. Of more direct interest here is that
sparsity models are becoming prevalent in estimation problems; s
Data Loading...
