Take the 2-minute tour ×

What would then be the way to determine a true dimensionality of a configuration of points $X\in\mathbb{R}^{n\times k}$ based on its Gram matrix $G=XX^T$? The "true" dimensionality refers to the minimum number of dimensions needed to represent a configuration (eg, a line is 1D, but can be represented in 2D).

Different shifts would imply different ranks of $G$ that correspond to different dimensionalities. Consider, for instance, the paper http://convexoptimization.com/TOOLS/Gower1.pdf (Sect. 3, very short, please consider)

If I understand correctly, as long as the shifts are of the form $X'=PX$, $P=I_n-1_nw^T$, where $1_n^Tw=1$, the rank of $G'=X'(X')^T$ is the true dimensionality of $X$? If you consider the 2x2 example from the above paper, a shift where one point is the origin reduces the dimensionality to 1D, which is the true dimensionality (same holds for a centroid origin) Does that mean that, in order to recover the "true" configuration, one is restricted to the above form of the shift?

share|improve this question
@AronAhmadia Isn't your "any shift that does not move one of the points onto the origin is guaranteed to preserve dimensionality of the space" contradicting with the above statement? –  usero Oct 30 '12 at 11:01
What do you mean by the true dimensionality of $X$? Is it the dimension of the affine space spanned by the columns? –  Arnold Neumaier Oct 30 '12 at 14:32
@ArnoldNeumaier The question has been edited: "true" dimensionality is the "minimum" dimensionality needed to represent a configuration. –  usero Oct 30 '12 at 15:52

1 Answer 1

up vote 2 down vote accepted

Yes. You need to move the affine subspace to the origin by subtracting from the points (rows of $X$) some point in this affine subspace, i.e., a linear combination of the given points. This leads to the form of $P$. The rank of the matrix $PX$ formed by the shifted points then gives the dimension of the subspace. As the rank of $X$ and $G=XX^T$ is the same, the rank of $PGP^T$ gives the correct dimension.

share|improve this answer

Your Answer


