ALAFF Equivalence of vector norms

Subsection 1.2.6 Equivalence of vector norms

Homework 1.2.6.1.

Fill out the following table:

\begin{equation*} \begin{array}{| c | c | c | c |} \hline x \amp \| x \|_1 \amp \| x \|_\infty \amp \| x \|_2 \\ \hline \left( \begin{array}{r} 1 \\ 0 \\ 0 \end{array} \right) \amp \amp \amp \\ \hline \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \amp \amp \amp \\ \hline \left( \begin{array}{r} 1 \\ -2 \\ -1 \end{array} \right) \amp \amp \amp \\ \hline \end{array} \end{equation*}

Solution

\begin{equation*} \begin{array}{| c | c | c | c |} \hline x \amp \| x \|_1 \amp \| x \|_\infty \amp \| x \|_2 \\ \hline \left( \begin{array}{r} 1 \\ 0 \\ 0 \end{array} \right) \amp 1 \amp 1 \amp 1 \\ \hline \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) \amp 3 \amp 1 \amp \sqrt{3} \\ \hline \left( \begin{array}{r} 1 \\ -2 \\ -1 \end{array} \right) \amp 4 \amp 2 \amp \sqrt{1^2 + (-2)^2 + (-1)^2 } = \sqrt{6} \\ \hline \end{array} \end{equation*}

In this course, norms are going to be used to reason that vectors are "small" or "large". It would be unfortunate if a vector were small in one norm yet large in another norm. Fortunately, the following theorem excludes this possibility:

Theorem 1.2.6.1. Equivalence of vector norms.

Let \(\| \cdot \|: \C^m \rightarrow \mathbb R \) and \(\vert \vert \vert \cdot \vert \vert \vert: \C^m \rightarrow \mathbb R \) both be vector norms. Then there exist positive scalars \(\sigma \) and \(\tau \) such that for all \(x \in \Cm \)

\begin{equation*} \sigma \| x \| \leq \vert \vert \vert x \vert \vert \vert \leq \tau \| x \|. \end{equation*}

Proof.

The proof depends on a result from real analysis (sometimes called "advanced calculus") that states that \(\sup_{x \in S} f( x ) \) is attained for some vector \(x \in S \) as long as \(f \) is continuous and \(S \) is a compact (closed and bounded) set. For any norm \(\| \cdot \| \text{,}\) the unit ball \(\| x \| = 1 \) is a compact set. When a supremum is an element in \(S \text{,}\) it is called the maximum instead and \(\sup_{x \in S} f( x ) \) can be restated as \(\max_{x \in S} f( x ) \text{.}\)

Those who have not studied real analysis (which is not a prerequisite for this course) have to take this on faith. It is a result that we will use a few times in our discussion.

We prove that there exists a \(\tau \) such that for all \(x \in \C^m \)

\begin{equation*} \vert \vert \vert x \vert \vert \vert \leq \tau \| x \|, \end{equation*}

leaving the rest of the proof as an exercise.

Let \(x \in \C^m \) be an arbitary vector. W.l.o.g. assume that \(x \neq 0 \text{.}\) Then

\begin{equation*} \begin{array}{l} \vert \vert \vert x \vert \vert \vert \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ \frac{\vert \vert \vert x \vert \vert \vert}{\| x \|} \| x \| \\ ~~~ \le ~~~~ \lt \mbox{ algebra} \gt \\ \left( \sup_{z \neq 0} \frac{ \vert \vert \vert z \vert \vert \vert} {\| z \|} \right) \| x \| \\ ~~~ = ~~~~ \lt \mbox{ change of variables: } y = z / \| z \| \gt \\ \left( \sup_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert \right) \| x \| \\ ~~~ = ~~~~ \lt \mbox{ the set }\| y \| = 1 \mbox{ is compact } \gt \\ \left( \max_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert\right) \| x \| \end{array} \end{equation*}

