9
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ It is the Cholesky factorization of $G$ that you are interested in. $\endgroup$
    – adam W
    Nov 28, 2012 at 17:10
  • 1
    $\begingroup$ Where is the $A \in SO(n)$ with Cholesky? $\endgroup$
    – copper.hat
    Nov 28, 2012 at 17:12
  • $\begingroup$ @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) $\endgroup$ Nov 28, 2012 at 17:36
  • $\begingroup$ @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. $\endgroup$
    – adam W
    Nov 28, 2012 at 18:01

2 Answers 2

5
$\begingroup$

Let $A = USV^*$ be the SVD solution for $A$, a symmetric matrix, which the Gram is. Then $X = U\sqrt{S}$ is an isometry for $X$, the original vectors. The rank of $S$ provides additional information about the input vectors $X$. To obtain the original vectors requires knowing 3 points of the original set so that the isometry can be rotated and/or reflected to match the original set.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 28, 2012 at 18:13
  • $\begingroup$ I'm missing your point? I wrote that $G_U = G_{UV}$? Is this not what you are saying? $\endgroup$
    – copper.hat
    Nov 28, 2012 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – copper.hat
    Nov 28, 2012 at 18:18
  • $\begingroup$ @MarcvanLeeuwen: I added an addendum to address what I think was your point. $\endgroup$
    – copper.hat
    Nov 28, 2012 at 18:39
  • $\begingroup$ 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). $\endgroup$ Nov 28, 2012 at 18:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .