Sparse Representations Are Most Likely to Be the Sparsest Possible
- PDF / 528,434 Bytes
- 12 Pages / 600.03 x 792 pts Page_size
- 55 Downloads / 164 Views
Sparse Representations Are Most Likely to Be the Sparsest Possible Michael Elad Computer Science Department, The Technion – Israel Institute of Technology, Haifa 32000, Israel Received 5 September 2004; Revised 23 January 2005; Accepted 27 January 2005 Given a signal S ∈ RN and a full-rank matrix D ∈ RN ×L with N < L, we define the signal’s overcomplete representations as all α ∈ RL satisfying S = Dα. Among all the possible solutions, we have special interest in the sparsest one—the one minimizing α0 . Previous work has established that a representation is unique if it is sparse enough, requiring α0 < Spark(D)/2. The measure Spark(D) stands for the minimal number of columns from D that are linearly dependent. This bound is tight—examples can be constructed to show that with Spark(D)/2 or more nonzero entries, uniqueness is violated. In this paper we study the behavior of overcomplete representations beyond the above bound. While tight from a worst-case standpoint, a probabilistic point of view leads to uniqueness of representations satisfying α0 < Spark(D). Furthermore, we show that even beyond this point, uniqueness can still be claimed with high confidence. This new result is important for the study of the average performance of pursuit algorithms—when trying to show an equivalence between the pursuit result and the ideal solution, one must also guarantee that the ideal result is indeed the sparsest. Copyright © 2006 Hindawi Publishing Corporation. All rights reserved.
1.
INTRODUCTION
1.1. General—sparse representations In signal processing we are often interested in a replacement of the representation, seeking some simplification for an obvious gain. This is the rational behind the so many transforms proposed over the past several centuries, such as the Fourier, cosine, wavelets, and many others. The basic idea is to “change language,” and describe the signal differently, in the hope that the new description is better for the application in mind. A natural justification for a transform is that given a signal, a representation has already been imposed due to the use of the trivial basis (e.g., samples as a function of time/space), and there is no reason to believe that this representation is the most appropriate one for our needs. The ease with which linear transforms are operated and analyzed keeps those as the first priority candidates in defining alternative representations. It is therefore not surprising to find that linear transforms are the more popular ones in theory and practice in signal processing. A linear transform is defined through the use of a full-rank matrix D ∈ RN ×L , where L ≥ N. Given the signal S ∈ RN , its representation is defined by S = Dα,
(1)
where α ∈ RL . For the case of L = N (and a nonsingular matrix D due to the full-rank property), the above relationship implies a linear operation both for the forward transform (from S to α) and its inverse. Many of the practical transforms are of this type, and many of them go further and simplify the matrix D to be structured and unitary
Data Loading...
