At a high level, my question is the following: given a set of $k$ vectors in Euclidean space which are pairwise "almost orthogonal", can one find a set of $k$ orthogonal vectors which are pairwise close to the original ones? This could be seen as a stable version of Gram-Schmidt orthogonalization, in which, under the promise that the original set of vectors is not too far from being orthogonal, one has the guarantee that they do not need to be moved too much in order to become orthogonal.

More precisely, assume given vectors $v_i$, $i=1,\ldots,k$ in a real (or complex) $k$-dimensional space, such that $\sum_{i\neq j} \langle v_i,v_j\rangle \leq \epsilon k$ ($\epsilon$ should be understood as an arbitrarily small constant, or it could even be $o(k)$ if needed -- the weaker the assumption the better). Then, does there exist a set of orthogonal vectors $w_i$ such that $\sum_i \|w_i - v_i\|^2 \leq \epsilon' k$? (The norm is the usual Euclidean norm.) The interesting question is whether one can get an $\epsilon'$ which depends on $\epsilon$ only, not on $k$.

A related question (the one I am originally most interested in), is that of orthogonalizing $d$-dimensional projector matrices $P_1,\ldots,P_k$: assume $\frac{1}{d} \sum_{i\neq j} \langle P_i,P_j \rangle \leq \epsilon$ (where now the inner product is the trace inner product), can you find orthogonal projectors $Q_i$ such that $\frac{1}{d}\sum_i \|P_i-Q_i\|_F^2 \leq \epsilon'$? (Here the norm is the Frobenius norm, the sum of squares of the coefficients.) So far using various iterative procedures I can only get a bound where $\epsilon' = poly(\log k) \epsilon$, but I would like to know if the dependence on $k$ can be removed.