Show the operator norm of $A^T A - I_n$ can be bounded by $3\max(\delta, \delta^2)$

Question

Let $A$ be an $m\times n$ matrix and $\delta>0.$ If all singular values of $A$ are between $1-\delta$ and $1+\delta$, $$1-\delta\leq s_n(A)\leq s_1(A) \leq 1+\delta,$$ prove $$\Vert A^TA-I_n\Vert \leq 3\max(\delta,\delta^2),$$where $s_1(A),\dots,s_n(A)$ are the singular values of $A$ and $s_1(A) \geq \cdots \geq s_n(A)$. Note that here the definition of the operator norm is $$\Vert A \Vert := \max_{x \in S^{n-1}\\ y \in S^{m-1}}\langle Ax,y\rangle=s_1(A).$$

---

So far, I have tried

$$\Vert A^TA-I_n\Vert = \Vert V(S^TS-I_n)V^T\Vert=s_1(A^TA-I_n).$$

But I am not sure how to connect with $3\max(\delta,\delta^2)$ . This is an extension exercise 4.1.6 from page 80 High-Dimensional Probability by Roman Vershynin. Thank you!

---

Answer 1

Hint: note that $A^TA$ is symmetric, so has real eigenvalues. Can you bound them using the singular values of $A$ (if this isn’t obvious, use the SVD)? What happens when you subtract off the identity matrix? How does this relate to the operator norm?

Answer 2

We only need to prove for any $z \geq 0$, \begin{equation*} \begin{split} 1 -\delta \leq z \leq 1+\delta \Rightarrow |z^2 - 1| \leq 3\max(\delta,\delta^2). \end{split} \end{equation*} When $0<\delta \leq 1$, we have \begin{equation*} \begin{split} &(1-\delta)^2 \leq z^2 \leq (1+\delta)^2 \\ \Rightarrow & -3\delta \leq -2\delta \leq -2\delta + \delta^2 \leq z^2 - 1 \leq 2\delta + \delta^2 \leq 3\delta \quad (\delta^2 \leq \delta)\\ \Rightarrow & |z^2 - 1| \leq 3\delta = 3\max(\delta, \delta^2). \end{split} \end{equation*} When $\delta > 1$, we have \begin{equation*} \begin{split} &1 -\delta < 0\leq z \leq 1 + \delta \\ \Rightarrow & 0 \leq z^2 \leq (1 + \delta)^2 \\ \Rightarrow & -3\delta^2< -\delta^2 < -1 \leq z^2 - 1 \leq 2\delta + \delta^2 \leq 3\delta^2 \quad (\delta \leq \delta^2)\\ \Rightarrow & |z^2 - 1| \leq 3\delta^2 = 3 \max(\delta,\delta^2). \end{split} \end{equation*}