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.

Suppose $\{ v_1, \ldots, v_k \}$ is a set of vectors in $\mathbb{R}^n$. The associated $k\times k$ Gram matrix is given by $$ G = [v_i \cdot v_j]_{i,j} $$ It's (apparently) well known that the Gram matrix of a set of vectors determines the vectors up to an isometry of $\mathbb{R}^n$ (e.g. [1])

My question is: does anyone know of a reference for an algorithm that performs the reconstruction? More precisely, I'm looking for an algorithm that takes $G$ as input and outputs $\{ Av_1, \ldots, Av_k \}$ for some $A \in SO(n)$.

[1] http://mathworld.wolfram.com/GramMatrix.html

share|improve this question
    
It is the Cholesky factorization of $G$ that you are interested in. –  adam W Nov 28 '12 at 17:10
1  
Where is the $A \in SO(n)$ with Cholesky? –  copper.hat Nov 28 '12 at 17:12
    
@adamW Perfect - thanks! copper.hat - the $A$ is implicit in the factorization that you find (e.g. the possible factorizations correspond to all the possible A's) –  David Dynerman Nov 28 '12 at 17:36
    
@David To finish this question I suggest you write up your own answer (expound on $A$ implicit in ...). I could answer, but as I am not familiar with the notation of $A \in SO(n)$ it would just be a restatement of my previous comment. –  adam W Nov 28 '12 at 18:01

1 Answer 1

It is impossible.

Let $V=\begin{bmatrix} v_1 \cdots v_k\end{bmatrix}$, and $G_V=V^TV$.

Note that if $U \in O(n)$, we have $G_V = (U V)^T UV = G_{UV}$.

Suppose that given input $G$, an algorithm produces an output $B$.

Then the same algorithm will produce $B$ for both $G_V$ and $G_{UV}$, where $U \in O(n)$. However, if $B=AV$ for some $A \in SO(n)$, then we must also have $B=A' UV$ for some other $A' \in SO(n)$. Since we may choose $U$ with $\det U = -1$, we have a contradiction.

Addendum to address comments below by Marc:

If the requirement $A \in SO(n)$ is relaxed to $A \in O(n)$ instead, then, as @adam w noted in the comments above, one can use the Cholesky decomposition. Since $G=G^T$ and $G\geq 0$, $G$ has a Cholesky decomposition $G = L L^T$ ($L$ is lower triangular, but that is not important here). Since we have $V^T V = L L^T$, we can show that there exists a $U \in O(n)$ (not necessarily unique) such that $V = UL^T$ (it follows from the fact that $\|Vx\| = \|L^T x\|$ for all $x$), and hence we have $L^T = U^T V$. Letting $A=U^T \in O(n)$ shows that $L^T$ does the job.

share|improve this answer
    
So you'r essentially saying that OP shouldn't have said $SO(n)$ but rather $O(n)$? Then you could have just said: a reflection does not change the Gram matrix, so you cannot choose between a solution and its reflection. –  Marc van Leeuwen Nov 28 '12 at 18:13
    
I'm missing your point? I wrote that $G_U = G_{UV}$? Is this not what you are saying? –  copper.hat Nov 28 '12 at 18:16
    
But yes, if the question was about $O(n)$ instead then the Cholesky factorization will work, as @adam W wrote in the comments above. Presumably the OP was interested in $SO(n)$ since that is what was written. –  copper.hat Nov 28 '12 at 18:18
    
@MarcvanLeeuwen: I added an addendum to address what I think was your point. –  copper.hat Nov 28 '12 at 18:39
    
Thanks - sorry, my question was imprecise. The MathWorld (and other) references say the reconstruction is up to isometry, so indeed we want O(n) rather than SO(n). –  David Dynerman Nov 28 '12 at 18:54

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.