Coresets for Data Discretization and Sine Wave Fitting

Alaa Maalouf, Murad Tukan, Eric Price, Daniel M. Kane, Dan Feldman

Abstract

This paper introduces the first coreset construction specifically designed for fitting sine waves and discretizing data. A coreset is a small, weighted summary of a massive dataset that maintains theoretical guarantees on approximation error. By proving that a dataset of $n$ points can be reduced to a subset of size $O(\text{polylog}(N))$, the authors enable high-accuracy anomaly detection and signal processing on massive data streams using negligible memory.

Introduction

In modern monitoring scenarios—ranging from medical ECG tracking to GPS telemetry—data often arrives as an unbounded stream. Fitting a sine wave to this data is a fundamental task for identifying underlying signals or detecting anomalies. However, as datasets scale to billions of points, traditional processing becomes computationally prohibitive, particularly on edge devices. Standard uniform sampling often fails to capture the "important" points that define a signal's periodic structure. This work addresses the challenge by creating a coreset: a representative subset ensuring that the cost of fitting a sine wave to the summary is nearly identical to the cost for the full dataset across any possible frequency.

Methodology: Sensitivity Sampling for Trigonometric Functions

The authors employ the Sensitivity Sampling Framework, which assigns an "importance" score (sensitivity) to each data point and samples accordingly. The primary technical innovation lies in bounding the total sensitivity and the VC dimension for non-linear, periodic trigonometric cost functions.

  1. Trigonometric Bounding: Unlike linear or polynomial functions, sine waves are periodic. The authors utilized arithmetic modulo and trigonometric identities to demonstrate that a point's sensitivity is inversely proportional to the density of nearby points in a cyclic sense.
  2. Graph Theoretic Reductions: To prove that total sensitivity remains small, the problem was reduced to finding the size of an independent set in a directed graph.
  3. Complexity Bounds: The authors proved that for a bounded query space (integers up to $N$), the VC dimension—a measure of problem complexity—is $O(\log(nN))$.

The resulting coreset size is polylogarithmic in the data range ($N$) and logarithmic in the number of points ($n$), allowing the summary to remain compact even as the stream grows indefinitely.

Data Discretization via Sine Fitting

Beyond signal processing, the authors demonstrate that sine fitting is a powerful tool for data discretization (quantization). By fitting a wave and projecting points to its nearest "root," they can reduce data bit-width while preserving structural integrity more effectively than naive methods.

The process of data discretization where points are projected to the nearest roots of a fitted sine wave.

Empirical Results

The method was evaluated on diverse real-world datasets, including Air Quality sensor data, Single Neuron recordings, Dog Heart ECGs, and Bat Echolocation pulses.

Across all benchmarks, the coreset consistently outperformed uniform sampling. A notable result occurred with the Dog Heart ECG dataset: the coreset captured the periodic structure so efficiently that the approximation error dropped to nearly zero even with minimal sample sizes, whereas uniform sampling required significantly more points to achieve comparable accuracy.

Approximation error vs. sample size for the Dog Heart ECG dataset, showing the coreset's superior performance reaching near-zero error.

Conclusion

This work provides a robust theoretical and empirical foundation for using coresets in periodic signal analysis. By leveraging the "Merge-and-Reduce" hierarchy, these coresets can process infinite streams with $O(\text{polylog}(n))$ memory. Future work includes extending the framework to higher-dimensional data and exploring more complex periodic functions for applications in deep learning quantization.

Summary updated

Abstract

In the monitoring problem, the input is an unbounded stream $P={p_1,p_2\cdots}$ 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. $\min_{c\in C}cost(P,c)+\lambda(c)$, where $cost(P,c)=\sum_{i=1}^n \sin^2(\frac{2\pi}{N} p_ic)$, $C\subseteq [N]$ is a feasible set of solutions, and $\lambda$ is a given regularization function. For any approximation error $\varepsilon>0$, we prove that every set $P$ of $n$ integers has a weighted subset $S\subseteq P$ (sometimes called core-set) of cardinality $|S|\in O(\log(N)^{O(1)})$ that approximates $cost(P,c)$ (for every $c\in [N]$) up to a multiplicative factor of $1\pm\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.
BibTeX
@inproceedings{maalouf2022coresets,
  author = {Alaa Maalouf and Murad Tukan and Eric Price and Daniel M. Kane and Dan Feldman},
  title = {{Coresets for Data Discretization and Sine Wave Fitting}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=tHy6PaqDzy},
}
Figure