35
$\begingroup$

How can one prove that $ \|A\|_2 \le \|A\|_F $ without using $ \|A\|_2^2 := \lambda_{\max}(A^TA) $?


It makes sense that the $2$-norm would be less than or equal to the Frobenius norm but I don't know how to prove it. I do know:

$$\|A\|_2 = \max_{\|x\|_2 = 1} {\|Ax\|_2}$$

and I know I can define the Frobenius norm to be:

$$\|A\|_F^2 = \sum_{j=1}^n {\|Ae_j\|_2^2}$$ but I don't see how this could help. I don't know how else to compare the two norms though.

$\endgroup$
4
  • $\begingroup$ Let $\Vert A\|_2 = \|Av\|$ for some $v$ with $\|v\| = 1$. Define an orthogonal matrix $U$ for which $v$ is the first column. Compute $\Vert AU\Vert_F $ and show that it is equal to $\Vert A\Vert_F $, then compare it to $\Vert Av\Vert$ by a direct computation. $\endgroup$ Dec 7, 2012 at 4:36
  • $\begingroup$ @HansEngler I dont exactly understand your answer. How would I compute $||AU||_2$ and if it is equal to $||A||_2$ then how does that prove anything about $||A||_F$? $\endgroup$
    – user972276
    Dec 7, 2012 at 4:42
  • $\begingroup$ @HansEngler I dont understand how to show $||AU||_F = ||A||_F$. I understand that the first column of AU is just Av and so I can show that $||A||_2 \le ||A||_F$. $\endgroup$
    – user972276
    Dec 7, 2012 at 4:50
  • $\begingroup$ $\Vert A\Vert_F^2 = trace(AA^T)$. Now compute the same thing for $AU$ and use the fact that $U$ is orthogonal. $\endgroup$ Dec 7, 2012 at 12:14

8 Answers 8

41
$\begingroup$

Write $x=\sum_{j=1}^nc_je_j$, for coefficients $c_1,\ldots,c_n$. Suppose that $\|x\|_2=1$, i.e. $\sum_j |c_j|^2=1$. Then \begin{align} \|Ax\|_2^2&=\left\|\sum_j c_j\,Ae_j\right\|_2^2\leq\left(\sum_j|c_j|\,\|Ae_j\|_2\right)^{2}\\ \ \\ &\leq\left(\sum_j|c_j|^2\right)\sum_j\|Ae_j\|_2^2=\sum_j\|Ae_j\|_2^2=\|A\|_F^2, \end{align} where the triangle inequality is used in the first $\leq$ and Cauchy-Schwarz in the second.

As $x$ was arbitrary, we get $\|A\|_2\leq\|A\|_F$.

