multidimensional triangulation based on non-Euclidean distances from landmarks

8 views (last 30 days)
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.

Answers (1)

Yash Sharma
Yash Sharma on 18 Jan 2024
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:
Hope it helps!

Categories

Find more on Dimensionality Reduction and Feature Extraction in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!