How can classical multidimensional scaling go wrong?
Authors: Rishi Sonthalia
Greg Vanbuskirk
Benjamin Raichel
Anna Gilbert
Venue: NeurIPS 2021 Poster (2021)
Keywords: Dimensionality reduction
spectral analysis
multidimensional scaling

Abstract: Given a matrix $D$ describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of its performance on non-Euclidean metrics is lacking. 

In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from $D$, for the Frobenius norm of the difference between $D$ and the metric $D_{\text{cmds}}$ returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has a significant number of negative eigenvalues, then $\|D-D_{\text{cmds}}\|_F$, after initially decreasing, will
eventually increase as we increase the dimension. Hence, counterintuitively, the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases as we increase the dimension for a variety of non-Euclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1-nearest neighbor) and complex (e.g., multi-layer neural nets) classifiers decreasing as we increase the embedding dimension.

Finally, our analysis leads us to a new efficiently computable algorithm that returns a matrix $D_l$ that is at least as close to the original distances as $D_t$ (the Euclidean metric closest in $\ell_2$ distance). While $D_l$ is not metric, when given as input to cMDS instead of $D$, it empirically results in solutions whose distance to $D$ does not increase when we increase the dimension and the classification accuracy degrades less than the cMDS solution.  

How can classical multidimensional scaling go wrong?
Rishi Sonthalia University Michigan rsonthal @umi ch. edu
Gregory Van Buskirk University of Texas - Dallas greg. vanbuskirkk@ttallles edu
Benjamin Raichel University of Texas Dallas Benj amin. Rai baicheloe @uthalll edu
Anna C. Gilbert
Yale University
anna. ama..ilbert@@alee edu edu
Abstract
Given matrix D describing the pairwise dissimilarities of data set, common task is to embed the data points into Euclidean space. The classical multidimen- sional scaling (cMDS) algorithm is widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of non-Buclidean metrics is lacking.
its performance
In this paper, we derive a formula, based on the eigenvalues of matrix obtained from D. for the Frobenius norm of the difference between D and the metric Demds returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has significant number of negative eigenvalues, then [D - Deautslle FI after initially decreasing, will eventually increase as we increase the dimension. Hence, counterintuitively. the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases
increase the dimension for variety of non non-Euclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1-nearest neighbor) and complex (e.g., multi-layer neural nets) classifiers decreasing as we increase the embedding dimension.
Finally, our analysis leads us to a new efficiently computable algorithm that returns matrix D; that is at least as close to the original distances as D, (the Euclidean metric closest in lz distance). While Dj is not metric, when given as input to cMDS instead of D, it empirically results in solutions whose distance to D does not increase when we increase the dimension and the classification accuracy degrades less than the cMDS solution.
Introduction
Multidimensional scaling (MDS) refers to a class of techniques for embedding data into Euclidean space given pairwise dissimilarities [Carroll and Arabie 1998 Borg and Groenen 2005). Apart from the general usefulness of dimensionality reduction, MDS has been used in a wide variety of applications including data visualization, data preprocessing, network analysis, bioinformatics, and data exploration. Due to its long history and being well studied, MDS has many variations such as
non-metric MDS [Shepard] 1962a bj. multi-way MDS [Kroonenberg 2008 multi-view MDS [Bai
ct al. 2017]. confirmatory or constrained MDS (Heiser and Meulman 1983] etc. (See France and Carrol
2010
Cox and Cox 2008 for surveys).
The basic MDS formulation involves minimizing an objective function over a space embeddings. There two main objective functions associated with MDS: STRESS and STRAIN.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The STRAIN objective (Equation 1 below) was introduced by Torgerson 1952 whose algorithm to solve for this objective now commonly referred as the classical MDS algorithm (cMDS).
x - VDV 2
Xends == arg min
(1)
X
Here V is the centering matrix given by V = JJ and I is the identity matrix and J is the matrix of all ones. cMDS first centers the squares of the given distance matrix and then uses its spectral decomposition to extract the low dimensional embedding. cMDS is one of the oldest and most popular methods for MDS, and its popularity is in part due to the fact that this decomposition is fast and can scale to large matrices. The point set produced by cMDS, however, is not necessarily the point set whose Euclidean distance matrix is closest under say Frobenius norm to the input dissimilarity matrix. This type of objective is instead captured by STRESS, which comes in a variety of related forms. In particular, in this paper we consider the SSTRESS objective (see Equation 2
Specifically, given an embedding X, let (XM be the corresponding Euclidean distance matrix, that is EDM(XXi; Dig ||X;; X,lli. where X,, X, are the ith and jth columns of X. If D is dissimilarity matrix whose entries are squared, then we are interested the matrix,
D := arg min D"=
(2)
Note that the reason we assume our dissimilarity matrix has squared entries is because the standard EDM characterizations uses squared entries (see further discussion of EDMs below). Equation is
well studied objective [Takane et al. 1977 Hayden and Wells 1988 Qi and Yuan 2014
There are a number of similarly defined objectives. If one considers this objective when the matrix entries are not squared (i.e. / D'J - DDs)), then is referred to as STRESS. one further normalizes
each entry of the matrix difference by the input distance value (i.e. (v Pij (Piy-VDi) / Piy) then it called Sammon Stress. In this paper, we are less concerned with the differences between different types of Stress, and instead focus on how the cMDS solution behaves generally under a Stress type objective. Thus for simplicity we focus on SSTRESS. It is important to note that there are algorithms to solve the SSTRESS objective, but the main drawback is that they are slow in comparison to cMDS Takane et al. 1977 Hayden and Wells, 1988 Qi and Yuan 2014). Thus, many practitioners default to using eMDS and do not optimize for SSTRESS.
In this paper, we shed light on the theoretical and practical differences between optimizing for these two objectives. Let Demds := (DDM(Xmadee where Xemas is the solution to Equation ! and let D, be the solution to Equation We are interested in understanding the quantity
err :=
| D Demasll 1
(3)
Doing so will provide practitioners with multiple advantages and will guide the development of better algorithms. In particular,
1. Understanding err is the first step in rigorously quantifying the robustness of the cMDS algorithm.
2. If err is guaranteed be small, then we can use the cMDS algorithm without having to worry about loss in quality of the solution.
3. If err is big, we can make an informed decision about the benefits of the speed of the cMDS algorithm versus the quality of the solution.
4. Understanding when err is big helps us design algorithms to approximate D; that perform better when cMDS fails.
Contributions. Our main theorem, Theorem I decomposes err into three components. This decomposition gives insight into when and why cMDS can fail with respect to the SSTRESS objective. In particular, for Euclidean inputs, err naturally decreases as the embedding dimension increases. For non- Euncliide inputs, however, our decomposition shows that after an initial decrease, counterintuitively err can actually increase as the embedding dimension increases. In practice one may not know priori what dimension to embed into, though one might assume it suffices to embed into some sufficiently large dimension. Importantly, these results demonstrate that when using cMDS to embed, choosing a dimension too large can actually increase error.

---

This degradation of the cMDS solution is of particular concern in relation to the robustness in the presence of noisy or missing data, as may often be the case for real world data. Several authors [Cayion and Dasgupta 2006 Mandanas and Kotropoulos) 2016 Forero and Giannakis) 2012 have proposed variations to specifically address robustness with eMDS. However, our decomposition of err, suggests novel approach. Specifically, by attempting to directly correct for the problematic term in our decomposition (which resulted in err increasing with dimension) we produce a new lower bound solution. We show empirically that this lower bound corrects for emr increasing, both by itself and when used as a seed for cMDS, Crucially the running time of our new approach comparable to cMDS, rather than the prohibitively expensive optimal SSTRES solution. Finally, and perhaps more importantly, we show that if we add noise or missing entries to real world data sets, then our new solution outperforms cMDS in terms of the downstream task of classification accuracy, under various classifiers. Moreover, our decomposition can be used to quickly predict the dimension where the increase in might occur.
The main contributions of our paper are as follows.
1. We decompose the error in Equation & into three terms that depend on the eigenvalues of matrix obtained from D. Using this analysis, we show that there is term that tells us that as we increase the dimension that we embed into, eventually, the error starts increasing.
2. We verify, using classification as downstream task, that this increase the error for cMDS results in the degradation of the quality of the embedding, as demonstrated by the classification accuracy decreasing.
3. Using this analysis, we provide an efficiently computable algorithm that returns matrix Dj such that if D, is the solution to Equation
P then [| r S Dr D[[r, and
empirically we see that D De S Dends Dalle.
4. While D; is not metric, when given as input to cMDS instead of D, it results in solutions that are empirically better than the cMDS solution. In particular, this modified procedure results more natural decreasing of the error as the dimension increases and has better classification accuracy.
2 Preliminaries and Background
In this section, we lay out the preliminary definitions and necessary key structural characterizations of Euclidean distance matrices.
cMDS algorithm. For completeness, we include the classical multidimensional scaling algorithm in Algorithm
Algorithm I Classical Multidimensional Scaling.
1: function CMDS(D,
2:
= *D* V/2
3:
Compute μ1 2 ... Hr 0, U the eigenvalues and eigenvectors of X
4:
return (iigg, / .......)
EDM Matrices
Definition 1. D E &R'x is a Euclidean Distance Matrix (EDM) if and only if there exists a d E N such that there are points T1.... In E Rdd with
Di -1:--1;11
Note that unlike other distance matrices, an EDM consists of the squares of the (Euclidean) distances between the points.
This form permits several important structural characterizations of the cone of EDM matrices.
1. Gower 1985
Schoenberg
[935 show that a symmetric matrix D is an EDM if only if
F (I 1s ) -11 s
is positive semi-definite matrix for all such that 1 s and Ds + 0.
3

---

2. Schoenberg 1938] showed that D is an EDM if and only if exp(-XD) is a PSD matrix with is along the diagonal for all 0. Note here exp is element wise exponentiation of the matrix.
3. Another characterization is given by Hayden and Wells (1988) in which D is an EDM if and only if D is symmetric, has Os on the diagonal (i.e., the matrix is hollow), and D is negative semi-definite, where is defined as follows
D f QDQ = fr E
(4)
Here f is vector and
Q Q=
uv for V = [1...., ,,.,,,,,,,, 1, vn"
(5)
u. v
Note Q is Householder reflector matrix (in particular, it's unitary) and it reflects a vector about the hyperplane span(u)'.
The characterization from Hayden and Wells 1988 the main characterization that we shall use. Hence establish some important notation.
Definition 2. Given any symmetric matrix RRxn, let us define À E R==1xn-1, (asiixxnn,[[AA) E R=-1 and {(A) E IR as follows
A
f(A)
QAQ
(AA) E(A)
addition to characterizations of the EDM cone, we are also interested the dimension the EDM Definition 3. Given EDM D, the dimensionality of D is the smallest dimension d, such that there exist points TI,...,
Fn E IRd with Dig = || x,112 11
Let E(r) be the of EDM matrices whose dimensionality is at most
Using Hayden and Wells 1988 's characterization of EDMs, Qi and Yuan 2014 show E ((r) and only if D is symmetric, hollow (i.c., Os along the main diagonal), and D in Equation is negative semi-definite with rank at most
Conjugation matrices: Q and V. Conjugating distance matrices either by Q (in Equation 5 or by the centering matrix V is important component of understanding both EDMs and the cMDS algorithm. We observe that V is also (essentially) a Householder matrix like Q. Let w = [l....,1] 1|7
and observe that www that V =
www.
Qi and Yuan 2014 establishes an important connection between Q and V that we make use of in our analysis in Section Specifically, for any symmetric matrix A, we have that
A o 0
0
VAV = Q
Q.
(6)
Here Å is the matrix given by Definition
This connection gives a new framework which we We know that given D, cMDS first computes -VDV/2.
2
can understand the cMDS algorithm.
D Q/2. Thus, when cMDS computes the spectral _
Using Equation 6 this is equal to -Q
decomposition of VDV/2, this is equivalent of computing the spectral decomposition of Đ. Then using the characterization of E(r) from Qi and Yuan [2014]. setting all but the largest r eigenvalues might seem like the optimal solution. However, this procedure ignores condition that the matrix must be hollow. As we shall show, this results in sub-optimal solutions.
3 Theoretical Results
Throughout this section we fix the following notation. Let D be distance matrix with squared entries. Let be the dimension into which we are embedding. Let X S S An-1 be the eigenvalues of D and U be the eigenvectors. Let À be n-dimensional vector where X; A, or i>r for

---

U
== 1 and Xn 0. Let S Q+
Let D, be the solution to Problem 2 and Dends
0
the resulting EDM from the solution to Problem
Let
nl[(S o S)Al -
Ci G= G=E x C2 -= -
Σ
A
C3
2
Then the main result of the paper is the following spectral decomposition of the SSTRESS error.
Theorem 1. If D is a symmetric, hollow matrix then, || Demds - DII? = C1 + Cj + C3.
The idea behind the proof of Theorem iss to decompose D = 1IQ cmdss Q Q
[Dedds
D Demnds/213 -
2I) f(D (Demms))ll..
which follows from Definition 2 We relate each of these three terms C1. C2. and C3. The following lemmas will work towards expressing each of these terms separately. In the following discussion, let
Y, := Xemds Xemdss and recall that Xemds is the solution to the classical MDS problem given in Equation !
The proofs for the following lemmas in the appendix.
Lemma 1. IfG is a positive semi-defiiite Gram matrix, then IV EDM G
0
Lemma 2. The value of the objective function obtained by Xemds in Equation
G. Specifically,
we have that A - (-VDV)/215
Σ =1-
Lemma 3. - D = Pp.
2
n-
Lemma 4. IfTr(D) = 0, then (E(D) (SG(D)-(DDeess {(Demas))
Σ 1=1
\
= C.C..
(S (S o S) - - C3-
Lemma 5. If D is hollow, then 2lI - -f 3(Demdss)
2
The first term in the error is C1. From the definition, eigenvalues of î corresponding to eigenvectors that not used (or are discarded) in the cMDS embedding. As we increase the embedding dimension, we use more eigenvectors. Hence as the embedding dimension increases, we see that C₁ monotonically decreases. In the case when D is an EDM, we can use all of the eigenvectors so this term will to zero. On the other hand, if D is not an EDM and Đ has positive eigenvalues (i.e. negative eigenvalues of -VDV), then these are cigenvalues that correspond eigenvectors that cannot be used. Thus, cMDS will always exhibit this phenomenon for Ci regardless of the input D (for both STRAIN and SSTRESS).
see C1 is the sum of the squares of the
The second term is C3. This term looks similar C1, but instead of summing the eigenvalues squared, we first sum the eigenvalues and then take the square. This subtle difference has big impact. First, we note that increases, C2 becomes more negative. Suppose that not an EDM, (i.e., D has positive eigenvalues) and let K be the number of negative eigenvalues of D. Then, since D has trace O, when r = K, C2 is negative. Hence, C2 decreases and is eventually negative increases which implies that as r increases, there certain value of after which C. increases. This results in the quality of the embedding decreasing. As we will see, this term will be the dominant term in the total error.
While O and C2 are simple to understand, C3 is more obtuse. To simplify it, we consider the following. If 8 an entry of random n by unitary matrix, then as n goes infinity the distribution for 8 svn converges to (0, 1) and the total variation between the two distributions is bounded above by 8/(n- 2) Easton 1989 Diaconis and Freedman, 1987.. Therefore, we can assume that the variance of an entry of random by orthogonal matrix is about 1/n. So, heuristically. So S 1 11"" and
n S)AIE ~ 12 n² 111T>
n 1 C².
5

---

Then since C3 of C3 is dominated by C2.
(8o8)) p- 02
C2-
we see that, least heuristically, the overall behavior
Algorithm 2 Lower Bound Algorithm.
function LOWER(D, r)
2: Compute D, [D) and E(D).
3: Compute A _ ... I A U as the eigenvalues and eigenvectors of ò E(D)
4: Initialize G X; and
5: Let negative_Co C2 0.
6:
for i 1.
do
7:
if 2 > or i > then
8:
negative C2 += X
9:
Set & to 0
10:
E = number c's not equal to 0
11:
sub = negative_C2,
12:
for = 1... n do
13:
if Cn-, = then
14:
Ca-it + sub 2 0 then
15:
G-t += sub, E - 1, negative_C, sub
16:
else
- L, negative += Cn-1, sub negative_CC C2/E
18:
c- 0
19:
Gn += sub, negative C2 - sub
20:
Let D U diag(A (o.g( Cn-1 U
D
S(D)
21:
return Q F(DD)
+Q
On
From the previous discussion, we see that the C2 term in the decomposition is the most vexing due to the term (g(D) - E ((Demds))² This term is from the excess the trace; that is, the result of discarding the cigenvalues changes the value of the trace from 0 to non-zero. From Lemma S that cMDS projects - f2/2 onto the cone of PSD matrices (which do not necessarily have trace 0). To retain the trace condition, we perform the following adaptation. Let n(r) be the space of symmetric, trace matrices A, such that À is negative semi-definie of rank at most r and project D onto wrr) instead. That is, we seek a solution the following problem.
D1 == arg min A DIE AEr(r)
Clearly this problem is strict relaxation of the SSTRESS MDS problem and hence get that
| - D 2 - D
Because no longer require the solution to be hollow, conjugating by S permits us to rewrite Problem f as:
C = arg min
Σ (a Xz)² (c, - E(D))
(8)
CER" 1==0 1=1
Vn>i, s0. Vn>j2r, 4==0
Theorem 2. is the solution Problem R and Dj the solution problem Aand if we let
M be the n 1 by n diagonal matrix with the first n terms of e on the diagonal, then
M
F(D)
STD S(D)
Ca
Unlike Problem 2 Problem 8 can be solved directly. We do so via Algorithm We see that in r to ensure the proper constraints on
the first loop (lines 6-9), we set 6; to be 0 if X; > we incur cost of C.. That is, we sum the squares of those
(i.e., the eigenvalues). Doing eigenvalues. Now the solution after line 9 does not necessarily satisfy cf1 0. fact, this stage
of the algorithm, have that c C2 and we have E many c's that are non zero that we can

---

adjust. That is, we modify these entries on average by C2/E. Because we use a Frobenius norm to measure error, this incurs a cost of C C2 / E. Finally, we note that the major computational step of the algorithm is the spectral decomposition. Hence it has comparable run time to cMDS.
Theorem 3. If D is a symmetric, hollow matrix, then Algorithm computes Dr the solution to 7 in O(n") time.
Proposition If D a symmetric, hollow matrix, then
|| - 2 C2 r ++1
C1
It is important to note that Dj is not a metric. However, if we want an EDM and hence an embedding. we can use Dj as the input to cMDS algorithm. Noting that Dj is negative semi-definite matrix of rank at most r, we see that if Diands is the metric returned by cMDS on input Dj, then we have that [| Diemdsll ? fD) f(Diemds) )l = 2D) [DDemdd I Similar to Lemma 5 we
get the following result.
nl((S e S)cl?
C2
Lemma 6. 2II - ((((D)-~(DDeaaa) 5(Diemds)
=: C:
2
Using Lemma
o
that
Diemdss Dl12 < Diemds Dill2 p + Di D
$ (D(mmds))
f(Di)1 + +ID,, - DII
n n|(SS S)
c²
DDiomaa - D1 11; - -DI
r+l C₁
2
On the other hand, we upper bound Demda difference, we get
D1
||Dr D1 using Proposition | Taking the
Demds D1E [D DI < r+1 C3
Using our heuristics for C33 and C4, we expect Demds to be be much further from Dr, than Diemds- These claims are experimentally verified in the next section.
Solving Equation 2 Another approach would be to solve Equation 2 directly. However, solving this problem is much more computationally expensive and works such Qi and Yuan [014 present new algorithms to do so. Algorithm 2 can be used to compute the solution as well. Here we Dykstra's method of alternating projections as Hayden and Wells 1988) do, but instead of only projecting i on the cone of negative semi definite matrices, without any rank constraint, project onto k(r) using Algorithm 2 The second, projection is then onto the the space of hollow matrices. Alternating these projections gives an iterative method compute D..
uP
12a4
E2 acuadd
C7 scuaee
123
8 10
1071
1122
10p
101
10f
200
663
600
20
1.0
120
50
100
2.5
Urmemson
Limersion
Ulmension
(a) Portugal
(b) Isomap with heart
(c) Perturbed with SNR 3.24
Figure I: Plots showing the cMDS error as well as the three terms that we decompose the error into. For the perturbed EDM input, this is error with respect to the perturbed EDM.
4 Experiments
In this section, we two things. First, we empirically verify all the theoretical claims. Second, we show that on the downstream task of classification, if we use cMDS to embed the data, then the
7

---

CMEES Loms
CHESS Lowar Vrue
cMSS
10f
Lowa
meeaive St
1800
10
123
Ialltive
3350
The
10
to:10
12'45
wr15
Dimersion
Dimersion
Uimerskon
(a) Portugal
(h) Isomap with Heart
(c) Perturbed Input
10/1
LMSc Lower
10"1
Lowe
Lower
Releve 52
160
Nededww SE
Rederive
10
k0
10
0
25
50
300
120
50
300
130
200
250
30
Olieesiin
Dimendion
(d) Perturbed Original
(e) Celegans
(f) Heart
Figure 2: Plots showing the relative squared error of the solutions with respect to the input matrix. For the perturbed EDM imput, we show the relative squared error with respect to the original EDM (figure (d)) and the perturbed EDM (figure (c)). For the Portugal data set, we couldn't 't compute the true solution due to computational restraints.
embedding dimension increases, the classification accuracy gets worse Thus, suggesting that the embedding quality of cMDs degrades.
Verifying theoretical claims. To do this, we look at three different types of metrics. First, are metrics that come from graphs and for these we use Celegans Rossi and Ahmed (2055) and Portugal Rozemberczki et al. [2019] datasets. Second, are metrics obtained in an intermediate step of Isomap. Third, are perturbations of Euclidean metrics. For both of these metrics we use the heart dataset Detrano et al. (1899.. In all cases, we show that the classical MDS algorithm does not perform as previously expected; instead, it matches our new error analysis. In each case, we demonstrate that our new algorithm Lower + cMDS outperforms cMDS in relation to SSTRESS.
Results. First, let us see what happens when we perturb an EDM. Here we consider two different measures. Let D be the original input, and D, be the perturbed. Then we measure
Dp Demes 12 and |D- - Demasll? 11
D
|
As can see from Figure an 2d as the embedding dimension increases both quantities eventually increase. The increase in the relative SSTRESS as we predicted theoretically. The increase in the second quantity suggests that cMDS does not do good job of denoising either. This suggests that the cMDS objective is not good one.
Next, we see how cMDS does graph datasets and with Isomap on Euclidean data. Here we plot the relative squared error ()) [I Demdssll: 1/ D Figure 2 shows that, as predicted, as the embedding dimension increases, the cMDS error eventually increases well. For both the Portugal dataset alone and with Isomap on the heart dataset, this error eventually becomes worse than the error when embedding into two dimensions! As can see from Figure I this increase is exactly due to the C term. Also, as heuristically predicted, the C3 term is roughly constant.
Let us see how the true SSTRESS solution and new approximation algorithm perform. We look at the relative squared error again. First, Figure shuuss shows us that our lower bound tracks the true SSTRESS solution extremely closely. We can also see from Figure 2d that the true SSTRESS solution and the Lower + cMDS solution are closer to the original EDM compared to the perturbed matrix. Thus, they are better at denoising than cMDS. Finally, we see that our new algorithm Lower + cMDS performs better than just eMDS and, most cases, fixes the issue of the SSTRESS error increasing with dimension. We also see that Diemds D
Dr D1 is also roughly constant.
8

---

We point out cMDS and Lower+cMDS have comparable rumning times as they can respectively be computed with one or two spectral decompositions. Computing D, requires computing a spectral decomposition in every round, with larger datasets requiring hundreds of rounds till they appear to converge. This is a significant advantage of Lower+cMDS over True, and also the reason we were not able to compute True for the Portugal dataset above, and the classifications experiments below.
Classification. For the classification tasks, we switch to more standard benchmark datattets: MNIST, Fashion MNIST, and CIFAR 10. If we treat each pixel as a coordinate then these datasets are Euclidean and we cannot demonstrate the issue with cMDS. We obtain First, we compute the Euclidean metric and then perturb it with a symmetric, hollow matrix whose off diagonal entries are drawn from a Gaussian. Second, we construct a nearest neighbor graph and then compute the all pair shortest path metric on this graph. This is the metric that Isomap tries to embed using cMDS. Third, we imagine each image has missing pixels and then compute the distance between any pair of images using the pixels that they have in common (as done in Balzano et al. 2010), Gilbert and Sonthalia (018 ). Thus, we have 9 different metries to embed. For each dataset, we constructed all 3 metrics for the first 2000 images. We embedded each of the nine metries into Euclidean space of dimensions from I to 1000 using cMDS and our Lower + cMDS algorithm. We do not embed by solving Equation 2 as this is computationally expensive. For each embedding, we then took the first 1000 images are training points and trained a feed-forward 3 layer neural network to do classification. Results with nearest neighbor classifier are in the appendix. We then tested the network on the remaining 1000 points. We can see from Figure E that as the embedding dimension increases, the classification accuracy drops significantly when trained on the cMDS embeddings. On the other hand, when trained on the Lower + cMDS embeddings, the classification accuracy does not drop, or if it degrades, it degrades significanlly less. Thus, showing that the increase in SSTRESS for cMDS on non Euclidean metrics, does result in a degradation of the quality of the embedding and that our new method fixes this issues to large extent.
Euclidean metrics in three ways.
Messnng NN MNST
Messing SN FRNNST
Mosingg MN Offi110
0.70
0.50
0.55
Aecuraay
3.77
AACUF
0.24
3:50
0925
0.21
DM25
03
250
1000
252
75c
1000
250
120
1000
Limensioo
Dimersion
(a) Missing Data- MNIST
(b) Missing Data- FMNIST
(c) Missing Data- CIFARIO
Eomap RANST
komap NN
325
23
0.25
3..0
200uracy
024
3.0
0.2
Bwer cVO5
0.22
Steer
04
Dimeneioo
meroson
Dimersion
(d) Isomap- MNIST
(e) Isomap- FMNIST Perturted TVRETT
(I) Isomap- CIFARIO
Parti bed NN NAIT
Perrurbed NJ CPer10
0.000
35
0.775
Acaarac
03
0H65
dHD5
0,00
-9035
02
JMDD
leser LMMS
bwvor
200
500
750
1000
203
500
750
1000
202
500
1000
Dimaniioo
Dimendson
Climans
(g) Perturbed MNIST
(h) Perturbed FMNIST
(i) Perturbed CIFARIO 10
Figure Plots showing the classification accuracy for 3 layer neural network.
9

---

Acknowledgements
Work on this paper by Gregory Van Buskirk and Benjamin Raichel was partially supported by NSF CAREER Award 1750780.
References
Phipps Arabie, Mark S Aldenderfer, Douglas Carroll, and Wayne DeSarbo. Three Way Scaling: Guide Multidimensional Scaling and Clustering. volume 65. Sage, 1987.
Song Bai, Xiang Bai, Longin Jan Latecki, and Qi Tian. Multidimensional scaling multiple input distance matrices. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Laura Balzano, Robert Nowak, and Waheed Bajwa. Column subset selection with missing data. 2010.
Ingwer Borg and Patrick JF Groenen. Modern multidimenssonal scaling: Theory and applications. Springer Science & Business Media, 2005.
J Douglas Carroll and Phipps Arabie. Multidimensional scaling. Measurement, judgenn and decision making, pages 179-250, 1998.
J Douglas Carroll and Jih-Jie Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of "eckart-young" decomposition. Psychometrika, 35(3):283-319, 1970.
Lawrence Cayton and Sanjoy Dasgupta. Robust euclidean embedding. In Proceedings of the 23rd international conference machine learning, pages 169-176, 2006.
Michael AA Cox and Trevor F Cox. Multidimenssinal scaling. In Handbook of data visualization, pages 315-347. Springer, 2008.
Chandler Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970. doi: 10.1137/0707001. URL https:///ooi http///i..rg///// org/10 1137/0707001
R. Detrano, A. Jánosi, W. Steinbrunn, M. Pfisterer, J. Schmid, S. Sandhu, K. Guppy, S. Lee, and V. Froelicher. International application of new probability algorithm for the diagnosis of coronary artery disease. The American journal of cardiology, 64 5:304-10, 1989.
Persi Diaconis and D. Freedman. A dozen de finetti-style results in search of a theory. Annales De L Institut Henri ciincar-probabillic Et Statistiques, 23:397 -23, 1987.
Daniel B. Dias, R. B. Madeo, Thiago Rocha, H. Bíscaro, and M. Peres. Hand movement recognition for brazilian sign language: A study using distance based neural networks. 2009 International Joint Conference on Neural Networks, pages 697-704, 2009.
Thomas Dietterich, Jain, Lathrop, and Tomas Pezzano-Perez A comparison of dynamic reposing and tangent distance for drug activity prediction. In NIPS, 1993.
I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli. Euclidean distance matrices: Essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6):12 30. 2015.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt:://archive.ttt uci edu/ml
Morris L. Easton. Chapter 7: Random orthogonal matrices, volume Volume 1 of Regional Conference
Series in Probability and Statistics, pages 100-107. Institute of Mathematical Statisties and American Statistical Association, Haywood CA and Alexandria VA, 1989. doi: /0.12m//cbss/ 1462061037. URL https://::/// http:::://ooi.o//0//// org/o0..//.. /214/cbms. 01011111224///mmmm166615133333 1142/610122277
Evett and E. Spiehler. Rule induction in forensic science. Knowledge Based Systems, pages 152-160, 1989.
10

---

Pedro A Forero and Georgios B Giannakis. Sparsity-exploitnng robust multidimensional scaling. IEEE Transactions on Signal Processing. 60(8):4118-411 2012.
Stephen L France and Douglas Carroll. Two-way multidimennsonal scaling: review. IEEE Transactions Systems, Man, and Cybernetics, Part C (Applications and Reviews), 41(5):644- 661, 2010.
Anna C. Gilbert and Rishi Sonthalia. Unsupervised metric learning in presence of missing data. pages 313-321, 2018. doi: 10.110%/LLERTON2201.... 88355555.
W. Glunt, T. L.. Hayden, S. Hong, and J. Wells. An alternating projection algorithm for computing the nearest Euclidean distance matrix. SIAM J. Matrix Anal. Appl.. 1 ((4))589-66)) 1990. ISSN 0895-4798, doi: 10.1137/0611042 URL https:///oi..rg///
1137 137/0611042
R. Gorman and T. Sejnowski. Analysis of hidden units in layered network trained classify sonar targets. Neural Networks, 1775-89,0 1988.
J. C. Gower. Euclidean distance geometry. Math. Sci., 7(1):1-14, 1982. ISSN 0312-3685.
J.C. Gower. Properties of euclidean and non-cuclidean distance matrices. Linear Algebra and its Applications, 07:81-97,jju 1985, doi: 1011016/022-375555501117749
H. A. Guvenir, B. Açar, G. Demiroz, and A. Çekin. supervised machine learning algorithm for arrhythmia analysis. Computers in Cardiology 1997, pages 433-436, 1997.
T.L. Hayden and Jim Wells. Approximation by matrices positive semidefinite a subspace. Linear Algebra and its Applicatioons, 109:115 130, 1988. ISSN 0024-3795. doi: https://do..rr//00 374-002244-79555888000007 p:1/00243796889022299
Willem Heiser and Jacqueline Meulman. Constrained multidimensional scaling, including confir- mation. Applied Psychological Measurement, 7(4):381-40 1983.
D. Kleinman and M. Athans. The design of suboptimal linear time-varying systems. IEEE Transac- fions Automatic Control, 13(2))150-159 1968.
Pieter M Kroonenberg. Applied multiway data analysis, volume 702. John Wiley & Sons, 2008
Monique Laurent. connection between positive semidefinite and euclidean distance matrix comple- tion problems. Linear Algebra and its Applications, 273(1):9 - 22, 1998. ISSN 0024-3795.
Fotios D Mandanas and Constantine L KKorropoulos Robust multidimensional scaling using a maximum correntropy criterion. IEEE Transactions on Signal Processing, 6594)9919993, 2016.
E. Million. The hadamard product elizabeth million april 12 2007 introduction and basic results. 2007.
Hou-Duo Qi and Xiaoming Yuan. Computing the nearest euclidean distance matrix with low embedding dimensions. Mathematical Programming. 147(1):31--38,, 2014.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL RRLLattp://ettoorrrpooiooo com
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, 2019.
J. Schoenberg. Remarks maurice fréchet's article "sur la définition axiomatique d' une classe d' essaccss distanciés vectoriellement applicable sur l'espace de hilbert". annals of mathematics 36(3, 1935.
I. Schoenberg, Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522-536, 1938. ISSN 00029947. URL httt:tttp///wwwjjstt jstor. org/ Sstable1998950
Roger N Shepard. The analysis of proximities: multidimensional scaling with an unknown distance function. i. Psychometrika, 27(2) 1962a.

---

Roger N Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function. ii. Psychometrika, 27(3):21--46, 1962b.
V. Sigillito, Wing, L. Hutton, and K. Baker. Classification of radar returns from the ionosphere using neural networks. 1989.
Y-H Taguchi and Yoshitsugu Oono. Relational patterns of gene expression via non-metric multidi- mensional scaling analysis. Bioinformatics, 21(6):730-740, 2005.
Yoshio Takane, Forrest, W. Young, and Jan De Leeuw. Nonmetric individual differences multidimen- sional scaling: An alternating least squares method with optimal scaling features. Psychometrika, pages 7-67, 1977.
J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimension- ality reduction. Science, 290 5500:2319 2000.
W. S. Torgerson. Multidimensiinal scaling i: Theory and method. Psychometrika, 17(4):401-419,
1952.
Warren Torgerson. Theory and methods of scaling. 1958.
Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis- theorem for statisticians. Biometrika, 10202)315-323, 04 2014. ISSN 0006-3444. doi: 10.1095/Diome//sv0000. URL https://doi org/ htw../000////m///////////0/
12


Reviews:
[{"review_id": "qHNR70RDxqQ", "reviewer": "Reviewer_BDxF", "summary": "The work shows a scenario that the classical MDS algorithm fails. \"When the derived matrix has a significant number of negative eigenvalues,\" the classical MDS algorithm tends to fail when the number of dimensions increases sufficiently large. Then the work designs an algorithm with improved performance bound and shows the potential on practical applications.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. The writing is good and gives clear explanations and detailed background for derivations, which are beneficial for both experienced and non-experienced readers.\n\n2. The analysis results seems reasonable to me.\n\n3. The resulting algorithm applies the Dykstra's method to iteratively projection onto the space of hollow matrices and achieve a fast solution procedure.\n\nConcerns:\n\n1. In MDS, typically people use a small number of dimensions for embedding. So the scenario of failures described in the paper seems rare, which may limit the practical significance of the results in the work.\n\n2. In literature, there are known issues on the classical MDS. For example from https://en.wikipedia.org/wiki/Isomap, \"following the connection between the classical scaling and PCA, metric MDS can be interpreted as kernel PCA.\" ... \"However, the kernel matrix K is not always Positive Semi-Definite. The main idea for kernel Isomap is to make this K as a Mercer kernel matrix (that is positive semidefinite) using a constant-shifting method, in order to relate it to kernel PCA such that the generalization property naturally emerges.\" Is there any relationship between the paper's finding and this known issue of non-PSDness? How to compare the proposed algorithm and the kernel PCA algorithm? It is preferred to see some discussion on this point in the rebuttal phase.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~4"}, "extra_text": {}}, {"review_id": "jRaBx1YkVRj", "reviewer": "Reviewer_rStB", "summary": "The paper considers the classic embedding method known as multidimensional scaling and focus on the so called STRAIN  and SSTRESS objectives, both designed for embedding a given squared distance matrix into a lower dimensional space, often for visualization, but potentially also for reducing problem size for downstream tasks. \n\nThe idea is that the SSTRESS is the better objective to optimize as it captures how well the distances of the embedded data points approximate the input distances, but computationally hard, so maybe it is enough to just use the solution for the simpler STRAIN objective, that boils down to Singular Value Decomposition and that may work fine.\n\nThe paper analyzes the solution of STRAIN in terms of the more relevant SSTRESS objective, and shows a decomposition of the error of the STRAIN solution as measured with the STRESS objective and analyzes this objective to understand what happens.\nThe punchline is that if the input distance matrix is not Euclidian (no data set with these pairwise distances exist in any dimension), then the SSTRESS error of the embedding achieved by optimizing STRAIN can  actually increase with increased embedding dimension. A property that seems counterintuitive as a higher dimension should allow improved embeddings. The paper shows  experimentally that this phenomena actually occurs in practice as well and that the performance is nicely explained by the error decomposition proved and discussed in the paper.\nIn particular the experiments show that the classic Isomap embedding has this issue. \nFurthermore, if these STRAIN embeddings are used for a simple downstream task like standard classification, the results become increasingly worse as the embedding size is increased.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the STRAIN objective may make most sense for Euclidian inputs and the failure is analyzed for non-euclidian, the experiments also show that just adding noise to the input distances may greatly worsen the results of using STRAIN based embeddings.  Based on the error decomposition the authors propose a way to fix the problem with the STRAIN objective, while maining the computational efficiency of the STRAIN method.\nThe fix improves the embedded distances, and improves the results for downstream tasks as the performance decrease significantly less, but it still seems there may better methods if a downstream classification task is the goal, and for me the experiments with the downstream task is more a proof of the failure of the STRAIN method to produce useful embeddings than that the new method is good solution for the dimensionality reduction problem. \n\nIn short, the paper shows that using STRAIN embeddings based for instance on IsoMap or other non-euclidean metrics to make a (semi) low dimensional embedding for instance for  downstream tasks is not good idea and should discourage practitioners from doing so, at least without proper thought. The error decomposition is computable and can be used to gauge into the potential issues with applying the STRESS optimization. \n\n\nTechnically the theoretical results seem sound and interesting and the analysis and result very relevant.\nI think the same is true for the experiments shown in the paper. \n\nA few things that may be improved/changed\n- For the plots the y-axis is different in every plot which makes the pattern look identical on many experiments which cheated the viewer (me)  before I noticed. \n- The claims of roughly constant of C3, C4, ... may be a slight exaggeration but the experiments shown they are clearly lower order so that may be okay. Actually C1 seems just as constant in the experiments. \n- For very low dimensional embeddings it seems interesting things are happening and here it seems that STRAIN may still be useful at least on the data sets considered. Maybe a few comments on why that may be would be helpfull from a geometric or eigenvalue spectra kind of perspective. \n\n\nOverall I think this line of research that explains the performance of well known algorithms is relevant and important. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Nnd81znJcC", "reviewer": "Reviewer_rAum", "summary": "A new decomposition of the classical multidimensional scaling (cMDS) error term is generated and used to get additional insights of the method. \nAs I first came across the draft, I naively thought; “Well, cMDS is extremely well known, how can one innovate on such topic?”. Moreover, the departing justification stating cMDS does not excel in non-linear mappings wasn’t that great; I mean cMDS ASSUMES Euclidean space and linearity so it was no wonder that used out of its natural scope it may be suboptimal. But I am very glad to say that the authors proved my naivety wrong very quickly! There is a very clear contribution, the paper is strongly supported, and reading enjoyable.\n\nSTRENGTHS\n+ The unusual “late comer”. Innovating in a method which is so well known is difficult.\n\nWEAKNESSES\n+ There are some unclear decisions and justifications but it is somewhat contradictory that I’m criticizing this when, I in the place of the authors, I would very likely have proceed equally… Notwithstanding, I’m indicating this below, in case a second thought can be given\n+ There is an unconventional mixture of theoretical claims with experimental testing whereby some “theoretical proofs” are complemented with heuristics verified experimentally, but actually not theoretically proven.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ ln 68-71: These advantages are a bit simplistic (and yet I would claim them equally!). The 3rd one is particularly weak; the error term guides the optimization but it does NOT measure the quality of the solution. The same error value can represent wildly different solutions. A better measure of quality of the embedding is the pairing between embedded vs real distances (analogous to a QQ-plot). And of course, this is not the only one, there are other measures of the quality of a solution e.g. topological stability, etc. \n+ ln 99-101: Ok but this seems a bit circumstantial. Can we guarantee that such relation holds for other tasks? Again, the quality of the embedding cannot be measure from the error.\n+ Perhaps I’m wrong on this but in Definition 1, I think a limit to d is missing, otherwise as long as d=n+1 there will always be a valid solution as one can form the n simplex, and hence every matrix D will eventually be EDM.\n+ ln 216-217: Sorry but this is NOT an analysis of complexity. You are very likely right, but unless you prove it formally or at least empricially, I would suggest to remove claims about running times.\n+ “unconventional mixtures of theoretical claims with experimental testing”;\n  * ln 228: I am unused to accept an heuristic as a part of a theoretical proof, unless the heuristic is itself theoretically proven (at which point, of course it ends being an heuristic).\n  * ln 239: Well, something that is formally proven doesn’t need any additional experimentation, does it?\n+ There is almost no discussion.\n+ There is no conclusions section.\n\n+ It is becoming more and more common to move the proofs to supplementary material, and the authors adhere to this practice. I disclose here that I very much dislike this practice, specially when the proofs are central to the research, and not a complement. Moreover, here the appendix are 7pgs!! If you truly needed 13+7=20pgs to communicate your research then perhaps a conference was not the right target for this research. But having said that, it is of course ultimately the authors decision, and I’m just being a grumpy old man! Please ignore my outburst, and proceed as you please.\n+ I have been unable to inspect the code in detail as it seems to be in Julia (JLD) which is a language I do not master. Sorry.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not included, but limitations of cMDS are well known and I do not think any evaluation of the societal impact is needed for this research.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}, {"review_id": "33uVSjCEHWg", "reviewer": "Reviewer_f18Z", "summary": "The authors study the problem of multidimensional scaling (MDS) for embedding data into Euclidean space and perform a theoretical error analysis of the classical muldimensional scaling (cMDS) algorithm. Their main result decomposes the error of cMDS into 3 components, which they use to explain the behaviour and degradation of the cMDS error with respect to the embedding dimension. Then, they propose an algorithm, based on their theoretical findings, and show that it outperforms cMDS on standard image classification datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\n\nThe authors mention in the abstract that a theoretical analysis for cMDS on non-Euclidean metrics is lacking. Can the authors mention the error analysis on Euclidean metrics and detail how their approach differs from the literature, as well as the difference between their algorithm and the ones mentioned in l.84.\n\n## Quality\n\nSection 3 would benefit from a toy example where the 3 components of the errors are plotted with respect to the embedding dimension to validate the authors interpretation and the different weights between C1-C3. Maybe refer to Fig. 1 and use it to illustrate the discussion.\n\nl. 102: The authors claim that they provide an \"efficiently computable algorithm\" but I do not see any argument in the paper supporting this claim such as a complexity analysis, comparison with other approaches, or benchmarks of computational time. l.216-217 mention that the major computational step is a spectral decomposition, is it affordable in large dimensions ? What are the complexity for the type of matrices considered (is it sparse, dense, structured matrices) ?\n\nl. 231: The authors mention that solving eq. (3) is much more computationally intensive than their approach, can they explain the reasons as well as an order of magnitude for the difference (i.e. is it 10, 100 times more expensive) ? Similarly, they mention another approach by Qi and Yuan but do not do any comparison with them.\n\nFigure 1: Why is the squared error so large ? Should it also not be normalized by ||D||_F^2 ?\n\nl.84, the authors refer to several papers which aim to address the robustness with respect to noisy data but do not compare their approach with the literature in the experiments of section 4.\n\nIn the classification paragraph in section 4, why are the authors using a simple 3 layer feed-forward neural network ? Image classification taks are traditionally done using a convolutional neural network.\n\n## Clarity\n\nThe paper is not very well written as it lacks clarity in several places, mostly in section 4.\n\nWhat is the motivation for using the characterization by Hayden and Wells ?\n\nI do not think that the presentation of Lemma 1-5 in the main text really supports the discussion. When describing the idea of the proof of Thm. 1, the authors could say that each of the three terms are identified to C1, C2^2 and C3, and point to the Supplementary Material.\nOn the contrary, the interpretation of these terms is central and would deserve a paragraph title for each to be clearly identified.\n\nIn Section 4, the discussion around Figures 1 and 2 is very confusing: the captions do not contain enough informations to understand the figures alone (they should at least define the terms in the legend). The organization of the figures is also confusing and it may be preferable to either discuss the decomposition of the error earlier in section 3 or organize the figures according to the datasets (e.g. for the Portugal one, having one panel for the decomposition and a second for the algorithm performance).\nIn Figure 2: the contribution would be clearer is the authors clearly identify their algorithm in the legend of Fig. 2. I do not understand as well what is the \"Lower\" curve and why the associated error is below the true solution.\n\nThe classification paragraph in section 4, the associated supplementary material, and the caption of Figure 3 lack informations to really understand and reproduce the experiment of the authors.\n\nMinor comments:\n- l. 120 \"if and only if\"\n- l. 121: Please define the space in which $\\mathbf{1}$ and $s$ live.\n- Definition 2: I found it confusing that the notations do not exactly match the one given in eq. (5).\n- l.161: Recall that $S\\circ S$ denotes the Hadamard product\n- l.174: \"we can see that C1\"\n- l. 233: \"Here we use\"\n\n## Significance\n\nThe error analysis of the authors explains the behaviour of the cMDS error, which is validated experimentally in Fig. 1. In Section 4, the authors show that their new algorithm outperform cMDS and does not degrade with respect to the embedding dimension.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper would benefit from a conclusion section summarizing the main contribution of the authors and discussing the strengths and limitations of the study.\n\nThe authors could also discuss potentially negative societal impacts if the method is applied for discriminative purposes on image datasets.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This seems to be a strong theoretical contribution to NeurIPS, although both some of the reviewers and myself suspect it is less relevant for practical usage.
Decision: Accept (Poster)