Sparse Approximation via Generating Point Sets

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 ∊. We present an efficient algorithm to compute such an ∊ ′-approximation of size k alg, where ∊ ′ is a function of ∊, and k alg is a function of the minimum size k opt 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.

Authors

• Avrim Blum
• Sariel Har-Peled
• Benjamin Adam Raichel

Keywords

No keywords are indexed for this paper.