# In Multidimensional Scaling (MDS), is it safe to assume that the optimal embedding dimension grows with the growth of sample size?

My question is more of a theoretical nature, so it'd be great to have some references to papers, but it'd be also nice to see some experiments.

Let $$D:=[d_{ij}]$$ be an $$n \times n$$ distance matrix, i.e. $$d(i,i)=0, d(i,j)=d(j,i) > 0 \forall i, j = 1 \dots n.$$ Assume that: the data came from an unknown dimensional Euclidean space. Assume we're performing classical MDS on the data to embed it into a lower dimension $$p$$ thna the original data came from. Assume $$p$$ has been supplied already. That is, we're performing the following algorithm:

1. Define the centering matrix $$H_n:= I_n - \frac{1}{n}1_n1_n^{T}.$$
2. Perform the SVD of $$-\frac{1}{2}H_nD^2H_n$$, where $$D^2$$ is the entrywise square of $$D$$ (so, not the square of $$D$$ as in matrix multiplication/squaring). Assume $$-\frac{1}{2}H_nD^2H_n= U\Lambda U^{T}$$ after SVD.
3. From the diagonal matrix $$\Lambda$$ above that contains the eigenvalues $$\{\lambda_1,\dots \lambda_n\}$$ of $$-\frac{1}{2}H_nD^2H_n,$$ extract the square roots of the $$p$$ largest eigenvalues, and the corresponding eigenvectors. Call the corresponding part of $$\Lambda$$ to be $$\sqrt\Lambda_p$$, and that of $$U^{T}$$ to be $$U_p^{T}$$
4. Finally, the $$p$$ -dimensional embedding is given by the $$n$$ columns of the $$p \times n$$ matrix $$Y_p:=\sqrt\Lambda_p U_p^{T}$$.

My question is as follows:

1) Is it "safe" to assume that for a "good quality" embedding, $$p \to \infty$$ as $$n \to \infty$$? By "good quality" embedding, I mean a statement that says: $$||-\frac{1}{2}H_nD^2H_n - Y_p^{T}Y_p||_F \to \infty$$ as $$n \to \infty$$ but $$p$$ is fixed. I'm getting the intuition from Johnsson-Lindenstrauss lemma, which states that : the lower embedding dimension to which a nearly distance-preserving linear map exists, varies as a function of $$O(log \hspace{1mm} n)$$. Note that in both type of dimensional reduction/embedding problems, we can just assume that the data came from 1D (i.e. $$\mathbb{R}$$), and then we'd not have the embedding dimension $$p \to \infty$$ as $$n \to \infty$$, as we can take the embedding just to be the identity map.