Prove $\text{cond}_2(A^T A + \alpha I) \leq \text{cond}_2(A^T A)$

Question

Let $A$ be an $m \times n$ matrix, where $m > n$, and $\alpha$ a real positive constant, prove that

$$\text{cond}_2(A^T A + \alpha I) \leq \text{cond}_2(A^T A)$$

where $I$ the identiy matrix. All norms indicate 2-norms.

---

My attempt:

I know that $\text{cond}_2(A^T A) = \sigma_{\max}^2/\sigma_{\min}^2$ where $\sigma_i$ are the diagonal elements of the singular value decomposition of $A$. Next, of which I'm unsure that it's true, I tried:

$$ \begin{align} \text{cond}_2(A^T A + \alpha I) &= \left( \max \limits_{x\neq0} \frac{\Vert(A^T A + \alpha I)x \Vert}{\Vert x \Vert} \right) \cdot \left( \min \limits_{x\neq0} \frac{\Vert(A^T A + \alpha I)x \Vert}{\Vert x \Vert} \right)^{-1} \\ &= \left( \max \limits_{x\neq0} \frac{\Vert A^T A x + \alpha Ix \Vert}{\Vert x \Vert} \right) \cdot \left( \min \limits_{x\neq0} \frac{\Vert A^T A x + \alpha Ix \Vert}{\Vert x \Vert} \right)^{-1} \\ &\leq \left( \max \limits_{x\neq0} \left[ \frac{\Vert A^T A x \Vert}{\Vert x \Vert} + \frac{\Vert \alpha I x \Vert}{\Vert x \Vert} \right]\right) \cdot \left( \min \limits_{x\neq0} \left[ \frac{\Vert A^T A x \Vert}{\Vert x \Vert} + \frac{\Vert \alpha I x \Vert}{\Vert x \Vert}\right]\right)^{-1} \\ &= \left( \max \limits_{x\neq0} \frac{\Vert A^T A x \Vert}{\Vert x \Vert} + 1 \right) \cdot \left( \min \limits_{x\neq0} \frac{\Vert A^T A x \Vert}{\Vert x \Vert} + 1\right)^{-1} \\ &= \frac{\sigma_{\max}^2+1}{\sigma_{\min}^2+1} \end{align}$$

If the above holds up, I believe all that's left to prove is, which I'm unable to,

$$ \frac{\sigma_{\max}^2+1}{\sigma_{\min}^2+1} \leq \frac{\sigma_{\max}^2}{\sigma_{\min}^2} $$

which seems to hold when I try it with random numbers in Matlab. Thanks in advance.

Answer 1

In fact, you made a mistake between lines 3 and 4. You should have ended up at $$ \frac{\sigma_{\max}^2+\alpha}{\sigma_{\min}^2+\alpha} \leq \frac{\sigma_{\max}^2}{\sigma_{\min}^2} $$ To prove that this is the case: let $p = \sigma_{\max}^2$, $q = \sigma_{\min}^2$. We note that with $q,\alpha >0$, we have $$ \frac{p + \alpha}{q + \alpha} = \frac{q + \alpha + (p-q)}{q + \alpha} = 1 + \frac{p - q}{q + \alpha} \leq \\ 1 + \frac{p - q}{q} = \frac{q + p-q}{q} = \frac{p}{q} $$ as desired.

Notes: We could also have used calculus: it suffices to compute the derivative of $f(x) = \frac{p + x}{q + x}$, and show that $f' < 0$ when $p\geq q>0$ and $x>0$. Also, if we divided the top and bottom by $\alpha$, we would see that it suffices to consider the $\alpha = 1$ case. In order to have a finite condition number, I assumed that $q = \sigma_{min} > 0$.

Answer 2

You have a couple of problems in your attempt: In the inequality, you use the triangle inequality to say that $\|A^{T}Ax+\alpha Ix\|\leq \|A^{T}Ax\|+\|\alpha Ix\|,$ which is certainly true, but in the right factor, there is an inverse. Since $0<a\leq b$ if and only if $0<b^{-1}\leq a^{-1},$ the inequality is in the wrong direction for that factor.

Also, you say that $\|\alpha Ix\|/\|x\|=1,$ but this should be $\alpha,$ since $\|\alpha Ix\|=|\alpha|\|Ix\|=\alpha\|x\|,$ since $\alpha\geq0,$ and $Ix=x.$

So we want to show that $\|A^{T}A+\alpha I\|=\|A^{T}A\|+\alpha=\sigma_{\mathrm{max}}^{2}+\alpha.$ Note that since $A^{T}A$ is Hermitian, and so is $\alpha I,$ that we may find the largest eigenvalue of $A^{T}A+\alpha I$ by maximizing the Rayleigh quotient $$\frac{x^{T}(A^{T}A+\alpha I)x}{x^{T}x}=\frac{x^{T}A^{T}Ax}{x^{T}x}+\alpha\frac{x^{T}Ix}{x^{T}x}=\frac{x^{T}A^{T}Ax}{x^{T}x}+\alpha.$$ Clearly, this is maximized at $\sigma_{\mathrm{max}}^{2}+\alpha,$ since the first quantity is exactly what needs to be maximized to find $\sigma_{\mathrm{max}}^{2}.$ Minimizing the quantity above yields $\sigma_{\mathrm{min}}^{2}+\alpha$ by the same reasoning. Therefore $$\mathrm{cond}_{2}(A^{T}A+\alpha I)=\frac{\sigma_{\mathrm{max}}^{2}+\alpha}{\sigma_{\mathrm{min}}^{2}+\alpha}.$$ I leave proving the inequality to you.