# Why do we care about Quasi-norm in Statistics and Machine Learning?

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.

• thanks for your informative answer. I am wondering how could you calculate quasi-norm in your examples above.
– jeza
May 10, 2018 at 10:47
• The standard way is $(\sum_{k} \vert x_k\vert ^p)^{1/p}$. Sorry, can't remember the the R command May 10, 2018 at 15:08
• the result 3125 should be 25
– jeza
May 10, 2018 at 15:11
• You're right, sorry about that. Just fixed it. May 10, 2018 at 15:12