TY - GEN
T1 - Sparse approximation via generating point sets
AU - Blum, Avrim
AU - Har-Peled, Sariel
AU - Raichel, Benjamin
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84962920208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84962920208&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974331.ch40
DO - 10.1137/1.9781611974331.ch40
M3 - Conference contribution
AN - SCOPUS:84962920208
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 548
EP - 557
BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
A2 - Krauthgamer, Robert
PB - Association for Computing Machinery
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Y2 - 10 January 2016 through 12 January 2016
ER -