Sparse approximation via generating point sets

Avrim Blum, Sariel Har-Peled, Benjamin Raichel

Research output: Chapter in Book/Report/Conference proceedingConference contribution


For a set P of n points in the unit ball b ⊂ℝd, consider the problem of finding a small subset T⊂P such that its convex-hull ϵ-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most e. We present an efficient algorithm to compute such an ϵ-approximation of size kalg, where ϵ is a function of ϵ, and kalg is a function of the minimum size kopt of such an ϵ-approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be eapproximated by a convex-combination of points of T that is O(l/ϵ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 T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781510819672
StatePublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Sparse approximation via generating point sets'. Together they form a unique fingerprint.

Cite this