Using $\|V_1 V_1^\star - V_2 V_2^\star\|_\infty$ to bound $\|V_1 - V_2\|_\infty$ The converse question of the result I am asking about is here. Denote the operator norm by $\|\cdot \|_\infty$. That is $\|X\|_\infty = \max\{\|Xv\|:\|v\| = 1\}$ and $\|\cdot\|$ is the Euclidean 2-norm for vectors.
Let $V_1, V_2$ be (possibly rectangular) matrices that satisfy $V_i^\star V_i = I$ (where $\star$ denotes the transpose conjugate) such that
$$\|V_1 XV_1^\star - V_2X V_2^\star\|_\infty\leq \varepsilon$$
for all positive semidefinite $X$ with $\lVert X\rVert_\infty = 1$. Is it possible to then bound
$$\|V_1 - V_2\|_\infty$$
in terms of $\varepsilon$?
 A: I just want to point out another possible positive answer that people may be interested in.
Claim: suppose $V_1, V_2 \in R^{n\times r}$ where $r \leq n$ and $V_1^{\star}V_1 =V_2^{\star}V_2 = I_{r}.$ If $\|V_1V_1^{\star} - V_2V_2^{\star}\| \leq \epsilon$, then there exists a rotation matrix $H \in R^{r\times r}$ where $H^{\star}H = I_{r}$ and
$$
\|V_1 H - V_2\| \leq 2\epsilon.
$$
One possible $H$ can be explicitly constructed: $H = U_Q V_Q^{\star}$ where $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ is the SVD of $V_1^{\star}V_2.$
Proof:  It is sufficient to show $\|V_1 H - V_2\| \leq 2\epsilon$ for $H = U_QV_Q^{\star}.$
First, notice that $\|AV_2\| \leq \|A\| \|V_2\| \leq \|A\|$ for any $A \in R^{n\times n}$. Let $A = V_1V_1^{\star} - V_2V_2^{\star}$, since $V_2^{\star}V_2 = I_r$, we have
$$
\|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon.
$$
We tend to show that $\|H - V_1^{\star}V_2\| \leq \epsilon$, then by the triangle inequality, we can complete the proof:
$$
\|V_1 H - V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| + \|V_1 (H - V_1^{\star}V_2)\| \leq \epsilon + \|V_1\| \|H-V_1^{\star}V_2\| \leq 2\epsilon.
$$
Note that in fact,
$$
\|H - V_1^{\star}V_2\| = \|U_Q V_Q^{\star} - U_Q\Sigma_Q V_Q^{\star}\| \leq \|U_Q\|\|I_r - \Sigma_Q\|\|V_Q\| = \|I_r - \Sigma_Q\|.
$$
Next, we want to bound $\|I_r - \Sigma_Q\|.$ Notice that $\|V_2^{\star}A\| \leq \|A\|$. Let $A = V_1V_1^{\star}V_2 - V_2$, we have
$$
\|V_2^{\star}V_1V_1^{\star}V_2 - V_2^{\star}V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon. 
$$
Note that $V_2^{\star}V_2 = I_r$ and $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ again, then
$$
\|V_Q \Sigma_Q^{2} V_Q^{\star} - I_r\| \leq \epsilon.
$$
This implies that $\|\Sigma_Q^2 - I_r\| \leq \epsilon.$ Notice that for any $a \in R^{+}$,
$$
|a-1| \leq |a-1||a+1| = |a^2 - 1|. 
$$
Therefore, since $\Sigma_Q$ is diagonal and non-negative (singular values), we have $\|\Sigma_Q - I_r\| \leq \|\Sigma_Q^2 - I_r\| \leq \epsilon.$ This completes the proof.
Remark: Here, $H = U_Q V_Q^{\star}$ is in fact also the optimizer of the following problem:
$$
\min_{F \in R^{r\times r}, F^{\star}F = I_{r}} \|V_1F - V_2\|_{\mathrm{F}}
$$
where $\|\cdot\|_{\mathrm{F}}$ is the Frobenius norm. See Orthogonal Procrustes problem for further reference.
