2
$\begingroup$

Let $A \in \mathbb{R}^{n \times m}$ and $x \in \mathbb{R}^n$. Prove the following inequality. $\left\lVert \cdot \right\rVert_F$ denotes the Frobenius norm and $\left\lVert \cdot \right\rVert_2$ denotes the $p$-norm with $p=2$.

$$\left\lVert Ax \right\rVert_2 \leq \left\lVert A \right\rVert_F \left\lVert x \right\rVert_2$$


tl;dr: I'm essentially stuck at this (or similar) inequality:

$$ \lambda_{max} (A^T \cdot A) \leq \left\lVert A^T \cdot A \right\rVert_F$$

while $\lambda_{max}$ is the largest eigenvalue of $A^T \cdot A$. I know that this inequality holds if the norm was a natural norm, but since frobenius norm isn't induced by a vector norm, I'm not sure how to proceed.


How I got to this point:

$$\left\lVert Ax \right\rVert_2 \leq \left\lVert A \right\rVert_2 \left\lVert x \right\rVert_2$$

So we have to show:

$$\left\lVert A \right\rVert_2 \leq \left\lVert A \right\rVert_F$$

or

$$\left\lVert A \right\rVert_2^2 \leq \left\lVert A \right\rVert_F^{2}$$

We have:

$$\left\lVert A \right\rVert_2^2 = \lambda_{max}(A^TA) \leq \left\lVert A^T A \right\rVert_F$$

The last inequality is the part I can't prove. If I could show it, we have:

$$\left\lVert A^T A \right\rVert_F \leq \left\lVert A^T \right\rVert_F \left\lVert A \right\rVert_F = \left\lVert A \right\rVert_F^2$$

Which was the thing we wanted to show above.


These threads were helpful:

Show that $ \lVert A \rVert_2^2 \leq \lVert A \rVert _1 \lVert A \rVert _ \infty $

The spectral radius of the matrix $A$ is less than or equal any natural norm

Anyways, thank you for your help. It is greatly appreciated.

$\endgroup$
3
$\begingroup$

Recall that the Frobenius norm is also the Schatten $2$-norm, and thus has a characterization in terms of $2$-norm of the singular values.

Letting $B = A^T A$, $$ \lVert B\rVert_F = \sqrt{\operatorname{Tr} B^T B} = \sqrt{\sum_{i=1}^n \lambda_i(B)^2} \geq \sqrt{(\max_{1\leq i\leq n}\lambda_i(B) )^2} = \max_{1\leq i\leq n}\lambda_i(B) $$ where $(\lambda_i(B))_{1\leq i\leq n}$ are the (real) eigenvalues of the symmetric matrix $B$. This shows $$ \lVert A^TA \rVert_F \geq \lambda_\max(A^TA) $$ as desired.

$\endgroup$
  • 1
    $\begingroup$ (Essentially, it's an $\ell_2$ vs. $\ell_\infty$ inequality on the vector of singular values of $A$.) $\endgroup$ – Clement C. Oct 22 '18 at 0:31
1
$\begingroup$

Here's another way: First prove the following

Lemma For two matrices $A,B$ we have $\| A B \|_F \le \| A \|_F \| B \|_F$.

Let $( A B )_{i,j} := (c_{i,j})_{i,j}$ Then we have \begin{align*} \| A B \|_F^2 & \overset{\text{Def}}{=} \sum_{i,j = 1}^{n} | c_{i,j} |^2 = \sum_{i,j = 1}^{n} | \langle a_{i, \ast}, b_{\ast,j} \rangle | \overset{\text{(CS)}}{\le} \sum_{i,j = 1}^{n} \| a_{i, \ast} \|_2^2 \cdot \| b_{\ast,j} \|_2^2 \\ & = \sum_{i,j = 1}^{n} \| a_{i, \ast} \|_2^2 \cdot \sum_{i,j = 1}^{n} \| b_{\ast,j} \|_2^2 = \| A \|_F^2 \cdot \| B \|_F^2, \end{align*} where (CS) means the Cauchy-Schwarz inequality. Now, since the function $x \mapsto \sqrt{x}$ is strictly increasing and monotone, you can take the square root from both sides and the inequality (since it's $\le$ and not $<$ will be preserved).


Now, we can prove $\| A x \|_2 \le \| A \|_F \| x \|_2$.

Using the lemma and putting $B = x$ we have $\| x \|_F = \| x \|_2$ (since the vector $x$ has, viewed as Matrix, rank 1). Therefore, we have \begin{align*} \| A x \|_{2} = \| Ax \|_F \overset{\text{(L)}}{\le} \| A \|_F \| x \|_F = \| A \|_F \| x \|_2, \end{align*} where (L) is the inequality from the lemma.

$\endgroup$

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.