# Stable orthogonalization procedure

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.

-
So in a way Graham-Schmidt may be seen as the greedy approach to this question: Pick the "new" n-th vector as the vector on the orthogonal complement of the span of the already picked n-1 vectors closest to the given n-th vector. – HenrikRüping Oct 19 '10 at 19:22
Yes. Unfortunately it is not "stable", in the sense that as the first t vectors get orthogonalized, the overlap of the remaining vectors on the span of the t orthogonal vectors will grow with t, so that it "costs" more and more (in terms of distance moved) to make each subsequent vector orthogonal to the previous ones. In my calculations this typically leads to a linear or quadratic dependence of $\epsilon'$ on k. – Thomas Oct 19 '10 at 19:29