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?
 A: 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).
A: 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$.
