Approximation of functions over redundant dictionaries using coherence

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 and a dictionary D = fOE i g i2I of unit vectors that span R . A representation R of B terms for input A 2 R is a linear combination of dictionary elements, R = i2 ff i OE i , for OE i 2 D and some , jj 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 kA \\Gamma Rk 2 = problem is to find the best B-term representation, i.e., find a R that minimizes kA \\Gamma Rk 2 . A dictionary may be redundant in the sense that there is more than one possible exact representation for A, i.e., jDj ? N = dim(R ). 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.