Sparse Approximation via Generating Point Sets

Avrim Blum, Sariel Har-Peled, Benjamin Raichel

Research output: Contribution to journalArticlepeer-review


For a set P of n points in the unit ball b Rd , 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 ϵ.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 ϵ-Approximated by a convex-combination of points of T that is O(1/ϵ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)
Article number32
JournalACM Transactions on Algorithms
Issue number3
StatePublished - Jul 2019


  • Convex hull
  • coreset
  • sparse approximation

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Sparse Approximation via Generating Point Sets'. Together they form a unique fingerprint.

Cite this