multidimensional triangulation based on non-Euclidean distances from landmarks

Question of a naïve experimental biologist to data scientists: How do I determine the relative or absolute positions of many multidimensional points, when I only know their non-Euclidian distances to many likewise multidimensional landmark points (in MATLAB)?

The question is related to the landmark multidimensional scaling method (Silva & Tenenbaum, 2004), which I have some trouble to implement. Also, I am unsure whether landmark MDS would even work with non-Euclidian distances (i.e., correlation distance). If that sounds naive, I already admitted so.

Answer 1

[Yash Sharma]

Hi Philipp,

Landmark MDS can work with non-Euclidean distances, such as correlation distances. However, it's important to note that the classical MDS assumes Euclidean distances, so when using non-Euclidean distances, one typically uses a variant of MDS known as non-metric MDS.

Here's a conceptual outline of how you might implement landmark MDS in MATLAB using non-Euclidean distances:

1. Select Landmarks: Choose a subset of your points to be landmarks. The choice of landmarks can be random, uniform, or based on some heuristic.
2. Compute Distance Matrices: Calculate the distance matrix between landmarks and between each point and the landmarks. Since you mentioned correlation distance, you can use MATLAB's pdist function with the 'correlation' option.
3. Classical MDS on Landmarks: Apply classical MDS to the landmarks to find their positions in the lower-dimensional space.
4. Map Remaining Points: Use the positions of the landmarks and the distances of the remaining points to the landmarks to estimate the positions of the remaining points in the lower-dimensional space.

Here is a MATLAB example that demonstrates these steps with a correlation distance matrix:

% Step 1: Select landmarks
% Assuming 'data' is your original high-dimensional data
numLandmarks = 10; % Or any other number you choose
landmarkIndices = randperm(size(data, 1), numLandmarks);
landmarkData = data(landmarkIndices, :);

% Step 2: Compute distance matrices
landmarkDists = pdist(landmarkData, 'correlation');
D_XL = pdist2(data, landmarkData, 'correlation');

% Step 3: Classical MDS on landmarks
% Convert distance matrix to a square form and apply MDS
landmarkDistsSquare = squareform(landmarkDists);
[Y_landmarks, ~] = cmdscale(landmarkDistsSquare);

% Step 4: Map remaining points
% This step involves optimization, and you might need to implement a
% stress minimization algorithm or use an existing MDS function that
% supports non-metric distances. MATLAB's mdscale function can be used for
% non-metric MDS.
[Y, stress, disparities] = mdscale(D_XL, 2, 'Criterion', 'stress', 'Start', Y_landmarks);

% 'Y' contains the positions of all points in the lower-dimensional space

Please note that the mdscale function with the 'stress' criterion is used for non-metric MDS, which is appropriate for non-Euclidean distances. The 'Start' parameter is set to the positions of the landmarks obtained from the classical MDS step to provide a good starting point for the optimization.

This is a simplified example, and the actual implementation may require additional considerations based on the specifics of your data and the desired outcome.

Please find below some documentation which will be helpful in your implementation:

• randperm: https://www.mathworks.com/help/matlab/ref/randperm.html
• pdist: https://www.mathworks.com/help/stats/pdist.html
• pdist2: https://www.mathworks.com/help/stats/pdist2.html
• squareform: https://in.mathworks.com/help/stats/squareform.html
• cmdscale: https://www.mathworks.com/help/stats/cmdscale.html
• mdscale: https://www.mathworks.com/help/stats/mdscale.html

Hope it helps!