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).

$\endgroup$
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$.

$\endgroup$
  • $\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 Sep 18 '12 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 Sep 18 '12 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 Sep 18 '12 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 Sep 18 '12 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 Sep 18 '12 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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