...$\vec{\delta}^{(ij)}=(\delta_{ij1},\ldots,\delta_{ijq})^T$

henceforth, all vectors are taken as column vectors; a row vector can be obtained from the column vector, and vice versa, by transposition, which is denoted with the T superscript

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... metric

D₂ corresponds to the Euclidean distance, and $D_\infty$ is equivalent to $$\max_a\delta_{ija}$$

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 

an $n\times n$ matrix [d_ij] is said to be Euclidean if n points can be embedded in a Euclidean space of some dimension, such that the Euclidean distance between the i^th and j^th points is d_ij, for all $1\le i,j\le n$

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 

in our work we have used an implementation of PCO - DistPCoA - made publicly available by Philippe Casgrain

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 

we use the indefinite article because there may be many distinct solutions with the same globally minimal value of the loss function

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... iteration

follows from the fact that the whole dissimilarity matrix $\vec{\Delta}$ of order $n\times n$ has to be inspected at every iteration, where n is the number of objects

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... experiment

actually a number of workstations have been used, and the timings normalised to that of the 300MHz CPU

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... solution

IM is a deterministic algorithm, thus for a given starting configuration it will always converge to the same local minimum

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$n_1=N^{\displaystyle\alpha^{\lceil\log_{\alpha}\log_N\phi\rceil}}$

calculated by expanding the sequence n: $n_1=N^{\displaystyle\alpha^{k-1}}$, and solving $$\min_k n_1\le \phi$$ for k

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...

labels correspond to steps of the algorithm

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...O

this is also the worst case running time of standard MDS: O(N³)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... efficiency

this is also the space requirement of standard MDS: O(N²)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 

we have based this evaluation on an implementation of PCA by Fionn Murtagh, available from the StatLib Multivariate Archive

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 

KYST version 2a is available from Netlib

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... respectively

the time taken by KYST to generate continuous configurations, which constitute a starting point for the greedy algorithms and SWO, has not been included, as it is negligible when compared to the time required to run GA

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.