Data visualization using nonlinear dimensionality reduction accelerated with fast multipole methods

Details

Supervisors

Lee, John Aldo ; Verleysen, Michel

Degree label

Master [120] : ingénieur civil en science des données, à finalité spécialisée

Abstract

The following thesis investigates the use of Fast Multipole Methods as part of the acceleration of multi-scale Neighbor Embeddings methods. Given the exponential increase in the amount of available data in recent years, it is essential that the tools and algorithms for processing it become faster. As a matter of fact, this does not exclude dimension reduction techniques such as the family of Neighbour embedding methods. Indeed, given their remarkable results, particularly in the context of visualisation, these methods have enjoyed growing popularity since their development. As for the current literature, the two most popular approaches for accelerating Neighbor Embedding methods are the Barns-Hut algorithm as well as Fast Multipole Methods. Accelerated single-scale Neighbor Embeddings algorithms that use these two methods are already widespread. Nevertheless, regarding the multi-scale scheme of Neighbor Embedding methods, only an acceleration using Barns-Hut is currently proposed. Given the improved results of multi-scale Neighbor Embeddings methods compared to those of the single-scale approaches, as well as the lower time complexity of Fast Multipole Methods when compared to the Barns-Hut algorithm, this work therefore seeks to combine both. Hence, the subsequent work is divided into three parts. The first one covers the single-scale and multi-scale versions of several Neighbor Embedding methods in detail. The second then analyses two distinct Fast Multipole Methods and the methodology by which they have been used to accelerate the single-scale methods previously covered. Finally, the third part analyses how these same Fast Multipole Methods can be adapted to accelerate the multi-scale scheme of previously accelerated single-scale methods. Both, an implementation and experimental results of these adaptations are then given and compared with some existing methods. Ultimately, the paper concludes by highlighting certain limitations as well as several promising results of the carried out implementations. In addition, a number of suggestions and ideas for improvements are put forward in order to not only avoid the limitations mentioned above, but also to improve the obtained results. In addition, the complexity and variability of Fast Multipole Methods are highlighted, although motivating further study for their use. Done implementations are publicly available at 'https://github.com/cedantoine/Multi-scale-FGT-and-PM'

Citations

• APA

Antoine, C. (2023). Data visualization using nonlinear dimensionality reduction accelerated with fast multipole methods. https://dial-mem.test.bib.ucl.ac.be/handle/2078.2/34224