Welcome to MathOverflow

Question

6

1

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.

flag	asked Oct 19 2010 at 19:01 Thomas 63●2

	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 2010 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 2010 at 19:29

ohai · Accepted Answer · 2010-10-20 13:53:06Z UTC

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.

Stable orthogonalization procedure

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.