7
$\begingroup$

Why we use the 2-norm all over the place instead of the 1-norm although both are equivalent and the 1-norm is more effieciently computable? I am currently implementing an algorithm that normalizes a vector in each step (using 2-norm). So i could also just use the 1-norm instead? More details: power iteration for the calculation of the dominat eigenvalue of a matrix:

x:=random vector of length numrows(A) x=x/||x|| 
while l changes (e.g. abs(l-l_last)<tolerance)
    x=Av
    l=||x||
    x=x/||x||
$\endgroup$
9
  • 3
    $\begingroup$ What do you mean they are equivalent? In what sense? $\endgroup$
    – mathreadler
    Jul 14 '18 at 21:08
  • 2
    $\begingroup$ what will it help you if you don't know what sense this equivalence? Here is from wikipedia : "However, all these norms are equivalent in the sense that they all define the same topology.". So unless we are interested in the topology of the space then maybe we should not care about that equivalence. $\endgroup$
    – mathreadler
    Jul 14 '18 at 21:17
  • 1
    $\begingroup$ That the 1 and 2 norms are not equivalent in other senses is very important for lots of the work on various types of regularized optimization last 10-15 years. "Total variation" (TV) was for example extremely popular in all kinds of applications 5-10 years ago because new efficient numerical methods to solve them were found. $\endgroup$
    – mathreadler
    Jul 14 '18 at 21:25
  • 1
    $\begingroup$ The 2-norm is not always better, but it does have certain nice properties. For example, $\| x \|_2$ can be interpreted geometrically as the length of the vector $x$. Also, $\|x\|_2^2 = \langle x, x \rangle$, which is a simple formula. $\endgroup$
    – littleO
    Jul 14 '18 at 21:27
  • 1
    $\begingroup$ math.stackexchange.com/questions/63238/… this may be useful in terms of optimization $\endgroup$
    – qwr
    Jul 14 '18 at 22:30
7
$\begingroup$

In your use case, the actual norm of the vector does not matter since you are only concerned about the dominant eigenvalue. The only reason to normalize during the iteration is to keep the numbers from growing exponentially. You scale the vector however you want to prevent numeric overflow.

A key concept about eigenvectors and eigenvalues is that the set of vectors corresponding to an eigenvalue form a linear subspace. This is a consequence of multiplication by a matrix being a linear map. In particular, any scalar multiple of an eigenvector is also an eigenvector for the same eigenvalue.

The Wikipedia article Power method mentions the use of the Rayleigh quotient to compute an approximation to the dominant eigenvalue. For real vectors and matrices it is given by the value $\, (v\cdot Av)/(v \cdot v). \,$ There are probably good reasons for the use of this formula. Of course, if $\,v\,$ is normalized so that $\, v \cdot v = 1, \,$ then you can simplify that to $\, v\cdot Av. \,$

$\endgroup$
6
  • $\begingroup$ So is this not true in general i guess. But i think if you can use the 1-norm then it is better to compute $\endgroup$
    – Paul
    Jul 14 '18 at 21:27
  • $\begingroup$ Depends on what you mean by "in general". $\endgroup$
    – Somos
    Jul 14 '18 at 21:29
  • $\begingroup$ I mean: there exist an algorithm that uses vector normalizations, for that the 2 norm produces different results than the 1 norm. ? $\endgroup$
    – Paul
    Jul 14 '18 at 21:41
  • $\begingroup$ For this particular problem, the dominant eigenvalue is the same no matter how you iterate. Try variations and find out for yourself. $\endgroup$
    – Somos
    Jul 14 '18 at 22:33
  • $\begingroup$ I tried using the 1norm and i get different results, the power method now does not converges against the dominat eigenvalue anymore $\endgroup$
    – Paul
    Jul 15 '18 at 11:59
4
$\begingroup$

In the eigenvalue algorithms, you're attempting to generate the eigenvalues and the orthogonal eigenvectors. The step right there is the normalization part. If you look at this. enter image description here

the next step doesn't work with the $\ell_{1}$ norm. Or the actual purpose of it doesn't. The entire purpose here was to make that normalized. If you realize how these algorithms work if the eigenvalues are closer together it makes them take a lot longer. So numeric error will destroy the algorithm.

$\endgroup$
2
  • $\begingroup$ This contradicts with the answer of somos !? $\endgroup$
    – Paul
    Jul 15 '18 at 11:54
  • $\begingroup$ You are right, the power method now converges to a value that is definitively not the dominat eigenvalue. $\endgroup$
    – Paul
    Jul 15 '18 at 12:05
4
$\begingroup$

Tell me which of these looks more like a ball, and I'll tell you which one is the better norm:

$$ \ $$

                                                        enter image description here

More seriously, the two-norm is given by an inner product, and this has far reaching consequences: like orthogonality, projections, complemented subspaces, orthonormal bases, etc., etc., etc., features that we see in Hilbert spaces.

$\endgroup$
3
  • 2
    $\begingroup$ So you are sayung „looks like a ball“ = good? $\endgroup$
    – Paul
    Jul 15 '18 at 11:53
  • 1
    $\begingroup$ Hello Martin, could you add an explanation why "looks like a ball" qualifies as the main criterion for choosing the better norm? $\endgroup$
    – Orphevs
    Jul 15 '18 at 12:38
  • $\begingroup$ I have added a small explanation. $\endgroup$
    – Martin Argerami
    Jul 19 '18 at 2:27

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.