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.
Best Answer
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.