1
$\begingroup$

I frequently see this statement about any matrix, $A$:

$\|A\|_2 \le k \,\,$ IFF $A^TA \le k^2 I$

where

  • $\|A\|_2$ is the L2 norm (or the "spectral norm", or the largest singular value) of A. not to be confused with the euclidean norm of a matrix, because that is different.

  • $k \in \mathbb{R_+}$

  • $\le$ is a matrix inequality that implies an inequality over the cone $S^n_+$

I do not undastand it.

The following is what I know:

  • The matrix $A^TA$ is PSD, which I think should help me in some way (e.g. the eigenvalues are all positive).
  • $\lambda_i = \sigma_i^2$ for all nonzero singular values, where $\lambda_i$ is an eigenvalue of $A$
$\endgroup$
1
$\begingroup$

Here's the "only if" part:

For $A\in\mathbb{R}^{m\times n}$, we have that $\|A\|_{2}\le k$, which means that for any $x\in\mathbb{R}^{n}$,

\begin{align} \|Ax\|_{2}^{2}&\le k^{2}\|x\|_{2}^{2}\\ \implies x^{\top}A^{\top}Ax&\le k^{2}x^{\top}x\\ \implies x^{\top}(A^{\top}A-k^{2}I)x&\le 0. \end{align}

Since $x$ was arbitrary, this means that $A^{\top}A-k^{2}I\preceq 0$, or, $A^{\top}A\preceq k^{2}I$.

The other direction is similar.

$\endgroup$
  • $\begingroup$ I do not follow how you got the second step, unless you are making the claim that $x^TA^TAx \le ||Ax||^2_2$. Is that the claim that you're making? $\endgroup$ – jaja Sep 27 '17 at 1:05
  • 1
    $\begingroup$ $\|Ax\|_{2}^{2}=\langle Ax,Ax\rangle=x^{\top}A^{\top}Ax$ $\endgroup$ – nemo Sep 27 '17 at 3:07
  • $\begingroup$ i see and is it also true that $||Ax||^2_2 = ||A||^2_2 ||x||^2_2 \,\,$ ? You seem to be using that equality in the first step. Sorry if this is basic stuff. i need to know these things. $\endgroup$ – jaja Sep 28 '17 at 15:54
  • $\begingroup$ I understand for induced norms $||Ax||_2 \le ||A||_2 ||x||_2 \,\,$, by the compatibility and consistency property of the L2 norm, but I don't understand how they can be equal here $\endgroup$ – jaja Sep 28 '17 at 16:00
  • 1
    $\begingroup$ If $\|A\|_{2}$ denotes the operator norm, then for any $x$, $\|Ax\|_{2}\le\|A\|_{2}\|x\|_{2}$ by definition (which is what you note above). And since $\|A\|_{2}\le k$, we get $\|Ax\|_{2}\le k\|x\|_{2}$. Squaring both sides gives the first step. $\endgroup$ – nemo Sep 28 '17 at 18:08

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.