What is Norm ?

A norm is a function that assigns a strictly positive length or size to each vector in a vector space—except for the zero vector, which is assigned a length of zero.

p-Norm or Lp Norm

Let p ≥ 1 be a real number. The p-norm (also called Lp-Norm) x = (x1,x2, , xn) is,

\[||X||_{p} \ :=\ \left(\sum ^{n}_{i=1} |x_{i} |^{p}\right)^{\frac{1}{p}} \\]

When p=1, it is called Taxi-cab norm, L1 norm.

What is Norm2 or Euclidean Norm?

On an n-dimensional Euclidean space Rn, the intuitive notion of length of the vector x = (x1,x2, , xn) is captured by the formula

||x||2:=x21+x22++x2n 

The Euclidean norm is also called the Euclidean length, L2 distance, L2 norm.

What is Overflow and Underflow condition ?

Now, there is a largest (in magnitude) number that can be stored and a smallest (in magnitude) number not equal to zero, that can be stored. Storing number larger than the magnitude will cause the memory to Overflow and often it is stored as “Not-A-Number” or “NAN”. Now if we try to store a number lower than magnitude but great than zero that situation will result Underflow and it is often set to Zero.

Let us focus on Overflow. The problem for computing the length (2-norm) of a vector is that equals the square root of the sum of the squared component. While the answer may not cause an overflow, but intermediate results when squaring components could. The same thing holds true for p-Norm

How can we solve the problem during numerical computation ?

||x||p  :=  pxp1 + xp2 ++ xpn 

we can also write as,

\[\displaystyle ||x||_{p} \ :=\sqrt[p]{\sum ^{n-1}_{i=0} \chi ^{p}_{i}} \\]

The solution is to exploit the above equation:

||x||p :=pn1i=0χpi

pn1i=0 [αp (χiα)p]

pαp n1i=0 [(χiα)p]

α pn1i=0 [(χiα)p]

where,

α=n1maxi=0 |χi| ; α>0 

Taking the example of 2-Norm / Euclidean Norm,

||x||2:=x21+x22++x2n 

we can also write as,

x2 :=n1i=0χ2i

Similarly as above:

||x||2:=n1i=0χ2i

n1i=0 [α2 (χiα)2]

α2 n1i=0 [(χiα)2]

αn1i=0 [(χiα)2]

α(xα)T(xα)  , this is the added step which is equivalent as the previous equation.

where,

α=n1maxi=0 |χi| ; α>0 

Note that there is no overflow for intermediate results (when squaring) will happen because all the elements are of magnitude less than or equal to one.

How to Handle p-Norm Overflow ?

Global Variables:

x = [] # Define the Vector
p = 1  # Define p >=1, for the p-Norm

Traditional Method which have a problem for Overflow while computing p-Norm:

temp = []
for i in x:
    temp.append(i**p)
total = sum(temp)
sol2 = (total)**(1/p)
print(sol2)

Proposed Solution to eliminate Overflow while computing p-Norm:

alpha = max(x)

temp = []
for i in x:
    temp.append((i/alpha)**(p))
total = sum(temp)

root = (total)**(1/p)
sol1 = root*alpha
print(sol1)

References

  1. https://www3.ntu.edu.sg/home/ehchua/programming/java/datarepresentation.html
  2. https://en.wikipedia.org/wiki/Euclidean_distance