# Finding linear transformation under which distance matrices are similar

I have $$n$$ sets of vectors, where each set $$S_i$$ contains $$k$$ vectors in $$\mathbb{R}^d$$. I know there is some unknown linear transformation $$W$$ under which the distance matrix $$D_i$$ (a $$k\times k$$ matrix) is approximately "the same" (i.e. has a low variance) among all sets $$S_i$$.

To illustrate, it might be the case that for each vector in each $$S_i$$, the first $$\frac{k}2$$ numbers are random noise, and the latter $$\frac{k}2$$ are the same for each $$i$$. In this case, $$W$$ would recover the last $$\frac{k}2$$ elements from each vector. But in practice the structure of the vectors may be more complex than in this toy example.

Is there a method to learn $$W$$ - either using direct linear algebra methods, or through learning (e.g. by optimizing a specific loss on the distance matrices), without finding the naive solution of $$W$$ being the zero mapping, or other mapping that maps all vectors to the same vector?

EDIT:

One possible approach I was considering is to apply a variant of Canonical correlation analysis (CCA) on the distance matrices. CCA projects two "views" of the same data to a shared subspace that maximizes the total correlation between the views; is there a variant of CCA in which the views are not pairs of vectors, but rather sets of vectors that each has some internal structure (as expressed by the distance matrices)? while in CCA we maximize the correlation between the pairs, here I'd like to maximize the correlation between the distance matrices of the different sets.

Thanks

• Is the same $W$ applied to every set $S_i$ or do you have a separate $W_i$ for each set?
– noe
Jul 26 '19 at 11:34
• It's the same transformation. Jul 26 '19 at 12:51
• I might have misunderstood, but my immediate thought was that you could apply something in the variant of principal component analysis? Jul 26 '19 at 16:09
• I don't think PCA would enable me to find the shared subspace. Jul 26 '19 at 16:10
• I was asking if a modified version of PCA might work. It's such a well known algorithm that I guess you've already explored this? Jul 26 '19 at 16:11

## 1 Answer

I think what you are searching is related to metric learning. PCA is an unsupervised learning method but there are equivalent method in which you can introduce label information to learn the best linear transformation that maximize the distance between data from different labels. http://contrib.scikit-learn.org/metric-learn/introduction.html#:~:text=Distance%20metric%20learning%20(or%20simply,%2C%20clustering%2C%20information%20retrieval).