Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I have understood that quasi-norm does not satisfy the inequality triangle.
I also know that the norm is a function on vector space that assigns length or size to the vector.
However, I do not exactly understand quasi-norm.
I do not really understand why we want to study them within statistics and machine learning.
I was wondering if anyone knew a nice intuitive motivation for the study of quasi-norm?
Many thanks
One common area where quasinorms are used involves dimension reduction and sparsity.
Consider Lasso, where the standard OLS problem is augmented by a penalty, or cost term:.
$$\min_{\beta}\dfrac{1}{N}\|Y-X\beta\|_2 \quad s.t. \|\beta\|_1\leq t$$
where $\|\cdot\|_p$ is the standard $L_p$ norm.
Why are we doing this again? Well, the "energy" of the signal we're trying to study might be clustered in a small number elements of $\beta = [\beta_0, \beta_1, ..., \beta_N]^T$, and by adding the above cost term, we penalize elements of $\beta$ that are "less important" to modelling the system. These "less important" ones get zeroed out, and we're left with a smaller-dimension system than where we started.
With the advent of big data and problems of extremely high dimension, there's been a lot of research suggesting that the standard $\|\cdot\|_1$ reduction (Lasso), or the the standard $\|\cdot\|_2$ reduction (Ridge) might not be enough.
That is, we can get better results by using $L_p$ norms with $0<p<1$. This is where quasinorms come into play, since these norms no longer satisfy the triangle inequality property of $L_p$ norms with $p\geq 1$
Diving a bit deeper, compare two different vectors representing the hypothetical "true" value of $\beta$ $$\beta_1 = [1,1,1,1,1]$$
Notice that this vector is not sparse. i.e. we need all the elements of $\beta_1$. The $L_p$ norms are $$\|\beta_1\|_2 \approx 2.23$$ $$\|\beta_1\|_1 = 5$$ $$\|\beta_1\|_{1/2} = 25$$
Now, compare this to the following "sparse" vector $$\beta_2 = [2.25,0,0,0,0]$$
Which gives us $$\|\beta_2\|_2 = 2.25$$ $$\|\beta_2\|_1 = 2.25$$ $$\|\beta_2\|_{1/2} = 2.25$$
Notice that $$\|\beta_1\|_2 \approx \|\beta_2\|_2$$ but that the differences of the norms really start to diverge as $p\rightarrow 0$
Using the initial Lasso example, if we sub in $L_{1/2}$ for $L_1$ in the cost term in the first equation, we see that a non-sparse estimates of $\beta$ will be greatly penalized. Thus, the smaller the value of $p$ the more elements of $\beta$ will end up being zeroed out.
This is an example using a small, five-dimensional object, but the results get more apparent as the dimension of the space you're working in increases. This is why it's relevant for big data and machine learning.
