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:
- Define the centering matrix $H_n:= I_n - \frac{1}{n}1_n1_n^{T}.$
- 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.
- 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}$
- 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.
