I am reading the paper "The Paulsen Problem Made Simple" by Hamilton and Moitra and I am trying to verify this claim in page 4:
$$\text{dist}^2(v_i,u_i):=\lVert v_i-u_i\rVert^2\leq \left(\sqrt{\frac{d}{n}}-\sqrt{(1-\epsilon)\frac{d}{n}}\right)^2+\gamma\quad(*)$$ where $\gamma\leq \lVert \eta_i\rVert^2+2\lVert \eta_i\rVert$ is a term that depends on $\eta_i$.
Setup: Let $\epsilon>0$ be given and let $V=v_1,v_2,\cdots,v_n$ be a set of vectors in $\mathbb{R}^d$. Suppose further that $V$ is an $\epsilon$-nearly equal norm Parseval frame, i.e., we have the following two conditions $$(1-\epsilon)I\preceq\sum_{i=1}^n v_iv_i^T\preceq (1+\epsilon)I\text{ and }(1-\epsilon)\frac{d}{n}\leq\lVert v_i\rVert^2\leq (1+\epsilon)\frac{d}{n},$$ where $\preceq$ is the Loewner order. Set $$u_i=\sqrt{\frac{d}{n}}\frac{v_i}{\lVert v_i\rVert}+\eta_i,$$ where the $\eta_i$'s are perturbations constructed in such a way that makes every $d$-subset (subset of $d$ elements) of the vectors $U=u_1,u_2,\cdots,u_n$ linearly independent. Moreover, we can make the norms of these perturbations as small as we want. All norms are the Euclidean norms on $\mathbb{R}^d$. Feel free to assume that $2\leq d\leq n$ and that $\epsilon\leq1/2$.
Attempt: Since $(1-\epsilon)\frac{d}{n}\leq\lVert v_i\rVert^2\leq (1+\epsilon)\frac{d}{n}$, then $$1-\frac{1}{\sqrt{1-\epsilon}}\leq 1-\sqrt{\frac{d}{n}}\frac{v_i}{\lVert v_i\rVert}\leq 1-\frac{1}{\sqrt{1+\epsilon}}.$$ Hence, $$\left|1-\sqrt{\frac{d}{n}}\frac{1}{\lVert v_i\rVert}\right|\leq \frac{1}{\sqrt{1-\epsilon}}-1.$$ Now write: $$\begin{align} \text{dist}^2(v_i,u_i):&=\lVert v_i-u_i\rVert^2\\ &= \left\lVert v_i-\sqrt{\frac{d}{n}}\frac{v_i}{\lVert v_i\rVert}-\eta_i\right\rVert^2\\ &\leq \left(\left|1-\sqrt{\frac{d}{n}}\frac{1}{\lVert v_i\rVert}\right|\lVert v_i\rVert+\lVert\eta_i\rVert\right)^2\\ &\leq \left(\left(\frac{1}{\sqrt{1-\epsilon}}-1\right)\sqrt{(1+\epsilon)\frac{d}{n}}+\lVert\eta_i\rVert\right)^2\\ &= \left(\left(\sqrt{\frac{d}{n}}\frac{\sqrt{1+\epsilon}}{\sqrt{1-\epsilon}}-\sqrt{(1+\epsilon)\frac{d}{n}}\right)+\lVert\eta_i\rVert\right)^2\\ &= \left(\sqrt{\frac{d}{n}}\frac{\sqrt{1+\epsilon}}{\sqrt{1-\epsilon}}-\sqrt{(1+\epsilon)\frac{d}{n}}\right)^2+\text{ terms that depends on }\eta_i \end{align} $$ This is the closest thing I got to $(*)$. I could not continue because $\frac{\sqrt{1+\epsilon}}{\sqrt{1-\epsilon}}\not\leq1$. Also I have $(1+\epsilon)$ instead of $(1-\epsilon)$ in the second term, but I think this is fine since when Moitra himself stated $(*)$ in this talk (at 22:30) he stated it with $(1\pm\epsilon)$. Thanks for your help!
Here's a natural way to get the estimate. I'll drop the subscript $i$ because it doesn't play a role. \begin{align} \|v-u\|^2 &=\|v\|^2+\|u\|^2-2\operatorname{Re}\langle v,u\rangle =\|v\|^2+\tfrac dn+\|\eta\|^2+2\sqrt{\tfrac dn}\tfrac1{\|v\|}\operatorname{Re}\langle v,\eta\rangle-2\operatorname{Re}\langle v,u\rangle\\[0.3cm] &=\|v\|^2+\tfrac dn+\|\eta\|^2+2\sqrt{\tfrac dn}\tfrac1{\|v\|}\operatorname{Re}\langle v,\eta\rangle-2\sqrt{\tfrac dn}\,\|v\|-2\operatorname{Re}\langle v,\eta\rangle\\[0.3cm] &=\|v\|^2+\tfrac dn-2\sqrt{\tfrac dn}\,\|v\|+\|\eta\|^2+2\Bigl(\sqrt{\tfrac dn}\tfrac1{\|v\|}-1\Bigr)\operatorname{Re}\langle v,\eta\rangle\\[0.3cm] &\leq (1+\varepsilon)\,\tfrac dn+\tfrac dn-2\sqrt{\tfrac dn}\,\sqrt{1-\varepsilon}\,\sqrt{\tfrac dn}+\|\eta\|^2+2\Bigl(\sqrt{\tfrac dn}\tfrac1{\|v\|}-1\Bigr)\operatorname{Re}\langle v,\eta\rangle\\[0.3cm] &=\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+2\Bigl(\sqrt{\tfrac dn}\tfrac1{\|v\|}-1\Bigr)\operatorname{Re}\langle v,\eta\rangle\\[0.3cm] &\leq\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+2\Bigl(\sqrt{\tfrac dn}\tfrac1{\|v\|}-1\Bigr)\|v\|\,\|\eta\|\\[0.3cm] &\leq\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+2\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)\,\|\eta\|\\[0.3cm] &=\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+2\sqrt{\tfrac dn}\Bigl(1-\sqrt{(1-\varepsilon)}\Bigr)\,\|\eta\|\\[0.3cm] &=\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+2\sqrt{\tfrac dn}\Bigl(\frac\varepsilon{\sqrt{(1-\varepsilon)}+1}\Bigr)\,\|\eta\|\\[0.3cm] &\leq\Bigl(\sqrt{\tfrac dn}-\sqrt{(1-\varepsilon)\tfrac dn}\Bigr)^2+\|\eta\|^2+\|\eta\|\\[0.3cm] \end{align}