Sparse Approximation via Generating Point Sets

DOI10.1145/3302249MaRDI QIDQ4972677zbMATH OpenOpenAlexFDO

Authors Benjamin Raichel, Avrim Blum, Sariel Har-Peled

Publication date 25 November 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3302249

zbMATH Keywords

sparse approximationconvex hullcoreset

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Recommendations

• Sparse approximation via generating point sets
• Covering point-sets with parallel hyperplanes and sparse signal recovery
• Sparse approximation by greedy algorithms
• On sparse interpolation and the design of deterministic interpolation points
• Approximating a planar convex set using a sparse grid
• Sparse approximations with interior point methods
• On iterative processes generating dense point sets
• Sparse representations and approximation theory
• Asymptotically efficient estimation of the sparsity function at a point
• Computing sparse approximations deterministically

Cites work

• scientific article; zbMATH DE number 1830719 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• Algorithms for polytope covering and approximation
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximating extent measures of points.
• Clustering to minimize the maximum intercluster distance
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Geometric approximation algorithms
• High-dimensional shape fitting in linear time
• Space exploration via proximity search
• Sparse approximation via generating point sets
• -nets and simplex range queries

Cited in

(9)

• Algorithms for approximate sparse regression and nearest induced hulls
• Computing instance-optimal kernels in two dimensions
• Sparse convex hull coverage
• Sparse approximation via generating point sets
• Random separating hyperplane theorem and learning polytopes
• Non-negative sparse regression and column subset selection with \(L_1\) error
• Spreading points using gradient and tabu
• Covering point-sets with parallel hyperplanes and sparse signal recovery
• Deep learning generalization and the convex hull of training sets

This page was built for publication: Sparse Approximation via Generating Point Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972677)