Limit of the $r$-norm $(\sum_{i=0}^n (y_1,x_i)-(y_2,x_i))^r )^{1/r}$ as $r \to \infty$ is $ \max_i \left|(y_1,x_i)-(y_2,x_i)\right| $

Question

In a book I was reading about data mining they wrote $$ \lim_{r \to \infty} \left(\sum_{i=0}^n (y_1,x_i)-(y_2,x_i))^r \right)^{1/r} $$ is equal to $$ \max_{ i=1,2,...,n} \left|(y_1,x_i)-(y_2,x_i)\right| $$ This is of course logical since the biggest outcome will dominate the equation but I wonder how did they prove it? Thank you a lot

Answer 1

Essentially we are considering a list of numbers $a_i$ and the $L_{\infty}$ norm: $$ L_{\infty} = \lim_{r \to \infty} \left[ \sum_{i} a_i^r \right]^{1/r} $$ Some entries in $a_i$ are smaller and some are larger. When you put all the entries to a large power (for example $r=100$), the differences become even more pronounced. Values that are close to $1$ remain close to $1$, but larger values get pushed towards infinity. So when you sum these up, the sum is basically only the sum of the large numbers, because a very large number plus a very small number is approximately equal to the large number. And remember that pushing the exponent up makes these differences even more pronounced.

Therefore, it's relatively intuitive that the value in the end turns out to be just the maximum absolute value in the list $$ L_{\infty} = \lim_{r \to \infty} \left[ \sum_{i} a_i^r \right]^{1/r} = \max_i \left| a_i \right| $$ As an example, let's take $$ a = [0.2, 1.5, 2, 7, 25] \qquad \text{and} \qquad r = 10 $$ then $$ a^r \approx [1.024 \times 10^{-7} ,\quad 57.6, \quad 1024 282\times 10^6,\quad 95\times 10^{12}] $$ The first entries pale in comparison to the last one, and the sum is $$ \sum a_i^r \approx 9.5368 \times 10^{13} \Rightarrow \sqrt[10]{\sum a_i^r} \approx 25 $$ which is the maximum of the values.

This was not a rigorous proof, but surely you'll understand the intuition.