Sparse Approximation via Generating Point Sets

Avrim Blum, Sariel Har-Peled, Benjamin Raichel

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume15
Issue number3
DOIs
StatePublished - Jul 2019

Keywords

  • Convex hull
  • coreset
  • sparse approximation

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

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

Cite this