2
$\begingroup$

Suppose an Euclidean distance $D\in\mathbb{R}^{n\times n}$ matrix between a set of $n$ objects is given. To obtain inner-products (which will be further be used to recover coordinates), entries of $D$ are squared, and the matrix is double-centered and scaled, ie., $K=-\frac{1}{2}JD^{(2)}J$, where matrix $J=I-\frac{1}{n}11^T$ defines the origin wrt which the inner-products are formed. So, the aim is to reconstruct coordinates $X$ that give rise to inner products $K$, $$K=-\frac{1}{2}JD^{(2)}J=JXX^TJ.$$ This is done by eigendecomposition of $K$.

Given the above equation, I wonder if one could use a shortcut $-\frac{1}{2}D^{(2)}=XX^T$, ie, obtain coordinates $X$ without double-centering $-\frac{1}{2}D^{(2)}$ (matrix $J$ is removed from the left and from the right).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Your proposal will give meaningless results. This can be seen already with simple examples consisting of two points only. Indeed, the matrix that you want to decompose is not even positive semidefinite as it is nonzero but has zero diagonal entries.

Note that you can't cancel $J$ since it is singular. In general, $Ju=Jv$ implies $u=v$ if and only if $J$ has a trivial kernel, i.e., iff the rank of $J$ equals the number of columns of $J$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Note that I'm mainly interested in a "technical reasoning". Wouldn't a solution $X$ to i) $-\frac{1}{2}D^{(2)}=XX^T$ be also a solution to ii) $-\frac{1}{2}JD^{(2)}J=XX^T$, up to origin position. Basically, why could not one solve ii) to obtain a solution to i) (just cancel $J$ from the sides of both sides?) Note that diagonal entries would remain zero. $\endgroup$
    – usero
    Commented Sep 18, 2012 at 13:22
  • 1
    $\begingroup$ No. $X$ will usually have complex entries, and is useless. - Multiplication by $J$ on both sides makes the diagonal positive when the distance matrix is Euclidean. Note that ypu can't cancel $J$ since it is singular. $\endgroup$
    – Arnold Neumaier
    Commented Sep 18, 2012 at 14:56
  • $\begingroup$ Your last sentence answered the question and many related ones. So, in case some $J$ is invertible (general case), one could cancel it. However, suppose a system i) $C^TACx=C^Tb$ is given, for $A\in\mathbb{R}^{n\times n}$ and a rectangular $C\in\mathbb{R}^{n\times m}$, $m<n$. In what manner could one rationalize that the solution to ii) $ACx=b$ is not a solution to i) (now, $C^T$ is rectangular, hence the singularity does not apply) $\endgroup$
    – usero
    Commented Sep 18, 2012 at 15:10
  • $\begingroup$ @usero: $C^Tu=C^Tv$ implies $u=v$ if and only if $C^T$ has a trivial kernel, i.e., iff the rank of $C$ equals the number of rows. $\endgroup$
    – Arnold Neumaier
    Commented Sep 18, 2012 at 17:32
  • $\begingroup$ I guess there is a misunderstanding: if I understand correctly, solving ii) cannot be replaced by solving i), but solving i) can be replaced by solving ii)? $\endgroup$
    – usero
    Commented Sep 18, 2012 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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