×

Approximation of functions over redundant dictionaries using coherence. (English) Zbl 1094.41500

Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 243-252 (2003).
Summary: 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 \({\mathbf A}\in\mathbb{R}^N\) and a dictionary \({\mathcal D}=\{\varphi_i \}_{i\in I}\) of unit vectors that span \(\mathbb{R}^N\). A representation \({\mathbf R}\) of \(B\) terms for input \({\mathbf A}\in\mathbb{R}^N\) is a linear combination of dictionary elements, \({\mathbf R}= \sum_{i\in\Lambda} \alpha_i\varphi_i\), for \(\varphi_i\in{\mathcal D}\) and some \(\Lambda\), \(| \Lambda|\leq B\). Typically, \(B\ll N\), so that \({\mathbf R}\) is a concise approximation to signal \({\mathbf A}\). The error of the representation indicates how well it approximates \({\mathbf A}\), and is given by \(\| {\mathbf A}-{\mathbf R}\|_2=\sqrt{\sum_t|{\mathbf A}[t]-{\mathbf R}[t]|^2}\). The problem is to find the best \(B\)-term representation, i.e., find an \({\mathbf R}\) that minimizes \(\|{\mathbf A}-{\mathbf R}\|_2\). A dictionary may be redundant in the sense that there is more than one possible exact representation for \({\mathbf A}\), i.e., \(|{\mathcal D}|>N=\dim(\mathbb{R}^N)\). 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 (i.e., vectors are nearly orthogonal). We present an algorithm that preprocesses any such dictionary in time and space polynomial in \(|{\mathcal D}|\), and obtains an \(1+\varepsilon\) approximate representation of the given signal in time nearly linear in signal size \(N\) and polylogarithmic in \(|{\mathcal D}|\); by contrast, most algorithms in the literature require \(\Omega(|{\mathcal 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.
For the entire collection see [Zbl 1006.00017].

MSC:

41A30 Approximation by other special function classes
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite