Sparse approximation via generating point sets

DOI10.1137/1.9781611974331.CH40MaRDI QIDQ4575617zbMATH OpenOpenAlexFDO

Authors Benjamin Raichel, Avrim Blum, Sariel Har-Peled

Publication date 16 July 2018

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

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

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: $$ For a set $dataset$ of $points$ points in the unit ball $$, consider the problem of finding a small subset $algsetsubseteqdataset$ such that its convex-hull $eps$-approximates the convex-hull of the original set. We present an efficient algorithm to compute such a $ep{s}^{\prime }$-approximation of size $kalg$, where $ep{s}^{\prime }$ is function of $eps$, and $kalg$ is a function of the minimum size $kopt$ of such an $eps$-approximation. Surprisingly, there is no dependency on the dimension $d$ in both bounds. Furthermore, every point of $dataset$ can be $eps$-approximated by a convex-combination of points of $algset$ that is $O(1/ep{s}^2)$-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset $algset$ of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.

Recommendations

• Sparse Approximation via Generating Point Sets
• Sparse convex hull coverage
• Approximating a planar convex set using a sparse grid
• Approximate convex hull of data streams
• New approximation algorithms for minimum enclosing convex shapes

Cited in

(11)

• Theorems of Carathéodory, Helly, and Tverberg without dimension
• Sparse convex hull coverage
• Covering point-sets with parallel hyperplanes and sparse signal recovery
• Sparse Approximation via Generating Point Sets
• Approximate convex hull of data streams
• Approximating Distance Measures for the Skyline
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries
• Spreading points using gradient and tabu
• Algorithms for approximate sparse regression and nearest induced hulls
• Robust vertex enumeration for convex hulls in high dimensions

This page was built for publication: Sparse approximation via generating point sets

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