# Sparse Approximation via Generating Point Sets

arXiv: https://arxiv.org/abs/1507.02574 · HTML: https://mlsanity.com/paper/1507.02574/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2015.

## Built on by (most cited first, 9 of 9)

- [Deep Learning Generalization and the Convex Hull of Training Sets](https://mlsanity.com/paper/2101.09849/) (2021)
- [A Sketching Method for Finding the Closest Point on a Convex Hull](https://mlsanity.com/paper/2102.10502/) (2021)
- [Dimensionality Reduction for General KDE Mode Finding](https://mlsanity.com/paper/2305.18755/) (2023)
- [To what extent should we trust AI models when they extrapolate?](https://mlsanity.com/paper/2201.11260/) (2022)
- [An Ambiguity Measure for Recognizing the Unknowns in Deep Learning](https://mlsanity.com/paper/2312.06077/) (2023)
- [Uncertainty Measurement of Deep Learning System based on the Convex Hull of Training Sets](https://mlsanity.com/paper/2405.16082/) (2024)
- [Data subsampling for Poisson regression with pth-root-link](https://mlsanity.com/paper/2410.22872/) (2024)
- [Random Separating Hyperplane Theorem and Learning Polytopes](https://mlsanity.com/paper/2307.11371/) (2023)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)

## Abstract (arXiv)

 newcommandkalgkalg newcommandkoptkopt newcommandalgsetT renewcommandReℝ newcommandepsvarepsilon newcommandpth[2][!]#1left(#2right) newcommandnpointsn newcommandballDmathsfb newcommanddatasetP  For a set dataset of npoints points in the unit ball ballD subseteq Red, consider the problem of finding a small subset algset subseteq dataset such that its convex-hull eps-approximates the convex-hull of the original set. We present an efficient algorithm to compute such a eps'-approximation of size kalg, where eps' 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/eps2)-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.