Accelerating the pace of engineering and science

# Documentation Center

• Trial Software

## Sparse Representation in Redundant Dictionaries

### Redundant Dictionaries and Sparsity

Representing a signal in a particular basis involves finding the signal's unique set of expansion coefficients in that basis. While there are many advantages to signal representation in a basis, particularly an orthogonal basis, there are also disadvantages.

The ability of a basis to provide a sparse representation of a signal depends on how well the signal characteristics match the characteristics of the basis vectors. For example, smooth continuous signals are sparsely represented in a Fourier basis, while impulses are not. On the other hand, a smooth signal with isolated discontinuities is sparsely represented in a wavelet basis, while a wavelet basis is not efficient at representing a signal whose Fourier transform has narrow high frequency support.

Real-world signals often contain features that prohibit sparse representation in any single basis. For these signals, you want the ability to choose vectors from a set not limited to a single basis. Because you want to ensure that you can represent every vector in the space, the dictionary of vectors you choose from must span the space. However, because the set is not limited to a single basis, the dictionary is not linearly independent.

Because the vectors in the dictionary are not a linearly independent set, the signal representation in the dictionary is not unique. However, by creating a redundant dictionary, you can expand your signal in a set of vectors that adapt to the time-frequency or time-scale characteristics of your signal. You are free to create a dictionary consisting of the union of several bases. For example, you can form a basis for the space of square-integrable functions consisting of a wavelet packet basis and a local cosine basis. A wavelet packet basis is well adapted to signals with different behavior in different frequency intervals. A local cosine basis is well adapted to signals with different behavior in different time intervals. The ability to choose vectors from each of these bases greatly increases your ability to sparsely represent signals with varying characteristics.

### Nonlinear Approximation in Dictionaries

Define a dictionary as a collection of unit-norm elementary building blocks for your signal space. These unit-norm vectors are called atoms. If the atoms of the dictionary span the entire signal space, the dictionary is complete.

If the dictionary atoms form a linearly-dependent set, the dictionary is redundant. In most applications of matching pursuit, the dictionary is complete and redundant.

Let {φk} denote the atoms of a dictionary. Assume the dictionary is complete and redundant. There is no unique way to represent a signal from the space as a linear combination of the atoms.

An important question is whether there exists a best way. An intuitively satisfying way to choose the best representation is to select the φk yielding the largest inner products (in absolute value) with the signal. For example, the best single φk is

which for a unit-norm atom is the magnitude of the scalar projection onto the subspace spanned by φk.

The central problem in matching pursuit is how you choose the optimal M-term expansion of your signal in a dictionary.