Stochastic quartet approach for fast multidimensional scaling

Multidimensional scaling is a statistical process that aims to embed high-dimensional data into a lower-dimensional, more manageable space. Common MDS algorithms tend to have some limitations when facing large data sets due to their high time and spatial complexities. This paper attempts to tackle the problem by using a stochastic approach to MDS which uses gradient descent to optimise a loss function defined on randomly designated quartets of points. This method mitigates the quadratic memory usage by computing distances on the fly, and has iterations in O(N) time complexity, with N samples. Experiments show that the proposed method provides competitive results in reasonable time. Public codes are available at "https://github.com/PierreLambert3/SQuaD-MDS.git"