Let $A$ be an $m\times n$ matrix, $\mu\in\mathbb{R}$ and $\epsilon\in[0,\frac{1}{2})$. Show that for any $\epsilon$-net $\mathcal{N}$ of the sphtere $S^{n-1}$ we have: \begin{equation} \sup_{x\in S^{n-1}}\big|\|Ax\|_2-\mu\big|\leq\frac{C}{1-2\epsilon}\sup_{x\in \mathcal{N}}\big|\|Ax\|_2-\mu\big| \end{equation}
My attempt:
I've assumed without loss of generalities that $\mu=1$ and I've tried to estimate the supremum for $x\in S^{n-1}$ of $\big|\|Ax\|_2^2-1\big|$. Now I can write $\big|\|Ax\|_2^2-1\big|=\langle Rx,x\rangle$ with $R=A^TA-I_n$. Now since $S^{n-1}$ is compact there exist $x_0$ such that: \begin{equation} \sup_{x\in S^{n-1}}|\langle Rx,x\rangle|=|\langle Rx_0,x_0\rangle|\leq \|R\| \end{equation} (with $\|R\|$ I denote the operator norm of $R$) Now by definition of $\epsilon$-net there exists $\hat{x}\in\mathcal{N}$ such that $\|x_0-\hat{x}\|_2\leq\epsilon$. Then using the result given in another exercise (I solved it so I can use it in the proof) that tells us that for $A$ an $n\times n$ symmetric matrix and for $\mathcal{N}$ an $\epsilon$-net of the sphere $S^{n-1}$ we have: \begin{equation} \sup_{x\in\mathcal{N}}\big|\langle Ax,x\rangle\big|\leq\|A\|\leq\frac{1}{1-2\epsilon}\sup_{x\in\mathcal{N}}\big|\langle Ax,x\rangle\big| \end{equation} This implies that since $R$ is an $n\times n$ symmetric matrix: \begin{equation} \begin{split} \sup_{x\in S^{n-1}}\big|\|Ax\|_2-1\big|&\leq\sup_{x\in S^{n-1}}\big|\|Ax\|_2^2-1\big|\\ &=\sup_{x\in S^{n-1}}\big|\langle Rx,x\rangle\big|\\ &\leq\sup_{x\in S^{n-1}}\big|\langle Rx_0,x_0\rangle\big|\\ &\leq\|R\|\leq\frac{1}{1-2\epsilon}\sup_{x\in\mathcal{N}}\big|\langle Rx,x\rangle\big|\\ &=\frac{1}{1-2\epsilon}\sup_{x\in S^{n-1}}\big|\|Ax\|_2^2-1\big| \end{split} \end{equation} Where I have used in the first inequality that if $z>0$ $|z-1|\leq|z^2-1|$. At this point I'm not able to obtain the quantity $\sup_{x\in\mathcal{N}}\big|\|Ax\|_2-1\big|$ also on the RHS; I know that I can write: \begin{equation} \big|\|Ax\|_2^2-1\big|=\big|\|Ax\|_2-1\big|\big|\|Ax\|_2+1\big| \end{equation} But I cannot find the correct way to conclude this reasoning. Can someone help me?
Now that $\sup_{x\in S^{n-1}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert \le \frac{1}{1-2\varepsilon} \sup_{x\in\mathcal{N}} \left\{ \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert \big( \lVert Ax \rVert_{2} + 1 \big) \right\}$, we have $\sup_{x\in S^{n-1}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert \le \frac{\color{red}3}{1-2\varepsilon} \sup_{x\in\mathcal{N}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert$ when $\lVert A \rVert \le 2$.
As for the case where $\lVert A \rVert > 2$, observe that $\sup_{x\in S^{n-1}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert = \lVert A \rVert - 1$ where the maximum is attained at some $x_{0} \in S^{n-1}$ and that the existence of $x_{1} \in \mathcal{N} \cap \{ x : \lVert x - x_{0} \rVert_{2} \le \varepsilon \}$ leads to that $$\begin{aligned} \sup_{x\in\mathcal{N}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert &\ge \lVert Ax_{1} \rVert_{2} - 1 \\ &\ge \lVert Ax_{0} \rVert_{2} - \lVert A(x_{1}-x_{0}) \rVert_{2} - 1 \\ &\ge \lVert A \rVert (1 - \varepsilon) - 1 \quad > 1 - 2\varepsilon . \end{aligned}$$ Then the conclusion is easily seen. To be explicit, $$\begin{aligned} \lVert A \rVert - 1 &\le \frac{1}{1-\varepsilon}\Big( \sup_{x\in\mathcal{N}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert + 1 \Big) - 1 \\ &= \frac{1}{1-\varepsilon}\Big( \sup_{x\in\mathcal{N}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert + \varepsilon \Big) \quad\le \frac{C}{1-2\varepsilon} \sup_{x\in\mathcal{N}} \big\lvert \lVert Ax \rVert_{2} - 1 \big\rvert , \end{aligned}$$ provided that $C = {\color{red}3} \ge \sup_{d > 1-2\varepsilon} \frac{1-2\varepsilon}{1-\varepsilon} \left( 1 + \frac{\varepsilon}{d} \right) = 1$.