Multidimensional Scaling: Theory And Applications

Описание: I discuss multidimensional scaling, a set of techniques for coming up with Euclidean point clouds that best match a specified distance matrix. This is useful to get a spatial visualization of data. I talk about some fun applications to survey data, ranked choice voting similarity, and bending invariant representations of 3D shapes. Along the way, I carefully derive all of the algorithms using linear algebra, so it's a great review if you're rusty on things like spectral decompositions and the singular value decomposition! I also make an explicit connection between classic multidimensional scaling and PCA, because I was never able to find a satisfying reference that did that.

Notebook/Code Here:
https://ctraliedotcom.github.io/CMDS/...

Table of Contents:
00:00 Intro Sequence
00:10 Multidimensional Scaling Motivation
04:34 Matrix Form of Squared Euclidean Distance Matrices
10:32 Double Centering
18:07 Geometric Interpretation of Double Centering
19:25 Solving for HX with Gram Eigendecomposition
23:37 Properties of Solution US^{1/2}
27:16 Coding Up Classical Multidimensional Scaling (CMDS)
35:58 Principal Component Analysis (PCA) And Projected Variance
41:58 Maximizing Projected Variance
48:26 SVD Connection Between PCA and CMDS
56:23 Cleaning up CMDS code
59:20 Non-Euclidean Distance Matrices / Sphere Example
1:09:00 Academic Subject Similarities
1:12:49 Ranked-Choice Voting Similarities
1:24:50 Bending Invariant 3D Shape Representations
1:35:07 p-Stress
1:38:45 Solving/Optimizing p-Stress in PyTorch
1:49:00 p-Stress on Ranked-Choice Voting
1:53:57 p-Stress on 3D Shapes
1:55:44 Adding anchors to fix points
2:06:20 Masking for nonrigid deformations



References:
Elad, Asi, and Ron Kimmel. "Bending invariant representations for surfaces." Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001. Vol. 1. IEEE, 2001.

Heat method for geodesic distances:
https://www.cs.cmu.edu/~kmcrane/Proje...

Kendall-Tau Distance:
https://ursinusdatastructures.github....