Breaking Point in the Flow of Functions ✎

Original: "Change-point Detection for Sparse and Dense Functional Data in General Dimensions"
arXiv:2205.09252 · 2022-05-19 · arXiv non-exclusive · independent analysis · 2 min
A new algorithm finds moments when functional data change behavior abruptly, even if each curve is measured at just one point.

A seismograph records underground tremors: the smooth line suddenly jerks and changes its character. Similarly, functional data, such as ocean temperature maps or brain signals, may shift their shape at some point. The new algorithm FSBS catches such breakpoints, even when each curve is measured at only one point and noise drowns the signal.

Previously, detecting such changes required complete, error-free curves or one-dimensional domains. FSBS is the first algorithm to work on multidimensional domains with sparse, noisy observations. It first reconstructs the mean function at each time point using kernel smoothing, then compares the averages to the left and right of every candidate change point. To find all breakpoints, the algorithm scans a set of intervals of varying lengths and splits them in half if it finds a suspicious jump.

Key detail: to speed up computations, only randomly selected points of the domain are checked, not the entire grid. This allows handling large datasets without losing accuracy.

Theoretical analysis reveals a phase transition: when the number of curves is sufficiently large, the localization error of a change point does not depend on that number. If there are fewer curves, the error grows according to a power law. In numerical experiments, the algorithm outperformed three existing methods in all five scenarios, including the extremely sparse case with one point per curve.

On real sea surface temperature data from the southern Pacific Ocean, the algorithm detected two change points: 1981 and 1996. These coincide with extreme El Niño and Indian Ocean Dipole events. The seismograph went off: the tremors of climate shifts became visible in the flow of functional data.

The algorithm can detect a change point even if each curve is measured at just one point (n=1). This is equivalent to detecting a change in the mean over time for scalar observations, but with guarantees that account for the functional nature of the data.

In Isaac Asimov's novel 'Foundation', psychohistorians predict crises in the development of a galactic empire by analyzing vast arrays of social data. FSBS does something similar, but for continuous functions: it finds moments when a system's behavior shifts abruptly, which may herald a crisis.

Concepts
functional analysis data processing dimensionality reduction dataset data cleaning partition function saddle point data analysis