{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T12:13:19Z","timestamp":1779106399507,"version":"3.51.4"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1415460,CCF-1525971,CCF-1421231,CCF-1217462"],"award-info":[{"award-number":["CCF-1415460,CCF-1525971,CCF-1421231,CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            For a set\n            <jats:italic>P<\/jats:italic>\n            of\n            <jats:italic>n<\/jats:italic>\n            points in the unit ball b\u2286 R\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            , consider the problem of finding a small subset\n            <jats:italic>T<\/jats:italic>\n            \u2286\n            <jats:italic>P<\/jats:italic>\n            such that its convex-hull \u03b5-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of\n            <jats:italic>T<\/jats:italic>\n            and the convex hull of\n            <jats:italic>P<\/jats:italic>\n            should be at most \u03b5. We present an efficient algorithm to compute such an \u03b5\u2032-approximation of size\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>alg<\/jats:sub>\n            , where \u03b5 \u2032 is a function of \u03b5 and\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>alg<\/jats:sub>\n            is a function of the minimum size\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>opt<\/jats:sub>\n            of such an \u03b5-approximation. Surprisingly, there is no dependence on the dimension\n            <jats:italic>d<\/jats:italic>\n            in either of the bounds. Furthermore, every point of\n            <jats:italic>P<\/jats:italic>\n            can be \u03b5-approximated by a convex-combination of points of\n            <jats:italic>T<\/jats:italic>\n            that is\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5\n            <jats:sup>2<\/jats:sup>\n            )-sparse.\n          <\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>T<\/jats:italic>\n            of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.\n          <\/jats:p>","DOI":"10.1145\/3302249","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T12:09:28Z","timestamp":1560427768000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Sparse Approximation via Generating Point Sets"],"prefix":"10.1145","volume":"15","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"P. K. Agarwal S. Har-Peled and K. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry J. E. Goodman J. Pach and E. Welzl (Eds.). Cambridge New York NY.  P. K. Agarwal S. Har-Peled and K. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry J. E. Goodman J. Pach and E. Welzl (Eds.). Cambridge New York NY."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 27th Annual Conference on Learning Theory (COLT\u201914)","volume":"35","author":"Arora S.","unstructured":"S. Arora , R. Ge , and A. Moitra . 2014. New algorithms for learning incoherent and overcomplete dictionaries . In Proceedings of the 27th Annual Conference on Learning Theory (COLT\u201914) . Vol. 35 . 779--806. S. Arora, R. Ge, and A. Moitra. 2014. New algorithms for learning incoherent and overcomplete dictionaries. In Proceedings of the 27th Annual Conference on Learning Theory (COLT\u201914). Vol. 35. 779--806."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 28th Annual Conference on Learning Theory (COLT\u201915)","volume":"40","author":"Balcan M.-F.","unstructured":"M.-F. Balcan , A. Blum , and S. Vempala . 2015. Efficient representations for lifelong learning and autoencoding . In Proceedings of the 28th Annual Conference on Learning Theory (COLT\u201915) . Vol. 40 . 191--210. M.-F. Balcan, A. Blum, and S. Vempala. 2015. Efficient representations for lifelong learning and autoencoding. In Proceedings of the 28th Annual Conference on Learning Theory (COLT\u201915). Vol. 40. 191--210."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746566"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"A. Blum S. Har-Peled and B. Raichel. 2015. Sparse approximation via generating point sets. ArXiv e-prints (July 2015). arxiv:cs.CG\/1507.02574  A. Blum S. Har-Peled and B. Raichel. 2015. Sparse approximation via generating point sets. ArXiv e-prints (July 2015). arxiv:cs.CG\/1507.02574","DOI":"10.1137\/1.9781611974331.ch40"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Blum A.","unstructured":"A. Blum , S. Har-Peled , and B. Raichel . 2016. Sparse approximation via generating point sets . In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916) , Robert Krauthgamer (Ed.). SIAM, 548--557. A. Blum, S. Har-Peled, and B. Raichel. 2016. Sparse approximation via generating point sets. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916), Robert Krauthgamer (Ed.). SIAM, 548--557."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems: Advances in Neural Information Processing Systems 30 (NIPS\u201917)","author":"Van Buskirk G.","unstructured":"G. Van Buskirk , B. Raichel , and N. Ruozzi . 2017. Sparse approximate conic hulls . In Proceedings of the Annual Conference on Neural Information Processing Systems: Advances in Neural Information Processing Systems 30 (NIPS\u201917) . 2531--2541. G. Van Buskirk, B. Raichel, and N. Ruozzi. 2017. Sparse approximate conic hulls. In Proceedings of the Annual Conference on Neural Information Processing Systems: Advances in Neural Information Processing Systems 30 (NIPS\u201917). 2531--2541."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57155-8_252"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824783"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_12_1","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"Har-Peled S.","unstructured":"S. Har-Peled . 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs , Vol. 173 . American Mathematical Society , Boston, MA . S. Har-Peled. 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs, Vol. 173. American Mathematical Society, Boston, MA."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 31st Annual Symposium on Computer Geometry (SoCG\u201915)","volume":"34","author":"Har-Peled S.","unstructured":"S. Har-Peled , N. Kumar , D. Mount , and B. Raichel . 2015. Space exploration via proximity search . In Proceedings of the 31st Annual Symposium on Computer Geometry (SoCG\u201915) . Vol. 34 . 374--389. S. Har-Peled, N. Kumar, D. Mount, and B. Raichel. 2015. Space exploration via proximity search. In Proceedings of the 31st Annual Symposium on Computer Geometry (SoCG\u201915). Vol. 34. 374--389."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3116000"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44634-6_4"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.)","volume":"70","author":"Mirrokni V.","unstructured":"V. Mirrokni , R. P. Leme , A. Vladu , and S. C. Wong . 2017. Tight bounds for approximate Carath\u00e9odory and beyond . In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.) , Vol. 70 . 2440--2448. V. Mirrokni, R. P. Leme, A. Vladu, and S. C. Wong. 2017. Tight bounds for approximate Carath\u00e9odory and beyond. In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.), Vol. 70. 2440--2448."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Symposium on Mathematics and Theoretical Automata.","volume":"12","author":"Novikoff A. B. J.","year":"1962","unstructured":"A. B. J. Novikoff . 1962 . On convergence proofs on perceptrons . In Proceedings of the Symposium on Mathematics and Theoretical Automata. Vol. 12 . 615--622. A. B. J. Novikoff. 1962. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematics and Theoretical Automata. Vol. 12. 615--622."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912)","author":"Spielman D. A.","unstructured":"D. A. Spielman , H. Wang , and J. Wright . 2012. Exact recovery of sparsely-used dictionaries . In Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912) . 37.1--37.18. D. A. Spielman, H. Wang, and J. Wright. 2012. Exact recovery of sparsely-used dictionaries. In Proceedings of the 25th Annual Conference on Learning Theory (COLT\u201912). 37.1--37.18."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3302249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3302249","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3302249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:48Z","timestamp":1750208508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3302249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,12]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3302249"],"URL":"https:\/\/doi.org\/10.1145\/3302249","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,12]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}