# 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

## 1 Answer

Use a Procrustes rotation of the standard basis vectors onto your vectors. This gives the set of orthogonal vectors with the smallest sum of squares of distances to your vectors.

http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem

"The orthogonal Procrustes problem is a matrix approximation problem in linear algebra. In its classical form, one is given two matrices A and B and asked to find an orthogonal matrix R which most closely maps A to B."

In your case you want to find the orthogonal matrix R which most closely maps the standard basis to your matrix. Something like the columns of R should then be the set of orthogonal vectors which are nearest to your vectors, where 'nearest' is in the sense of sum of squares.

-
Sorry, I should have mentioned all vectors are unit. I am not familiar with Procrustes rotations; is there a good reference to start learning about them (in relation to my original problem)? –  Thomas Oct 19 '10 at 19:45
That turned out to work pretty well also for the case of the projectors I was mentioning, thanks! –  Thomas Oct 21 '10 at 4:25