16
$\begingroup$

I am new to optimization. I keep seeing equations that have a superscript 2 and a subscript 2 on the right-hand side of a norm. For instance, here is the least squares equation

min $ ||Ax-b||^2_2$

I think I understand the superscript 2: it means to square the value of the norm. But what is the subscript 2? How should I read these equations?

$\endgroup$
  • 3
    $\begingroup$ $||\theta||_p$ is the $\ell_p$-norm of $\theta$. Let's say $\theta$ is $d$-dimensional, then $||\theta||_p = \left(\sum_{i=1}^d |\theta_i|^p\right)^\frac{1}{p}$. $\endgroup$ – Sobi Dec 15 '15 at 17:21
  • $\begingroup$ Single vertical bars are used for absolute value (magnitude): $|\theta|$ $\endgroup$ – Scortchi Dec 15 '15 at 17:28
  • $\begingroup$ Thanks!...but what is the superscript 2 for?...the subsript is for the pth norm....the superscript is for? $\endgroup$ – mathopt Dec 15 '15 at 18:37
  • $\begingroup$ @user1467929: Squaring - if it's anything else they'd surely have said. $\endgroup$ – Scortchi Dec 15 '15 at 19:48
16
$\begingroup$

You are right about the superscript. The subscript $||.||_p$ specifies the $p$-norm.

Therefore:

$$||x_i||_p=(\sum_i|x_i|^p)^{1/p}$$

And:

$$||x_i||_p^p=\sum_i|x_i|^p$$

$\endgroup$
  • $\begingroup$ ah. And there are conventions for the meanings of the subscripts I see. en.wikipedia.org/wiki/Norm_(mathematics)#p-norm. So like 1 = taxicab norm, 2=euclid norm etc $\endgroup$ – bernie2436 Nov 13 '15 at 14:04
  • $\begingroup$ @bernie2436: These are special cases of the general definition given in the answer above (except maybe the sup-norm with $p = \infty$) $\endgroup$ – Michael M Nov 13 '15 at 14:55
10
$\begingroup$

$\|x\|_2$ is the Euclidean norm of the vector $x$; $\|x\|_2^2$ is the squared Euclidean norm of $x$. Note that as the Euclidean norm is probably the mostly commonly used norm people routinely abbreviated by $\|x\|$. By definition when assuming a Euclidean vector space: $\|x\|_2 := \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$.

As mentioned in the comments, the subscript $p$ refers to the degree of the norm. Other commonly used norms are for $p = 0$, $p = 1$ and $p = \infty$. For $p=0$ one gets the number of non-zero elements in $x$, for $p=1$ (ie. $\|x\|_1$) one gets the Manhattan norm and for $p = \infty$ one gets the maximum absolute value from the elements in $x$. Both $p = 0$ and $p = 1$ are popular in sparse/compressed application settings where one wants to "urge" some coefficient(s) to be zero.

$\endgroup$

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.