6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.