1
$\begingroup$

Please explain what results we use to get the following:

$$\|AA^T(Ax-b)\| \leq \|A^TA\|\cdot\|(Ax-b)\|,$$

where $A$ is an $m \times n$ matrix; $b$ and $x$ are $m \times 1$ vectors, and $\|.\|$ is the $2$-norm.

  • 0
    This can't be true. Let $A=1, b=0, x=2$. Then the above inequality gives $2^2 \leq 2$, which is clearly false. I would suspect that the square on the lhs should be removed, then the result follows from the fact that $\|M\| = \|M^T\|$ (assuming the Euclidean norm, and a real matrix).2012-09-10
  • 0
    This is clearly wrong because it does not have the right scaling behaviour. It should be $\|A A^T (Ax - b)\| \le \|A^T A\| \|Ax - b\|$. $\|A^T A\|$ and $\|A A^T\|$ are equal because we're using the spectral norm and $AB$ and $BA$ always have the same nonzero eigenvalues.2012-09-10
  • 0
    thanks @RobertIsrael! Could you please explain to me why the square isn't valid? Wait.. does that mean that we're not using Cauchy Schwarz at all?2012-09-10
  • 0
    Is the inequality in your comment a trivial result? or does it derive from something? We were only introduced to matrix norms this week.. so I'm a little confused.2012-09-10
  • 0
    @copper.hat I don't think $||M|| = ||M^T||$ gives the desired result, because the order of A and $A^T$ stay the same after a transpose: i.e. $(AA^T)^T = AA^T$2012-09-10
  • 0
    @RobertIsrael how can AB and BA have the same non-zero eigenvalues if AB and BA are of different dimensions? In this example, $AA^T$ is m x m whereas $A^TA$ is n x n?2012-09-10
  • 2
    @James: Because of the "nonzero". The larger of $AB$ and $BA$ has additional eigenvalues that are all $0$.2012-09-10
  • 0
    @James: You are right, I should have written $\|AB\| = \|BA\|$. If $\lambda \neq 0$, and $AB x = \lambda x$, then multiplying by $B$ gives $BA (Bx) = \lambda (Bx)$ ($\neq 0$), hence they share the same non zero eigenvalues.2012-09-10
  • 0
    And $\|AB\|^2 = \lambda_{\max}((AB)^T AB) = \lambda_{\max}(AB (AB)^T) = \|BA\|^2$.2012-09-10
  • 0
    @James: The result follows from the fact that for an induced norm, $\|Ax\| \leq \|A\| \|x\|$.2012-09-10

1 Answers 1