Fitting a simplex to set of almost orthogonal vectors

Question

I am trying to solve the following question, that I guess (hope?) has been solved before but I couldn't find any reference.

Let $S$ be a set of $d$ unit vectors in a $d$-dimensional Euclidean space such that for any pair of vectors in $S$ their distance is the range $[\sqrt 2 -O(1/d), \sqrt 2 + O(1/d)]$.

Then, one can find a set $Q$ of $d$ pairwise orthogonal unit vectors such that there is a 1-to-1 mapping between vectors in $S$ and $Q$ such that each point of $S$ is mapped to a point in $Q$ at distance at most $O(1/d)$.

Note: If the range was $\sqrt 2\pm c/\sqrt d$ for some large constant $c$, that would not necessarily be true, here the fact that we have a $1/d$ additive term is key. But I am not sure how to use it...

Answer 1

The point of this answer is to confirm fedja's statement. Let $c$ be a fixed poitive constant, let $x = c/d$ and let $y = \sqrt{1-(d-1)x^2} = 1-(c^2/2)d^{-1} + O(d^{-2})$. Consider the $d$ unit vectors $x_1=(y,x,x,\ldots, x)$, $x_2=(x,y,x,\ldots,x)$, $x_3=(x,x,y,\ldots, x)$, ... $x_d=(x,x,x,\ldots, y)$. Note that the distance between $x_i$ and $x_j$ is $\sqrt{2(x-y)^2} = \sqrt{2} + O(d^{-1})$.

Let $u_i$ be any orthonormal vectors. I will show that $\sum |u_i-x_i|^2 \geq c^2 + O(d^{-1})$, and thus at least one of the $|u_i-x_i|$ is $\geq c/\sqrt{d} + O(d^{-1})$.

Let $U$ and $X$ be the matrices with columns $u_i$ and $x_i$. Then $\sum |u_i-x_i|^2$ is the square of the distance between $U$ and $X$ as elements of $\mathbb{R}^{n^2}$. The matrix $X$ is positive definite, because it is the sum of the positive semidefinite matrix all of whose entries are $x$, and the positive definite matrix $(y-x) \text{Id}_d$. For any positive definite matrix $X$, the distance $\text{dist}(U,X)$ to an orthogonal matrix is minimized at $U = \text{Id}_d$. (See, eg, here for a more general statement.) So we just need to compute $\text{dist}(\text{Id}_d, X)$. We have $$\text{dist}(\text{Id}_d, X)^2 = d (y-1)^2 + (d^2-d) x^2 = c^2 + O(d^{-1}),$$ as promised.