mlsanityData to 7 Oct 2026

Coresets for Data Discretization and Sine Wave Fitting

arXiv 2203.03009 ↗First posted 6 Mar 2022cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

30 of 70 references.

References · 30

  1. 2021A Survey of Quantization Methods for Efficient Neural Network Inferencecited by 798
  2. 2020Up or Down? Adaptive Rounding for Post-Training Quantizationcited by 600
  3. 2019Provable Filter Pruning for Efficient Neural Networkscited by 98
  4. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  5. 2016Coresets for Scalable Bayesian Logistic Regressioncited by 79
  6. 2017Adaptive Quantization for Deep Neural Networkcited by 67
  7. 2018On Coresets for Logistic Regressioncited by 65
  8. 2016Coresets and Sketchescited by 63
  9. 2018Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Boundscited by 43
  10. 2020Coresets for Near-Convex Functionscited by 38
  11. 2016New Frameworks for Offline and Streaming Coreset Constructionscited by 37
  12. 2021Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decompositioncited by 33
18 more
  1. 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
  2. 2020DAQ: Channel-Wise Distribution-Aware Quantization for Deep Image Super-Resolution Networkscited by 29
  3. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  4. 2020On Coresets for Support Vector Machinescited by 19
  5. 2020Sets Clusteringcited by 19
  6. 2021A Unified Approach to Coreset Learningcited by 18
  7. 2019Introduction to Coresets: Accurate Coresetscited by 17
  8. 2020Data-Independent Structured Pruning of Neural Networks via Coresetscited by 17
  9. 2017One-Shot Coresets: The Case of k-Clusteringcited by 15
  10. 2018Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and morecited by 14
  11. 2015Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixturescited by 12
  12. 2019Tight Sensitivity Bounds For Smaller Coresetscited by 11
  13. 2020Deep Learning Meets Projective Clusteringcited by 10
  14. 2021Coresets for Decision Trees of Signalscited by 10
  15. 2018On Periodic Functions as Regularizers for Quantization of Neural Networkscited by 8
  16. 2020Coresets for Regressions with Panel Datacited by 8
  17. 2021A Novel Sequential Coreset Method for Gradient Descent Algorithmscited by 7
  18. 2021Introduction to Coresets: Approximated Meancited by 5

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 5.

6 papers.

  1. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  2. 2023Provable Data Subset Selection For Efficient Neural Network Trainingcited by 14
  3. 2023Dataset Distillation Meets Provable Subset Selectioncited by 7
  4. 2023ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Explorationcited by 5
  5. 2023AutoCoreset: An Automatic Practical Coreset Construction Frameworkcited by 4
  6. 2023On the Size and Approximation Error of Distilled Setscited by 3