Extract Angles from Gramian Matrix

243 Views Asked by At

Let $\mathbf{G}$ be a positive semi-definite matrix of rank $d$. Then it is the Gramian of some position matrix $\mathbf{X}$ in $\mathbb{R}^d$ i.e. $\mathbf{G}_{ij}=\mathbf{x}_i \cdot\mathbf{x}_j$ where $\mathbf{x}_i \in \mathbb{R}^d$ and $\mathbf{x}_i \cdot\mathbf{x}_j$ is the dot product between vectors.

The distance matrix $\mathbf{D}$, defined as $D_{ij}=||\mathbf{x}_j - \mathbf{x}_i||$, can be retrieved directly from $\mathbf{G}$ as follows : $$ \mathbf{D}=\delta(\mathbf{G})\cdot\mathbf{1} + \mathbf{1}\cdot\delta(\mathbf{G}) - 2\mathbf{G} $$ where $\mathbf{1}$ is a matrix of ones and $\delta(\mathbf{G})$ is the diagonal matrix of $\mathbf{G}$ i.e. $\delta(\mathbf{G}) = \mathbf{G}*\mathbf{I}$ where $\mathbf{I}$ is the Identity matrix and $*$ the element-wise product.

Is it possible to recover the angle tensor defined as $\mathbf{\Theta}_{ijk} = \text{angle}(\mathbf{x}_i,\mathbf{x}_j,\mathbf{x}_k)$ directly without having to find the position matrix $\mathbf{X}$?

Edit: We can define the angle between three vectors as $\theta_{ijk}=\arccos \left(\frac{(\mathbf{x}_i-\mathbf{x}_j) \cdot (\mathbf{x}_k-\mathbf{x}_j)}{||(\mathbf{x}_i-\mathbf{x}_j)|| ||(\mathbf{x}_k-\mathbf{x}_j)||}\right)$

1

There are 1 best solutions below

0
On BEST ANSWER

I believe the answer is yes.

Let $i, j, k$ be given and consider the problem of computing $$s = (x_i - x_j) \cdot (x_k-x_j).$$ Let $g_{ij}$ denote the $(i,j)$ entry of $G$. Then $$ s = x_i \cdot x_k - x_i \cdot x_j - x_j \cdot x_k + x_j \cdot x_j = g_{ik} - g_{ij} - g_{jk} + g_{jj} $$ In particular, when $k=i$ we find $$ \|x_i - x_j\|_2^2 = g_{ii} - 2 g_{ij} + g_{jj}.$$ This allows us to assemble the fraction needed to compute the angles.