1
$\begingroup$

I'm given a problem:

$\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_r$ are the nonzero singular values of $\textbf{A}\in\mathbb{R}^{M\times N}$. If $\epsilon \neq 0$ is a real scalar, s.t. $|\epsilon| < \sigma^{2}_r$, show that $(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})$ is invertible.

I found the resources Why is $A^TA$ invertible if $A$ has independent columns? and Matrix inverse of $A + \epsilon I$, where $A$ is invertible

But I'm not sure how useful they are. The first is in the case where A has independent columns, which is not necessarily true here, and the second presumes A is invertible. I believe that $\textbf{A}^T\textbf{A}$ is invertible by definition, but I'm not sure if I can just plug $\textbf{A}^T\textbf{A}$ in everywhere that post uses A and follow through. That also wouldn't help me understand the problem, just blindly substitute into a solution.

Can anyone help me understand WHY $(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})$ is invertible? And/or point me in the right direction to construct a proof of it?

$\endgroup$
1
  • $\begingroup$ Just a thought, you can diagonalize $A^TA$, so it shouldnt be too hard to analyze everything after a suitable change of basis $\endgroup$ – operatorerror Dec 5 '18 at 21:59
3
$\begingroup$

Write out $A$ in its SVD, $A=U\Sigma V^T$. Then we have

$$A^TA+\epsilon I = V\Sigma^2 V^T+\epsilon I = V\Sigma^2V^T+\epsilon VV^T = V(\Sigma^2+\epsilon I)V^T.$$ From this, we have that the eigenvalues are exactly $\sigma_i^2+\epsilon$ for $i=1\dots r$ and $\epsilon$ for $i=r+1\dots n$. These are all nonzero, so the matrix is invertible.

$\endgroup$
1
  • $\begingroup$ Thank you! Is there a straightforward way to find the limit of $(\textbf{A}^T\textbf{A}+\epsilon \textbf{I})^{−1}\textbf{A}^T$ as $\epsilon$ goes to 0? Obviously this reduces to $(\textbf{A}^T\textbf{A})^{-1}\textbf{A}^T$, but I'm not sure where to go from here without specific values for A $\endgroup$ – W. MacTurk Dec 6 '18 at 1:58
1
$\begingroup$

You can show that $A^\top A$ is positive semi-definite (specifically, that it has nonnegative eigenvalues $\sigma_1^2, \ldots, \sigma_r^2, 0, \ldots, 0$).

[It is not always invertible. Specifically, if some of its eigenvalues are zero, then it is not invertible.]

Knowing this fact about $A^\top A$, can you explicitly write down the eigenvalues of $A^\top A + \epsilon I$? What values of $\epsilon$ make this matrix invertible or non-invertible?

$\endgroup$
1
  • $\begingroup$ Wouldn't the eigenvalues just be $\sigma_{1}^{2}+\epsilon , \sigma_{2}^{2}+\epsilon , ...\sigma_{r}^{2}+\epsilon$, with trailing eigenvalues of $\epsilon$ if $\textbf{A}^T\textbf{A}$ was not invertible? $\endgroup$ – W. MacTurk Dec 7 '18 at 3:24

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.