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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.