overcomplete

Overcomplete refers to a set of vectors or atoms that spans a vector space but contains more elements than necessary to form a basis. In a finite-dimensional space like R^N, a standard basis has exactly N vectors. An overcomplete set has M vectors with M > N, providing redundancy while still spanning the space. In this sense, an overcomplete system is not a basis, but can still represent any vector in the space.

In signal processing and related fields, overcomplete dictionaries are used to represent signals with more flexibility. A signal s ∈ R^N is expressed as s = Dα, where D ∈ R^{N×M} is the dictionary containing M atoms and α ∈ R^M is a coefficient vector. Because the dictionary is redundant (M > N), there are typically many possible α that yield the same s, i.e., representations are not unique.

A central idea in using overcomplete representations is sparsity. Among all possible representations, one seeks the sparsest coefficient vector α, containing only a few nonzero entries. This leads to problems solved by sparse coding techniques, such as l1-norm minimization or greedy pursuit algorithms (e.g., basis pursuit, matching pursuit). The goal is to capture the signal with as few active atoms as possible, often improving interpretability and robustness.

Applications include denoising, compression, inpainting, and source separation. Benefits of overcompleteness include increased expressiveness and robustness to noise, while drawbacks include higher computational cost and potential ambiguities when dictionary atoms are highly correlated. Dictionary learning methods adapt the dictionary to data to enhance sparsity further.