An Innovative Algorithm For Robust, Interactive, Piecewise-Linear Data Exploration

Stephen Wright, Colin PatersonarXiv 2025 · DOI · arXiv

Abstract

Researchers at the University of York have developed a generalized version of the Theil-Sen algorithm that leverages massively parallel processing for robust, piecewise-linear data fitting. By identifying modes in parameter space rather than a single median, the algorithm detects regime shifts, manages heavy outliers, and disentangles multiple underlying data-generating processes in an interactive environment.

Introduction

In empirical fields such as Economics and Finance, researchers often encounter "found" data—noisy, short datasets like tax returns or sales reports that frequently contain outliers and "regime shifts." Traditional statistical tools, notably Ordinary Least Squares (OLS) regression, are highly sensitive to these anomalies; a single outlier can significantly skew the results.

While robust methods like the Theil-Sen estimator exist, they are often computationally prohibitive and typically optimized for finding a single global fit. This paper introduces a tool designed to explore multidimensional data where multiple linear relationships may coexist, requiring a method that is both robust to noise and capable of piecewise discovery.

Methodology

The proposed algorithm builds upon the non-parametric Theil-Sen estimator, which determines slopes by calculating the median of slopes between all pairs of points. To adapt this for complex modern datasets, the authors introduced several key innovations:

  1. Mode Detection: Instead of a global median, the algorithm identifies peaks (modes) in the parameter distribution, allowing for the discovery of multiple linear segments or clusters.
  2. Affinity Matrix and Clustering: Data points are grouped into segments using an affinity matrix based on their "votes" for specific parameter modes. Hamming distance is then used to partition the data into distinct clusters.
  3. LAD-LASSO Integration: To handle high-dimensional data and prevent overfitting, the authors integrated LASSO regularization using a Least Absolute Deviation (LAD) approach.
  4. Parallel Processing: The combinatorial nature of these calculations is handled via massively parallel processing on GPUs, enabling real-time interaction through a TensorFlowJS-based browser tool.
Workflow of the robust, piecewise-linear data exploration algorithm.

As shown in the workflow, the process involves iterative cycles of dimension reduction, parameter fitting, and stability analysis to produce a coarse granular description of the data, alongside model forms and confidence estimations.

Experimental Evaluation

The algorithm was tested against several classic "stress test" datasets designed to challenge standard statistical methods:

  • Anscombe’s Quartet and Datasaurus Dozen: These datasets demonstrate how identical summary statistics can mask vastly different visual structures. The algorithm's affinity matrix provided clear visual signatures for these clusters.
  • Simpson’s Paradox: In cases where global trends contradict local relationships (e.g., salary appearing to decrease with experience globally while increasing within specific groups), the algorithm correctly identified the distinct positive-slope clusters where OLS failed.
  • 3D Hyperplanes: Synthetic tests confirmed the ability to disentangle two distinct 2D relationships embedded in a 3D space.

Discussion and Key Insights

A central theme of this work is the "Compute for Robustness" trade-off. The authors argue that the widespread availability of parallel computing power makes previously "too slow" robust estimators the new gold standard for interactive data exploration. Furthermore, the inclusion of a "Human-in-the-Loop" approach—providing quality-of-fit heat maps—allows domain experts to visually identify local minima and select the most sensible models.

Limitations and Future Directions

The primary challenge remains scalability. The combinatorial nature of the algorithm currently limits its use to small-to-medium datasets (approximately 100 points and 3 explanatory variables). Future research will focus on optimizing memory usage, developing prune-and-merge heuristics, and exploring randomized sampling techniques to scale the algorithm for high-dimensional "Big Data" applications.

Summary updated

BibTeX
@misc{wright2025innovative,
  author = {Stephen Wright and Colin Paterson},
  title = {{An Innovative Algorithm For Robust, Interactive, Piecewise-Linear Data Exploration}},
  year = {2025},
  eprint = {2511.12705},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.12705},
}
Figure