I am reading a published paper on
K- SVD: An algorithm for designing overcomplete dictionaries for sparse representation
In the introduction, it says:
Recent years have witnessed a growing interest in the research for sparse representations of signals. Using 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 representation of $y$ may either be exact $y=Dx$ or approximate, $y \approx Dx$, satisfying $||y-Dx||_p \leq \epsilon$. The vector contains the representation coefficients of the signal $y$. In approximation methods, typical norms used for measuring the deviation are the $l^p$-norms for $p=1,2$ and $\infty$. In this paper, we shall concentrate on the case of $p=2$.
My main question is, how the inequality is obtained from the quality or approximation? Plus, why do we use $l^p$-norm for $p=1,2$ and $\infty$ for measuring deviation? And is there any specific reason as to why they have chosen $p=2$?
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.
I am also a computer scientist. Depending on your norm you punish outliers (= values that deviate a lot from the mean) harder or less hard. The higher your norm is, the more emphasis you put on your outliers.
The two norm is the most natural one, since it is the one you normally use when measuring distances in a 2 dimensional plane. That is probably the reason why people use this one the most. The 1-norm is used when you even want to decrease the effect of outliers, and $\infty$ is an extreme were the biggest outlier just determines your error measure.
In fact 2-norm is most of the time the most important. Sometimes people also want to investigate extreme cases and that is why they sometimes also investigate $\infty$ norm.