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