The desired \(\tau \) can now be chosen to equal \(\max_{\| y \| = 1} \vert \vert \vert y \vert \vert \vert \text{.}\)

Homework 1.2.6.2.

Complete the proof of Theorem 1.2.6.1.

Solution

We need to prove that

\begin{equation*} \sigma \| x \| \leq \vert\vert\vert x \vert \vert \vert. \end{equation*}

From the first part of the proof of Theorem 1.2.6.1, we know that there exists a \(\rho > 0 \) such that

\begin{equation*} \| x \| \leq \rho \vert\vert\vert x \vert \vert \vert \end{equation*}

and hence

\begin{equation*} \frac{1}{\rho} \| x \| \leq \vert\vert\vert x \vert \vert \vert . \end{equation*}

We conclude that

\begin{equation*} \sigma \| x \| \leq \vert\vert\vert x \vert \vert \vert \end{equation*}

where \(\sigma = 1 / \rho \text{.}\)

Example 1.2.6.2.

Let \(x \in \R^2 \text{.}\) Use the picture
to determine the constant \(C \) such that \(\| x \|_1 \leq C \| x \|_\infty \text{.}\) Give a vector \(x \) for which \(\| x \|_1 = C \| x \|_\infty \text{.}\)
For \(x \in \R^2 \) and the \(C \) you determined in the first part of this problem, prove that \(\| x \|_1 \leq C \| x \|_\infty \text{.}\)
Let \(x \in \Cm \text{.}\) Extrapolate from the last part the constant \(C \) such that \(\| x \|_1 \leq C \| x \|_\infty \) and then prove the inequality. Give a vector \(x \) for which \(\| x \|_1 = C \| x \|_\infty \text{.}\)

Solution

Consider the picture
- The red square represents all vectors such that \(\| x \|_\infty = 1 \) and the white square represents all vectors such that \(\| x \|_1 = 2 \text{.}\)
- All points on or outside the red square represent vectors \(y \) such that \(\| y \|_\infty \ge 1 \text{.}\) Hence if \(\| y \|_1 = 2 \) then \(\| y \|_\infty \geq 1 \text{.}\)
- Now, pick any \(z \neq 0 \text{.}\) Then \(\left\| 2 z / \| z \|_1 \right\|_1= 2) \text{.}\) Hence
  
  \begin{equation*} \left\| 2 z / \| z \|_1 \right\|_\infty \ge 1 \end{equation*}
  
  which can be rewritten as
  
  \begin{equation*} \| z \|_1 \le 2 \| z \|_\infty. \end{equation*}
  
  Thus, \(C = 2 \) works.
- Now, from the picture it is clear that \(x = \left( \begin{array}{c} 1 \\ 1 \end{array} \right) \) has the property that \(\| x \|_1 = 2 \| x \|_\infty \text{.}\) Thus, the inequality is "tight."
We now prove that \(\| x \|_1 \leq 2 \| x \|_\infty \) for \(x \in \R^2 \text{:}\)

\begin{equation*} \begin{array}{l} \| x \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ \vert \chi_0 \vert + \vert \chi_1 \vert \\ ~~~ \leq ~~~~ \lt \mbox{ algebra} \gt \\ \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) + \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ 2 \max(\vert \chi_0 \vert, \vert \chi_1 \vert ) \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ 2 \| x \|_\infty. \end{array} \end{equation*}
From the last part we extrapolate that \(\| x \|_1 \leq m \| x \|_\infty \text{.}\)

\begin{equation*} \begin{array}{l} \| x \|_1 \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~ \leq ~~~~ \lt \mbox{ algebra} \gt \\ \sum_{i=0}^{m-1} \left( \max_{j=0}^{m-1} \vert \chi_j \vert \right) \\ ~~~ = ~~~~ \lt \mbox{ algebra} \gt \\ m \max_{j=0}^{m-1} \vert \chi_j \vert \\ ~~~ = ~~~~ \lt \mbox{ definition} \gt \\ m \| x \|_\infty. \end{array} \end{equation*}

Equality holds (i.e., \(\| x \|_1 = m \| x \|_\infty \)) for \(x = \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) \text{.}\)

Some will be able to go straight for the general result, while others will want to seek inspiration from the picture and/or the specialized case where \(x \in \R^2 \text{.}\)

Homework 1.2.6.3.

Let \(x \in \Cm \text{.}\) The following table organizes the various bounds:

\begin{equation*} \begin{array}{c | c | c } \amp \| x \|_1 \leq C_{1,2} \| x \|_2 \amp {\color{black} {\| x \|_1 \leq C_{1,\infty} \| x \|_\infty}} \\ \hline \| x \|_2 \leq C_{2,1} \| x \|_1 \amp \amp \| x \|_2 \leq C_{2,\infty} \| x \|_\infty \\ \hline \| x \|_\infty \leq C_{\infty, 1} \| x \|_1 \amp \| x \|_\infty \leq C_{\infty, 2} \| x \|_2 \amp \end{array} \end{equation*}

For each, determine the constant \(C_{x,y} \) and prove the inequality, including that it is a tight inequality.

Hint: look at the hint!

Hint

\(\| x \|_1 \leq \sqrt{m} \| x \|_2 \text{:}\)

This is the hardest one to prove. Do it last and use the following hint:

Consider \(y = \left( \begin{array}{c} \chi_0 / \vert \chi_0 \vert \\ \vdots \\ \chi_{m-1} / \vert \chi_{m-1} \vert \end{array} \right) \) and employ the Cauchy-Schwarz inequality.

(How do you modify this hint to cover the case where one or more elements equal zero?)

Solution 1 \(\| x \|_1 \leq C_{1,2} \| x \|_2 \)

\(\| x \|_1 \leq \sqrt{m} \| x \|_2 \text{:}\)

Consider \(y = \left( \begin{array}{c} \psi_0 \\ \vdots \\ \psi_{m-1} \end{array} \right) = \left( \begin{array}{c} \chi_0 / \vert \chi_0 \vert \\ \vdots \\ \chi_{m-1} / \vert \chi_{m-1} \vert \end{array} \right). \) Then

\begin{equation*} \vert x^H y \vert = \left\vert \sum_{i=0}^{m-1} \overline{\chi_i} \chi_i / \vert \chi_i \vert \right\vert = \left\vert \sum_{i=0}^{m-1} \vert \chi_i \vert^2 / \vert \chi_i \vert \right\vert = \left\vert \sum_{i=0}^{m-1} \vert \chi_i \vert \right\vert = \| x \|_1. \end{equation*}

We also notice that \(\| y \|_2 = \sqrt{m} \text{.}\)

From the Cauchy-Swartz inequality we know that

\begin{equation*} \| x \|_1 = \vert x^H y \vert \leq \| x \|_2 \| y \|_2 = \sqrt{m} \| x \|_2. \end{equation*}

The problem with the above argument is that one of more \(\chi_i \) may equal zero. The argument can be fixed by choosing

\begin{equation*} \psi_i = \left\{ \begin{array}{ll} \chi_i / \vert \chi_i \vert \amp ~ \mbox{if } \chi_i \neq 0 \\ 0 \amp \mbox{otherwise} \end{array} \right. \end{equation*}

\begin{equation*} \psi_i = \left\{ \begin{array}{ll} \chi_i / \vert \chi_i \vert \amp ~ \mbox{if } \chi_i \neq 0 \\ 1 \amp \mbox{otherwise.} \end{array} \right. \end{equation*}

To demonstrate that equality is attained for at least one non-zero vector, we choose

\begin{equation*} x = \left( \begin{array}{c} 1 \\ \vdots \\ 1 \end{array} \right) \end{equation*}

then \(\| x \|_1 = m \) and \(\| x \|_2 = \sqrt{m}\) so that \(\| x \|_1 = \sqrt{m} \| x \|_2 \text{.}\)

Solution 2 \(\| x \|_1 \leq C_{1,\infty} \| x \|_\infty\)

\(\| x \|_1 \leq m \| x \|_\infty \text{:}\)

See Example 1.2.6.2.

Solution 3 \(\| x \|_2 \leq C_{2,1} \| x \|_1 \text{:}\)

\(\| x \|_2 \leq \| x \|_1 \text{:}\)

\begin{equation*} \begin{array}{l} \| x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \left( \sum_{i=0}^{m-1} \vert \chi_i \vert \right)^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_1^2. \end{array} \end{equation*}

Taking the square root of both sides yields \(\| x \|_2 \leq \| x \|_1 \text{.}\)

If we now choose

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) \end{equation*}

then \(\| x \|_2 = \| x \|_1 \text{.}\)

Solution 4 \(\| x \|_2 \leq C_{2,\infty} \| x \|_\infty \)

\(\| x \|_2 \leq \sqrt{m} \| x \|_\infty \text{:}\)

\begin{equation*} \begin{array}{l} \| x \|_2^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \left( \max_{j=0}^{m-1} \vert \chi_j \vert \right)^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \sum_{i=0}^{m-1} \| x \|_\infty^2 \\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ m \| x \|_\infty^2. \end{array} \end{equation*}

Taking the square root of both sides yields \(\| x \|_2 \leq \sqrt{m} \| x \|_\infty \text{.}\)

Consider

\begin{equation*} x = \left( \begin{array}{c} 1 \\ \vdots \\ 1 \end{array} \right) \end{equation*}

then \(\| x \|_2 = \sqrt{m} \) and \(\| x \|_\infty = 1\) so that \(\| x \|_2 = \sqrt{m} \| x \|_\infty \text{.}\)

Solution 5 \(\| x \|_\infty \leq C_{\infty,1} \| x \|_1 \text{:}\)

\(\| x \|_\infty \leq \| x \|_1 \text{:}\)

\begin{equation*} \begin{array}{l} \| x \|_\infty \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \max_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_1. \end{array} \end{equation*}

Consider

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) . \end{equation*}

Then \(\| x \|_\infty = 1 = \| x \|_1 \text{.}\)

Solution 6 \(\| x \|_\infty \leq C_{\infty,2} \| x \|_2\)

\(\| x \|_\infty \leq \| x \|_2 \text{:}\)

\begin{equation*} \begin{array}{l} \| x \|_\infty^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \left( \max_{i=0}^{m-1} \vert \chi_i \vert \right)^2\\ ~~~=~~~~ \lt \mbox{ algebra } \gt \\ \max_{i=0}^{m-1} \vert \chi_i \vert^2\\ ~~~\leq~~~~ \lt \mbox{ algebra } \gt \\ \sum_{i=0}^{m-1} \vert \chi_i \vert^2 \\ ~~~=~~~~ \lt \mbox{ definition } \gt \\ \| x \|_2^2. \end{array} \end{equation*}

Taking the square root of both sides yields \(\| x \|_\infty \leq \| x \|_2 \text{.}\)

Consider

\begin{equation*} x = \left( \begin{array}{c} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array} \right) . \end{equation*}

Then \(\| x \|_\infty = 1 = \| x \|_2 \text{.}\)

Solution 7 Table of constants

\begin{equation*} \begin{array}{c | c | c } \amp \| x \|_1 \leq \sqrt{m} \| x \|_2 \amp {\color{black} {\| x \|_1 \leq m \| x \|_\infty}} \\ \hline \| x \|_2 \leq \| x \|_1 \amp \amp \| x \|_2 \leq \sqrt{m} \| x \|_\infty \\ \hline \| x \|_\infty \leq \| x \|_1 \amp \| x \|_\infty \leq \| x \|_2 \amp \end{array} \end{equation*}

Remark 1.2.6.3.

The bottom line is that, modulo a constant factor, if a vector is "small" in one norm, it is "small" in all other norms. If it is "large" in one norm, it is "large" in all other norms.