|
 ABSTRACT
One of the central problems of modern mathematical approximation theory is to approximate functions, or signals, concisely, with elements from a large candidate set called a dictionary. Formally, we are given a signal A ∈ RN and a dictionary D = {φi}i∈I of unit vectors that span RN. A representation R of B terms for input A ∈ RN is a linear combination of dictionary elements, R = σi∈A αiφi, for φi ∈ D and some A, |A| ≥ B. Typically, B ⪡ N, so that R is a concise approximation to signal A. The error of the representation indicates by how well it approximates A, and is given by ∥A - R∥2 = √Σt|A[t - R[t]|2. The problem is to find the best B-term representation, i.e., find a R that minimizes ∥A - R∥2. A dictionary may be redundant in the sense that there is more than one possible exact representation for A, i.e., |D| > N = dim(RN). Redundant dictionaries are used because, both theoretically and in practice, for important classes of signals, as the size of a dictionary increases, the error and the conciseness of the approximations improve.We present the first known efficient algorithm for finding a provably approximate representation for an input signal over redundant dictionaries. We identify and focus on redundant dictionaries with small coherence (ie., vectors are nearly orthogonal). We present an algorithm that preprocesses any such dictionary in time and space polynomial in |D|, and obtains an 1 + ε approximate representation of the given signal in time nearly linear in signal size N and polylogarithmic in |D|; by contrast, most algorithms in the literature require Ω(|D|)time, and, yet, provide no provable bounds. The technical crux of our result is our proof that two commonly used local search techniques, when combined appropriately, gives a provably near-optimal signal representation over redundant dictionaries with small coherence. Our result immediately applies to several specific redundant dictionaries considered by the domain experts thus far. In addition, we present new redundant dictionaries which have small coherence (and therefore are amenable to our algorithms) and yet have significantly large sizes, thereby adding to the redundant dictionary construction literature.Work with redundant dictionaries forms the emerging field of highly nonlinear approximation theory. We have presented algorithmic results for some of the most basic problems in this area, but other mathematical and algorithmic questions remain to be explored.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
Constructive Approximation. http://www.math.vanderbilt.edu/~ca.
|
| |
3
|
E. Candes. Ridgelets: Theory and Applications. PhD thesis, Dept. of Stastistics, Stanford University, 1998.
|
| |
4
|
|
| |
5
|
R. Coifman and M. V. Wickerhauser. Entropy-based algorithms for best basis selection. IEEE Trans. inform. Theory, 38(2), March 1992.
|
| |
6
|
|
| |
7
|
G. Davis, S. Mallat, and M. Avellaneda. Greedy adaptive approximation. Journal of Constructive Approximation, 13:57--98, 1997.
|
| |
8
|
R. A. DeVore. Nonlinear approximation. Acta Numerica, 7:51--150, 1998.
|
| |
9
|
R. A. DeVore and G. G. Lorentz. Constructive Approximation. Springer-Verlag, New York, 1993.
|
| |
10
|
D. Donoho. Wedgelets: Nearly-minimax estimation of edges. Annals of Statistics, 27:859--897, 1999.
|
| |
11
|
D. L. Donoho and X. Huo. Beamlet pyramids: A new form of multiresolution analysis, suited for extracting lines, curves, and objects from very noisy image data. In Proceedings of SPIE 2000, volume 4119, 2000.
|
 |
12
|
Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
[doi> 10.1145/509907.509966]
|
| |
13
|
A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
[doi> 10.1145/509907.509933]
|
| |
14
|
|
| |
15
|
|
| |
16
|
The Journal of Approximation Theory. http://www.math.ohio-state.edu/JAT.
|
| |
17
|
Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States
[doi> 10.1145/276698.276877]
|
| |
18
|
S. Mallat and Z. Zhang. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, 41(12):3397--3415, 1993.
|
| |
19
|
C. M. Thiele and L. F. Villemoes. A fast algorithm for adapted time frequency tilings. Applied and Computational Harmonic Analysis, 3:91--99, 1996.
|
| |
20
|
|
| |
21
|
Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad. Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition. In Proc. of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, pages 40--44, 1993.
|
| |
22
|
V. N. Temlyakov. The best m-term approximation and greedy algorithms. Advances in Computational Math., 8:249--265, 1998.
|
| |
23
|
|
| |
24
|
Lars Villemoes. Best approximation with Walsh atoms. Constructive Approximation, 13:329--355, 1997.
|
| |
25
|
Lars Villemoes. Nonlinear approximation with Walsh atoms. In A. Le Méhauté, C. Rabut, and L. L. Schumaker, editors, Surface Fitting and Multiresolution Methods, pages 329--336. Vanderbilt University Press, 1997.
|
CITED BY 12
|
|
|
|
|
|
|
|
|
|
|
|
|
|
William Aiello , Anna Gilbert , Brian Rexroad , Vyas Sekar, Sparse approximations for high fidelity compression of network traffic data, Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, p.22-22, October 19-21, 2005, Berkeley, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.1