@article{f108203a389e438d9892e2e23c65962e,

title = "Sparse Approximation via Generating Point Sets",

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.",

keywords = "Convex hull, coreset, sparse approximation",

author = "Avrim Blum and Sariel Har-Peled and Benjamin Raichel",

note = "Funding Information: Work by A.B. was conducted while on sabbatical at the University of Illinois and was partially supported by NSF awards CCF-1415460 and CCF-1525971. Work by S.H. was partially supported by NSF AF awards CCF-1421231 and CCF-1217462. Work by B.R. was partially supported by the University of Illinois Graduate College Dissertation Completion Fellowship, NSF CRII Award 1566137, and CAREER Award 1750780. A preliminary version of this article appeared in SODA 16 [7]. The full version of the article is also available on the arxiv [6]. Authors{\textquoteright} addresses: A. Blum, Toyota Technological Institute at Chicago (TTIC), 6045 S. Kenwood Ave. Chicago, IL 60637, USA; S. Har-Peled, SC 3306, Computer Science, UIUC, 201 N. Goodwin Avenue, Urbana, IL 61801, USA; B. Raichel, Department of Computer Science, Univeristy of Texas at Dallas, 800 W. Campbell Rd., MS EC-31, Richardson, TX 75080, USA. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2019 Association for Computing Machinery. 1549-6325/2019/06-ART32 $15.00 https://doi.org/10.1145/3302249",

year = "2019",

month = jul,

doi = "10.1145/3302249",

language = "English (US)",

volume = "15",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}