Calculating the norm of a vector , or a complex number means calculating . Without loss of generality, we can set . If we draw this, we get the following.
Now, the issue with the norm is that the operation is expensive to compute. That's why we would like another way to approximate the norm. A first idea is to look at other norms available, indeed, what we have called "norm" so far is actually the 2-norm, also named euclidean norm. Let's have a look at two other norms : the infinity norm and the Manhattan norm.
Infinity norm is :
Manhattan norm is :
Now we see the Manhattan norm is indeed a lower bound for the 2-norm, even if it's rough. The Infinity norm, however, is too high. But that is not an issue, we could simply scale it up so that it is always higher than the 2-norm. The scaling factor is chosen, such as the yellow curve tangent to the circle. For that, we need it to be equal to .
We have a lower bound! By choosing the closest to the circle between the yellow and green curves, we get an octagon that is very close to the circle. We can define the upper bound of the circle with a function such as:
Note that this is different from Paul's article. You do need to take the maximum value of the two norms to select the points that are closest to the center. Generally speaking, for two norms, if one's value is higher than the other, then the former will be drawn closer to the origin when plotting the curve.
To trace this function, note that Manhattan and infinity norms isolines cross when and or and .
The first idea you can get from the lower bound we found is to scale it up so that the octagon corners touch the circle.
To do so, we need to find the 2-norm of one of the corners and divide by it.
Let's take the one at , . We have:
Thus, the upper-bound for the 2-norm with the octagon method is :
Now, we could stick to Paul Hsieh's choice of taking the middle between the lower and the upper bounds, and it will probably be fine. But come on, let's see if it is the best choice. 😉
Formally, the problem is to find a number such as defined as follows is the closest possible to the norm-2.
Let's plot this function for various values of . To make things easier, I will "unroll" the circle, and plot the norms against , the angle between our vector and the axis.
As expected, we can continuously vary our approximation between the upper and lower bounds. Notice that these functions are periodic and even. We can thus focus on the first half period to minimize the error. The first half period is when the vector is at the first octagon vertices, starting from the axis and circling anti-clockwise.
To minimize the error with our approximation, we want to minimize the square error. That is:
Thankfully, the expression of and thus of should simplify a lot on the given interval. You can see on schematic above that on this interval we have, . We can thus rewrite as follows.
Where and .
As we can see from these plots, there is a minimal error, and though 0.5 is a reasonable choice for , we can do slightly better around 0.3.
We can explicitly calculate . Let . We have
Where . Thus, we look for the position of the minimum, that is where .
Not that far from 0.3!
The maximum deviation from the result is then . Looking for that maximum is like looking for the maximum of . Long story short, the maxima can only occur on the boundaries of the allowed domain for , that is or , meaning
With our choice for , we get , so the maximum deviation is 0.052. That is, we have at most a 5.3% deviation from the norm-2!
That was a fun Sunday project! Originally this was intended to be included in a longer blog-post that is yet to be finished, but I figured it was interesting enough to have its own post. The take-home message being, you can approximate the Euclidean norm of a vector with:
You'll get at most a 5.3% error. This is a bit different from what's proposed on Paul Hsieh's blog-post. Unless I made a mistake, there might be a typo on his blog!
If you are interested in playing with the code used to generate the figures in this article, have a look at the companion notebook!
As always, if you have any question, or want to add something to this post, you can leave me comment or ping me on Twitter or Mastodon.