# An Oxymoron of Sparse Proportions?

While reading the paper, M. Babaie-Zadeh, V. Vigneron, and C. Jutten, “Sparse Decomposition over Non-full-rank dictionaries,” Proc. ICASSP, 2009, I came across the following phrase:

For a non-full rank overcomplete dictionary …

For some moments this shook my confidence in understanding what it means for a dictionary to be overcomplete, and for the dictionary matrix to have full rank. How can one call a dictionary overcomplete while there exist vectors that don’t exist in its column space? That sounds to me like an incomplete dictionary. In other words, I have always thought that for a dictionary $$\MD$$ of $$n$$ atoms of dimension $$m$$, $$\text{rank}(\MD) = m$$ implies completeness, and overcompleteness when $$n > m$$. And if a fat dictionary is not full rank, i.e., $$\text{rank}(\MD) < m$$, then it cannot be complete, not to mention overcomplete. In other words, one cannot have an overcomplete dictionary that is not full rank.

Perhaps though, the designation “overcomplete” is like the term “optimized,” where it is meaningless without a reference. Optimized with respect to what? Overcomplete with respect to what? If we have a space described by \mathcal{A} = \text{span}\{\va_i \in \mathcal{R}^m : ||\va_i|| = 1\}_{i=1, \ldots, k}, k n\), the dictionary is overcomplete.”

Just because a dictionary is fat does not make it overcomplete. Fatness does mean that $$\MA\vs = \vx$$ is an underdetermined system, but not necessarily that there always exists a solution to this system. Completeness means that there will always exist a solution to $$\MA\vs = \vx$$, and overcompleteness means that there exists an infinite number of solutions. In other words, a fat matrix does not necessarily mean it is an overcomplete dictionary; but overcompleteness implies a fat and full rank dictionary. Thus, “overcomplete” (and thus full rank) is a stronger condition on a dictionary than “fat.”

Am I missing something with regards to “non-full rank overcomplete dictionaries,” or is this truly an oxymoron?