I would like to analyze the following problem (different cases leads to which solutions to the problem and such):
$$||y-Dx||_2 \leq \epsilon$$
(an overcomplete dictionary matrix $D \in \mathbb{R}^{n \times K}$that contains $K$ prototype signal-atoms for columns, $\{d_j\}^K_{j=1}$ , a signal $y \in \mathbb{R}^n$can be represented as a sparse linear combination of these atoms)
The paper I am reading, says:
if $n < K$ and $D$ is full rank matrix, an infinite number of solutions are available for the problem, hence constraints on the solution must be set.
I need to know the reason behind this(that on the above conditions, there will be an infinite number of solutions), please shed some light on the problem.
I am a computer science graduate, so please explain in not-very complicated facts and theorms so that I can follow your reasoning, very much appreciated.
Since $D\in \mathbb{R}^{n x K}$, it is a linear mapping from a $K$ dimensional space to an $n$ dimensional space. But , we are given that $K>n$. So, in a sense we are mapping a "bigger" space to a "smaller" space and we are looking for a solution to $Dx=y$.i.e., given $y$ in the "smaller" space find $x$ in the bigger space such that $Dx=y$. There could be many such $x$'s satisfying this equation. Therefore we need more constraints to get a unique solution.