Acceleration of multidimensional scaling by vector extrapolation techniques
View Patent ↗A method for multidimensional scaling (MDS) of a data set comprising a plurality of data elements is provided, wherein each data element is identified by its coordinates, the method comprising the steps of: (i) applying an iterative optimization technique, such as SMACOF, a predetermined amount of times on a coordinates vector, said coordinates vector representing the coordinates of a plurality of said data elements, and obtaining a modified coordinates vector; (ii) applying a vector extrapolation technique, such as Minimal Polynomial Extrapolation (MPE) or reduced Rank Extrapolation (RRE) on said modified coordinates vector obtaining a further modified coordinates vector; and (iii) repeating steps (i) and (ii) until one or more predefined conditions are met.
1. A program storage device comprising:
a storage area; and
information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps for multidimensional scaling of a data set comprising a plurality of data elements, each data element identified by its coordinates, the method comprising the steps of:
(i) applying an iterative optimization technique a predetermined amount of times on a coordinates vector, said coordinates vector representing the coordinates of a plurality of said data elements, and obtaining a modified coordinates vector;
(ii) applying a vector extrapolation technique on said modified coordinates vector obtaining a further modified coordinates vector; and
(iii) repeating steps (i) and (ii) until one or more predefined condition are met.
2. A program storage device according to claim 1 , wherein said iterative optimization procedure is carried on in a multi-scale manner.
3. A program storage device according to claim 1 , wherein said iterative optimization technique is SMACOF.
4. A program storage device according to claim 1 , wherein the cost function optimized for by the iterative optimization technique includes a stress cost function as a component, with or without the addition of other terms.
5. A program storage device according to claim 1 , wherein said vector extrapolation technique is Minimal Polynomial Extrapolation or Reduced Rank Extrapolation.
6. A program storage device according to claim 1 , wherein said one or more predefined conditions comprises:
(i) the norm of the change in the vector ∥x n+i+1 −x n+i ∥ under some norm is smaller than a specified value;
(ii) the relative change in the cost function
F
cost
(
x
n
+
i
)
-
F
cost
(
x
n
+
i
+
1
)
F
cost
(
x
n
+
i
+
1
)
is smaller than a specified value;
(iii) a specified number of iterations/cycles has elapsed;
(iv) a certain amount of time has passed; or
(v) any combination thereof.
7. A program storage device according to claim 1 , wherein said iterative optimization technique comprises:
(i) Gradient Descent algorithm with or without line search;
(ii) Conjugate Gradients algorithm with or without line search;
(iii) Quasi Newton algorithm with or without line search;
(iv) Newton algorithm with or without line search; or
(v) Levenberg-Marquardt algorithm with or without line search.
8. A program storage device according to claim 1 , wherein the cost function associated with the iterative optimization technique comprises:
(i) the least squares cost function;
(ii) the SSTRESS cost function;
(iii) the STRAIN cost function;
(iv) a p-norm on the distortion of distances;
(v) any non-metric MDS cost function; or
(vi) any cost functional including a distance distortion term.
9. A program storage device according to claim 1 , used in one or more of the following applications:
(i) visualization of abstract data;
(ii) generic machine learning and/or semi-supervised learning for pattern recognition;
(iii) image retrieval, using various image features as a basis for a dissimilarity;
(iv) geometric surfaces processing;
(v) identification of sampled objects;
(vi) pattern classification and data mining for large data sets;
(vii) data visualization for real-time data from network administration and/or supply networks and/or infrastructure; or
(viii) detecting trends and components of multidimensional data.
10. A program storage device according to claim 1 , wherein said data set is reduced to two or three dimensions.