$\endgroup$
2
  • $\begingroup$ is there a way to do it without using Cauchy-Schwartz? $\endgroup$
    – user972276
    Dec 7, 2012 at 4:54
  • $\begingroup$ Not that I can think of. In any case I simplified the argument by using the triangle inequality (basically, the previous version had a built-in proof of the triangle inequality, which by the way I don't think you can prove without CS). $\endgroup$ Dec 7, 2012 at 10:58
24
$\begingroup$

In fact, the proof from $\left\| \mathbf{A}\right\|_2 =\max_{\left\| \mathbf{x}\right\|_2=1} \left\| \mathbf{Ax} \right\|_2$ to $\left\| \mathbf{A}\right\|_2 = \sqrt{\lambda_{\max}(\mathbf{A}^H \mathbf{A})}$ is straight forward. We can first simply prove when $\mathbf{P}$ is Hermitian $$ \lambda_{\max} = \max_{\| \mathbf{x} \|_2=1} \mathbf{x}^H \mathbf{Px}. $$ That's because when $\mathbf{P}$ is Hermitian, there exists one and only one unitary matrix $\mathbf{U}$ that can diagonalize $\mathbf{P}$ as $\mathbf{U}^H \mathbf{PU}=\mathbf{D}$ (so $\mathbf{P}=\mathbf{UDU}^H$), where $\mathbf{D}$ is a diagonal matrix with eigenvalues of $\mathbf{P}$ on the diagonal, and the columns of $\mathbf{U}$ are the corresponding eigenvectors. Let $\mathbf{y}=\mathbf{U}^H \mathbf{x}$ and substitute $\mathbf{x} = \mathbf{Uy}$ to the optimization problem, we obtain

$$ \max_{\| \mathbf{x} \|_2=1} \mathbf{x}^H \mathbf{Px} = \max_{\| \mathbf{y} \|_2=1} \mathbf{y}^H \mathbf{Dy} = \max_{\| \mathbf{y} \|_2=1} \sum_{i=1}^n \lambda_i |y_i|^2 \le \lambda_{\max} \max_{\| \mathbf{y} \|_2=1} \sum_{i=1}^n |y_i|^2 = \lambda_{\max} $$

Thus, just by choosing $\mathbf{x}$ as the corresponding eigenvector to the eigenvalue $\lambda_{\max}$, $\max_{\| \mathbf{x} \|_2=1} \mathbf{x}^H \mathbf{Px} = \lambda_{\max}$. This proves $\left\| \mathbf{A}\right\|_2 = \sqrt{\lambda_{\max}(\mathbf{A}^H \mathbf{A})}$.

And then, because the $n\times n$ matrix $\mathbf{A}^H \mathbf{A}$ is positive semidefinite, all of its eigenvalues are not less than zero. Assume $\text{rank}~\mathbf{A}^H \mathbf{A}=r$, we can put the eigenvalues into a decrease order:

$$ \lambda_1 \geq \lambda_2 \geq \lambda_r > \lambda_{r+1} = \cdots = \lambda_n = 0. $$

Because for all $\mathbf{X}\in \mathbb{C}^{n\times n}$, $$ \text{trace}~\mathbf{X} = \sum\limits_{i=1}^{n} \lambda_i, $$ where $\lambda_i$, $i=1,2,\ldots,n$ are eigenvalues of $\mathbf{X}$; and besides, it's easy to verify $$ \left\| \mathbf{A}\right\|_F = \sqrt{\text{trace}~ \mathbf{A}^H \mathbf{A}}. $$

Thus, through $$ \sqrt{\lambda_1} \leq \sqrt{\sum_{i=1}^{n} \lambda_i} \leq \sqrt{r \cdot \lambda_1} $$ we have $$ \left\| \mathbf{A}\right\|_2 \leq \left\| \mathbf{A}\right\|_F \leq \sqrt{r} \left\| \mathbf{A}\right\|_2 $$

$\endgroup$
0
13
$\begingroup$

The Frobenius norm is sub-multiplicative, therefore $||Ax||_F \leq ||A||_F ||x||_F$, which gives:

$$\forall x \neq 0 \quad \frac{ ||Ax||_2 } {||x||_2} = \frac{ ||Ax||_F } {||x||_F} \leq ||A||_F $$

So you have an upper bound for the quotient, and since the supremum (here maximum) is by definition smaller than any other upper bound, you immediately get:

$$ \underset{x \neq 0}{\max}{\frac{||Ax||}{||x||}} =||A||_2 \leq ||A||_F $$

$\endgroup$
7
$\begingroup$

Use the following two facts/properties:

  1. The Frobenius norm and the 2-norm coincide for vectors: $\|u\|_2 = \|u\|_{F}$.
  2. The Frobenius norm is submultiplicative: $\|AB\|_{F} \leq \|A\|_{F}\|B\|_{F}$ for any compatible matrices $A$,$B$ (in particular when, $B$ is a vector).

The proof then goes like this: $$ \begin{align*} \|A\|_{2} &= \sup_{\|u\|_{2}=1}\|Au\|_{2} \quad \text{(Definition of 2-norm)}\\&= \sup_{\|u\|_{2}=1}\|Au\|_{F} \quad \text{(Property 1)} \\&\leq \sup_{\|u\|_{2}=1}\|A\|_{F}\|u\|_{F} \quad \text{(Property 2)}\\&= \sup_{\|u\|_{2}=1}\|A\|_{F}\|u\|_{2} \quad \text{(Property 1)}\\&= \|A\|_{F}\sup_{\|u\|_{2}=1}\|u\|_{2} \\&= \|A\|_{F}. \end{align*} $$

$\endgroup$
2
$\begingroup$

The OP defines $\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2$. Let $x$ be a maximiser of $\|Ax\|_2$ on the unit sphere. By completing $\{x\}$ to an orthonormal basis of $\mathbb R^n$, we can obtain an orthogonal matrix $Q$ whose first column is $x$. Therefore $\|Ax\|_2=\|AQe_1\|_2=\|Q^TAQe_1\|_2\le\|Q^TAQ\|_F=\|A\|_F$, where $e_1=(1,0,\ldots,0)^T$.

$\endgroup$
2
$\begingroup$

Lemma. If $x$ is a vector in $\mathbb R^n$ with at most $r$ nonzero coordinates, then $$ \|x\|_\infty \le \|x\|_2 \le \sqrt{r}\|x\|_\infty, $$ where $\|x\|_p := \begin{cases}(\sum_{i=1}^n|x_i|^p)^{1/p},&\mbox{ if }1 \le p < \infty,\\\max_{i=1}^n|x_i|,&\mbox{ else.}\end{cases}$

Proof. Google "equivalence of Lp norms" (e.g https://math.stackexchange.com/a/218129/168758). $\quad\quad\Box$

Now, apply this to the vector of singular values $\sigma := (\sigma_1,\ldots,\sigma_n)$ of $A$, noting that $\|A\|_2 := \|\sigma\|_\infty$ and $\|A\|_F := \|\sigma\|_2$.

$\endgroup$
1
$\begingroup$

We will denote a normalized vector (i.e. $\frac{\vec{v}}{|\vec{v}|}$) by $\vec{v^*}$. ($|\vec{v}|\vec{v^*}={\vec{v}}$)

We will write the rows of $A$ as transposes of the vectors $a_1,\cdots,a_n$. Since the $i$th row of $A$ is $\vec{a_i}^\top$, the $i$th entry $(A\vec{x})_i$ of $A\vec{x}$ is $\vec{a_i} \cdot \vec{x}$.

$$ ||A||^2= \sup |A\vec{x^*}|^2= \sup \sum_{i=1}^n(A\vec{x^*})_i^2= \sup \sum_{i=1}^n(\vec{a_i} \cdot \vec{x^*})^2 $$ $$ \le \sup \sum_{i=1}^n|\vec{a_i}|^2|\vec{x^*}|^2= \sum_{i=1}^n|\vec{a_i}|^2= |A|^2 \implies ||A|| \leq |A| $$

$\endgroup$
1
$\begingroup$

We have that :

\begin{equation} \|A\|^2_2 =\sup_{\|x\|_2=1 }\|Ax\|_2^2 = \sup_{\|x\|_2=1}\sum_{i=1}^n \|A_{i*}x\|_2^2\leq \sum_{i=1}^n\sup_{\|x\|_2=1} \|A_{i*}x\|_2^2 = \|A\|_F^2 \end{equation}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .