23/08/2020

Voronoi graph traversal in high dimensions with applications to topological data analysis and piecewise linear interpolation

Vladislav Polianskii, Florian T. Pokorny

Keywords: linear interpolation, Voronoi diagram, topological data analysis, Delaunay complex

Abstract Paper Similar Papers

Abstract: Voronoi diagrams and their dual, the Delaunay complex, are two fundamental geometric concepts that lie at the foundation of many machine learning algorithms and play a role in particular in classical piecewise linear interpolation and regression methods. More recently, they are also crucial for the construction of a common class of simplicial complexes such as Alpha and Delaunay-vC ech complexes in topological data analysis. We propose a randomized approximation approach that mitigates the prohibitive cost of exact computation of Voronoi diagrams in high dimensions for machine learning applications. In experiments with data in up to 50 dimensions, we show that this allows us to significantly extend the use of Voronoi-based simplicial complexes in Topological Data Analysis (TDA) to higher dimensions. We confirm prior TDA results on image patches that previously had to rely on sub-sampled data with increased resolution and demonstrate the scalability of our approach by performing a TDA analysis on synthetic data as well as on filters of a ResNet neural network architecture. Secondly, we propose an application of our approach to piecewise linear interpolation of high dimensional data that avoids explicit complete computation of an associated Delaunay triangulation.

The video of this talk cannot be embedded. You can watch it here:
https://dl.acm.org/doi/10.1145/3394486.3403266#sec-supp
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at KDD 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 12:11 
 0
 0
 0
 0
 20:08 
 0
 0
 0
 0
 3:27 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 14:01 
 0
 0
 0
 0
 5:17 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 15:58 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 1:02 
 0
 0
 0
 0
 9:23 
 0
 0
 0
 0
 3:44 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 2:49 
 0
 0
 0
 0
 18:10 
 1
 0
 1
 1
 13:26 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 16:38 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 6:58 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 15:25 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 3:04 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 1
 5:15 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 11:28 
 0
 0
 0
 0
 5:09 
 0
 0
 0
 0
 12:34 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 13:15 
 0
 0
 0
 0
 5:09