Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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).

share|improve this answer
1  
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.