3
$\begingroup$

I have a basic question about the metric spaces. There are several metric spaces like $L_1$, $L_2$ to $L_\infty$. The $L_p$ metric is defined by the following equation:

$$d_p(x,y)=\left(\sum_{i=1}^{n}|x_i-y_i|^p \right)^{1/p}$$

Now, when $p = \infty$, then the equation of the matrix is following:

$$d_{\infty}(x,y)=\max_{i=1,2,\ldots, n}|x_i-y_i|$$

Now, I am taking the value of $x$ as $x = [1,2,3]^T$ (Transpose) and compute $L_p$ metric for, $p = 1,2$ and $\infty$.

My question is, why $L_\infty$ metric choose the maximum value.

$\endgroup$
  • 1
    $\begingroup$ i wish you would use $\LaTeX$ so i could copy your equation to save time in answering. please learn the tools. $\endgroup$ – robert bristow-johnson Mar 3 '16 at 2:53
  • $\begingroup$ I assume you have to go through a mathematical proof of this to fully understand it. Please do not make the mistake and try to explain this result by setting p to higher and higher values - this is an intuitive and often very useful thing to do, but it needs not give you the correct result. $\endgroup$ – M529 Mar 3 '16 at 9:18
  • 1
    $\begingroup$ Shouldn't this migrate to math.SE? $\endgroup$ – Carl Witthoft Mar 3 '16 at 13:07
  • 2
    $\begingroup$ No need for migration, the answer is already on math.SE: math.stackexchange.com/questions/109615/… $\endgroup$ – Jazzmaniac Mar 3 '16 at 14:19
7
$\begingroup$

In the general case, let $x = (x_1,\dots,x_n)$ be a finite-length vector (in a finite dimensional space). The finite sequence of absolute values $|x_i|$ does attain its maximum (because the sequence is finite), denoted $M = \max_i |x_i|$.

Let $m$ be the (exact) number of coordinates in $x = (x_1,\dots,x_n)$ whose absolute value is equal to $M$. Thus, $1\le m\le n$. Then, we can lower and upper bound the $\ell_p$ norm of $x$ as follows: $$(mM^p)^{\frac{1}{p}}\le\ell_p(x)\le (nM^p)^{\frac{1}{p}}\,.$$

Both $m^\frac{1}{p}$ and $n^\frac{1}{p}$ tend to $1$ as $p\to\infty$, thus $\ell_p(x) \to M$, by the squeeze theorem.

[EDIT] To provide more concrete substance, let us see what happen with your example: $x=[1,2,3]^T$ (the transposition does not change the result): $$\|x\|_p = d_p(x,0) = (1^p+2^p+3^p)^{1/p} = 3\times\left(\left(\frac{1}{3}\right)^p+\left(\frac{2}{3}\right)^p+1\right)^{1/p}\,.$$

Both $\left(\frac{1}{3}\right)^p$ and $\left(\frac{2}{3}\right)^p$ tend to $0$ as $p \to \infty$. Thus, $\|x\|_p \to 3$.

$\endgroup$
  • 1
    $\begingroup$ That's the stuff! :) $\endgroup$ – Jazzmaniac Mar 3 '16 at 16:53
1
$\begingroup$

The $L_p$ norm is

$$ d_p(\mathbf{x}, \mathbf{y}) \triangleq \left( \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}} $$

there exists a positive value that is the maximum value:

$$ M \triangleq \max_{1 \le i \le n} |x_i - y_i| $$

now, suppose you divide both sides of the $L_p$ norm definition by that positive value,

$$ \frac{d_p(\mathbf{x}, \mathbf{y})}{M} = \frac{1}{M} \left( \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}} $$

$$ \begin{align} \frac{d_p(\mathbf{x}, \mathbf{y})}{M} & = \frac{1}{M} \left( \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}} \\ & = \left( \frac{1}{M^p} \right)^{\frac{1}{p}} \left( \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}} \\ & = \left( \frac{1}{M^p} \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}} \\ & = \left( \sum\limits_{i=1}^{n} \frac{1}{M^p} |x_i - y_i|^p \right)^{\frac{1}{p}} \\ & = \left( \sum\limits_{i=1}^{n} \left( \frac{|x_i - y_i|}{M} \right)^p \right)^{\frac{1}{p}} \\ \end{align} $$

now ask yourself, what will happen to the right-hand side of this equation as $p \to \infty$? all terms, except for the term that is equal to the maximum, will have value of less than 1. they will go to 0 as $p \to \infty$, but the term that has $|x_i - y_i| = M$, that term is equal to 1 and will remain 1 even as $p \to \infty$.

$\endgroup$
  • $\begingroup$ Robert, what if there are two terms in the sum that are equal to $M$? Shouldn't the sum be equal to 2 in that case? $\endgroup$ – MBaz Mar 3 '16 at 3:48
  • $\begingroup$ hi Robert, thanks. It's a very good answer. So, Suppose, I have two matrix: x = [1,2,3]T and Y = 0. And, I want to compute, L1, L2 and L-infinity. So, here, Max value (M according to your explanation) would be 3? Right? Just to make sure. Thanks. $\endgroup$ – Odrisso Mar 3 '16 at 4:11
  • $\begingroup$ This is a very nice and intuitive explaination. However, I suppose it is not 100% mathematically sound, which is why @MBaz asked the question with the factor of 2, if your vector had two entries corresponding to M. I think the problem stems from not obeying the limit from the start on. Getting the factor 1/M into the brackets of the sum is critical and probably the point where it fails when p goes to infinity. $\endgroup$ – M529 Mar 3 '16 at 9:14
  • $\begingroup$ You could maybe argue that the sum s is bounded between 1 and n. Hence you have lim p->inf s^(1/p) which is 1. $\endgroup$ – M529 Mar 3 '16 at 9:25
  • 1
    $\begingroup$ @David, it doesn't matter if it's trivial. If you make false assumptions about the nature of something and don't explicitly consider the case that these assumptions fail, your argument is wrong. Yes, mathematics is pedantic. That's why it's so useful. $\endgroup$ – Jazzmaniac Mar 4 '16 at 19:05

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.