# Coresets for Data Discretization and Sine Wave Fitting

arXiv: https://arxiv.org/abs/2203.03009 · HTML: https://mlsanity.com/paper/2203.03009/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 70 references that are in the map.
- First posted on arXiv 6 Mar 2022.

## Builds on (most cited first, 30 of 30)

- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [Up or Down? Adaptive Rounding for Post-Training Quantization](https://mlsanity.com/paper/2004.10568/) (2020)
- [Provable Filter Pruning for Efficient Neural Networks](https://mlsanity.com/paper/1911.07412/) (2019)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Adaptive Quantization for Deep Neural Network](https://mlsanity.com/paper/1712.01048/) (2017)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition](https://mlsanity.com/paper/2107.11442/) (2021)
- [DAQ: Channel-Wise Distribution-Aware Quantization for Deep Image Super-Resolution Networks](https://mlsanity.com/paper/2012.11230/) (2020)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [On Coresets for Support Vector Machines](https://mlsanity.com/paper/2002.06469/) (2020)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [Introduction to Coresets: Accurate Coresets](https://mlsanity.com/paper/1910.08707/) (2019)
- [Data-Independent Structured Pruning of Neural Networks via Coresets](https://mlsanity.com/paper/2008.08316/) (2020)
- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures](https://mlsanity.com/paper/1508.05243/) (2015)
- [Tight Sensitivity Bounds For Smaller Coresets](https://mlsanity.com/paper/1907.01433/) (2019)
- [Deep Learning Meets Projective Clustering](https://mlsanity.com/paper/2010.04290/) (2020)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [On Periodic Functions as Regularizers for Quantization of Neural Networks](https://mlsanity.com/paper/1811.09862/) (2018)
- [Coresets for Regressions with Panel Data](https://mlsanity.com/paper/2011.00981/) (2020)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)

## Built on by (most cited first, 6 of 6)

- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [On the Size and Approximation Error of Distilled Sets](https://mlsanity.com/paper/2305.14113/) (2023)

## Abstract (arXiv)

In the monitoring problem, the input is an unbounded stream P=p1,p2cdots of integers in [N]:=1,cdots,N, that are obtained from a sensor (such as GPS or heart beats of a human). The goal (e.g., for anomaly detection) is to approximate the n points received so far in P by a single frequency sin, e.g. minc∈ Ccost(P,c)+λ(c), where cost(P,c)=sumi=1n sin2(frac2πN pic), Csubseteq [N] is a feasible set of solutions, and λ is a given regularization function. For any approximation error varepsilon>0, we prove that every set P of n integers has a weighted subset Ssubseteq P (sometimes called core-set) of cardinality |S|∈ O(log(N)O(1)) that approximates cost(P,c) (for every c∈ [N]) up to a multiplicative factor of 1±varepsilon. Using known coreset techniques, this implies streaming algorithms using only O((log(N)log(n))O(1)) memory. Our results hold for a large family of functions. Experimental results and open source code are provided.