High-dimensional approximate r-nets

DOI10.1137/1.9781611974782.2MaRDI QIDQ4575735zbMATH OpenOpenAlexFDO

Authors Georgia Avarikioti, Ioannis Z. Emiris, L. Kavouras, Ioannis Psarros

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04755

zbMATH Keywords

\(r\)-netsapproximation algorithmshigh dimensionlocality-sensitive hashingmetric geometry

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: The construction of $r$-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate $r$-nets with respect to Euclidean distance. For any fixed $epsilon>0$, the approximation factor is $1+epsilon$ and the complexity is polynomial in the dimension and subquadratic in the number of points. The algorithm succeeds with high probability. More specifically, the best previously known LSH-based construction of Eppstein et al. cite{EHS15} is improved in terms of complexity by reducing the dependence on $epsilon$, provided that $epsilon$ is sufficiently small. Our method does not require LSH but, instead, follows Valiant's cite{Val15} approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which $r$-nets are computed efficiently and the error can be controlled. Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the $(1+epsilon)$-approximate $k$th nearest neighbor distance in time subquadratic in the size of the input.

Recommendations

• High-dimensional approximate \(r\)-nets
• Deep ReLU neural networks in high-dimensional approximation
• High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks
• Random Projection RBF Nets for Multidimensional Density Estimation
• High-dimensional Apollonian networks
• A note on the expressive power of deep rectified linear unit networks in high-dimensional spaces
• Learning Network from High-Dimensional Array Data
• Interpretable approximation of high-dimensional data
• A fast iterative algorithm for high-dimensional differential network

Cited in

(3)

• High-dimensional approximate \(r\)-nets
• Random Projection RBF Nets for Multidimensional Density Estimation
• Learning Network from High-Dimensional Array Data

This page was built for publication: High-dimensional approximate r-nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575735)