# Is there an algorithm similar to Gram Schmidt?

Everybody knows the Gram-Schmidt algorithm when it comes to basic linear algebra, to take a set of vectors $x_i \in \mathbb{R}^n$ and transform them into a set of vectors that spans the same space, is linear combination of $x_i$ and all vectors in the new set are orthogonal.

I have a different, but similar problem. Let $A \in \mathbb{R}^{d \times n}$, and $x_i$ a set of vectors as before for $i=1,\ldots,m$. I want to make them all orthogonal in a projected space, such that $\langle Ax_i , Ax_j \rangle = 0$ for all $i \neq j$.

This means that $x_i^{\top} A^{\top} A x_i = 0$ for all $i \neq j$.

I want them of course to span the same space, and the new vectors to be a linear combination of the $x_i$.

The key point is that I only have "access" to $A^{\top} A$. I can never refer directly to $A$.

Is there a procedure for doing that?

-

The Gram Schmidt process works with any inner product. If $A$ is invertible, then $\langle x , y \rangle_* = \langle A x , A y \rangle$ defines a perfectly good inner product.

Remember to use the corresponding norm $\|x\|_* = \|A x\| = \sqrt{\langle x , A^TA y \rangle}$ as well.

So, in the algorithm, replace $\langle x , y \rangle$ by $\langle x , y \rangle_*$ and $\|x\|$ by $\|x\|_*$, and it will produce a set of vectors that are '$\langle \cdot , \cdot \rangle_*$' orthogonal.

And, of course, $\langle x , y \rangle_* = \langle A x , A y \rangle = \langle x , A^TA y \rangle$, so you only need $A^T A$ to do the computations.

Note: I assumed that $A$ was invertible, hence square, which is not what the OP asked. Here is the 'fix' (a minor modification), and some comments:

In all cases, the Gram Schmidt process produces a set of vectors that spans the same space and are orthogonal with respect to the inner product.

If $\ker A = \{0\}$ (ie, A in injective), then $\langle \cdot , \cdot \rangle_*$ is still a valid inner product on $\mathbb{R}^n$. This is true iff $A^TA >0$. The Gram Schmidt process works exactly as you want.

If $\ker A \neq \{0\}$, then a little more care is needed. In this case $\langle \cdot , \cdot \rangle_*$ is a valid inner product on $Q =\mathbb{R}^n/\ker A$, the quotient space, and unchanged will produce a set of vectors (in $Q$) that spans (again in $Q$) the same space as the original vectors. So the Gram Schmidt process will discard vectors that it considers to be zero (ie, vectors for which $\|x\|_*=0$, or equivalently, $x \in \ker A$). So, in this case, the process needs to be modified to retain all vectors, but no longer perform computations on them if they are zero in $Q$. The resulting set of vectors (which includes vectors that would have been discarded by the original process) will still span the original space, and will also be orthogonal in $Q$ (which is what you wanted).

-
I am not sure that it always defines an inner product - because I can imagine cases where $x A^{\top} A x = 0$ for $x \neq 0$. I guess $A^{\top} A$ has to be positive definite. – kloop Aug 2 '12 at 18:17
thanks! I will just assume that it is positive definite :-) oh well. – kloop Aug 2 '12 at 18:19
You just need $A$ to be invertible, then $A^TA >0$ (since $\langle x , A^T A x \rangle = \langle A x , A x \rangle = \|A x\|^2 >0$ whenever $x \neq 0$). – copper.hat Aug 2 '12 at 18:20
$A$ can be a rectangular matrix, not sure invertibility makes sense in that case. But I think it is not too bad to assume that $A^{\top} A$ is positive definite, and not just positive-semidefinite (like any $A^{\top} A$). – kloop Aug 2 '12 at 18:23
Sorry, I missed that completely in the question. – copper.hat Aug 2 '12 at 18:24

Since you have $A^TA$, you can compute the left singular vectors ($u_j$) of $A$, which are the eigenvectors of $A^TA$. Then you can expand $u_j$ with respect to $x_i$ ($i=1,\cdots,m$) by $$u_j=\sum_{i=1}^m\alpha_ix_i$$ Because $Au_j$ will give you the right singular vector $v_j$, you will have $\langle Au_i, Au_j\rangle = 0$ for $i \neq j$.

-