What is the maximum number of dimensions in MDS? If I have an arbitrary Euclidean distance matrix $D=(d_{ij}:i=1,\ldots, I; j=1,\ldots, I)$ and I want to reconstruct its elements (pairwise Euclidean distances) via classical Euclidean MDS. That is finding (a possible solution) $x=(x_{ih}:i=1,\dots,I; h=1,\dots,H)$ such that
$$
d_{ij} = \sqrt{\sum_{h=1}^{H} (x_{ih}-x_{jh})^2}.
$$
What is the minimal number $H$ (as a function of $I$) that entails reconstructing exactly any matrix $D$?
My attempt and comments:

*

*The solution $x$ is not unique because we can transform $x$ according to transformations in the Euclidean group (translations, rotations, and reflections) and still have the same distance matrix. However, I am not interested in a unique solution, I am interested in the existence of a solution.

*Since $D$ is a distance matrix it is a square symmetric matrix with diagonal elements equal to $0$, it has $I(I-1)/2$ elements that can vary.

*Intuitively $H$ must be smaller or equal to $I$, but I am not sure if $H=I$ is the answer since $x$ has $I H$ elements that can be greater or equal than $I(I-1)/2$ also for some $H<I$.


If you don't need exact reconstruction, the Johnson-Lindenstrauss Lemma says you can get close to preserving all interpoint distances with $O(\log I)$ dimensions.  If $H>8\log(I)/\epsilon^2$ you can get all the interpoint distances to within a factor of $1\pm\epsilon$.
This paper says that you can't do much better: you can't improve on the error bounds in the Johnson-Lindenstrauss lemma and you can't guarantee an  exact reconstruction with fewer than some multiple of $I^{0.9998}$ dimensions.
It's not (as far as I know) necessarily the case that the dimensions you get from classic MDS are optimal, but there's an extension of the Johnson-Lindenstrauss Lemma that says any random set of $H$ linear combinations has a high probability of achieving the error boud.
