CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Theil-Sen Estimator (Robust Regression)

Non-parametric robust linear regression method that fits a line y = m*x + b by taking the median of slopes across all pairs of 2D data points, tolerating up to 29.3% gross outliers.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Machine Learning
Difficulty: Beginner
Family: Robust Regression & Statistical Estimation
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 2
Code example: Not ready
Visualization: Ready
Aliases: Theil-Sen Robust Linear Regression, Sen's Slope Estimator, Median-of-Slopes Regression

Overview

Unlike Ordinary Least Squares (OLS), where a single extreme outlier can arbitrarily tilt the fitted regression line, the Theil-Sen Estimator computes the slope m_{ij} = (y_j - y_i) / (x_j - x_i) for every pair of points with distinct x-coordinates, sets the fitted slope m to the median of all pairwise slopes, and sets the intercept b to the median of (y_i - m * x_i). It is deterministic, requires no tuning thresholds, and has an asymptotic breakdown point of 1 - 1/sqrt(2) approx 29.3%.

Core Concepts

median of pairwise slopes29.3% breakdown pointnon-parametric trend estimationoutlier resistance

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n) via randomized slope selection (Matoušek / Cole et al.)

Average

O(n^2) direct pairwise median

Worst

O(n^2)

Space

O(n^2) for all pairwise slopes (or O(n) subsampled)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Theil-Sen Estimator (Robust Regression) across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(n^2) direct pairwise median

0.2 min

Offline Batch / Timeout Risk~5.00B ops

Est. Worst-Case TimeO(n^2)

0.2 min

Offline Batch / Timeout Risk~5.00B ops

Est. Working MemoryO(n^2) for all pairwise slopes (or O(n) subsampled)

149.01 GB

High RAM PressureN=100,000

When to Use

Use the Theil-Sen Estimator when fitting a linear trend line to 2D data containing gross outliers or heavy-tailed noise, especially when you want a deterministic parameter-free fit.
Use it instead of ordinary least squares whenever corrupted measurements or spikes would skew the mean squared error.

When Not to Use

Avoid when more than 29.3% of the dataset consists of outliers (where RANSAC or Repeated Median Estimator can tolerate up to 50% outliers) or in high dimensions d >> 2.

What It Does

Fits a robust linear trend line y = m*x + b to 2D data contaminated with extreme outliers or non-Gaussian noise
Deterministically resists up to 29.3% arbitrary corrupted data points without requiring an inlier threshold hyperparameter

Use Cases

Trend estimation in environmental, climate, and financial time series with sensor spikes (Sen's slope)
Deterministic robust 2D line fitting when RANSAC's random sampling or threshold tuning is undesirable
Calibrating hardware measurements in the presence of intermittent glitch readings

Inputs

n 2D data points (x_0, y_0), ..., (x_{n-1}, y_{n-1})

Outputs

Robust slope m = median_{i < j}((y_j - y_i)/(x_j - x_i)) and intercept b = median_i(y_i - m * x_i)

Key Formulas (1)

Theil-Sen Slope & Breakdown Point

m = median_{x_i ≠ x_j} ((y_j − y_i) / (x_j − x_i)); breakdown = 1 − 1/√2 approx 29.3%

m = median_{x_i != x_j} ((y_j - y_i) / (x_j - x_i)); breakdown = 1 - 1/sqrt(2) approx 29.3%

Up to 29.3% of points can be moved to infinity before half the pairwise slopes are corrupted.

Pseudocode

1.Initialize empty list slopes = []
2.For each pair of indices 0 <= i < j < n:
3. If x[j] != x[i]: append (y[j] - y[i]) / (x[j] - x[i]) to slopes
4.Compute fitted slope m = median(slopes)
5.Compute residuals r[i] = y[i] - m * x[i] for i in 0..n-1
6.Compute fitted intercept b = median(r) and return (m, b)

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Initialize empty list slopes = []
For each pair of indices 0 <= i < j < n:
If x[j] != x[i]: append (y[j] - y[i]) / (x[j] - x[i]) to slopes
Compute fitted slope m = median(slopes)
Compute residuals r[i] = y[i] - m * x[i] for i in 0..n-1
Compute fitted intercept b = median(r) and return (m, b)

Canonical Example

Input: Points: (1, 2), (2, 4), (3, 6), (4, 8), plus extreme outlier (5, 1000)
Output: m = 2.0, b = 0.0 (exact line y = 2x recovered despite the y=1000 outlier)
Explanation: Of the 10 pairwise slopes, 6 pairs among the 4 clean points have slope 2.0 and 4 pairs involving the outlier have huge slopes, so the median slope is exactly 2.0.

Implementation Notes

Use Quickselect (median selection) on the array of pairwise slopes to find the median slope in O(N_pairs) time instead of full sorting.

Common Pitfalls

Dividing by zero when two points share the exact same x-coordinate (x_i == x_j); skip vertical pairs with x_i == x_j.
Computing the intercept using the mean of (y_i - m*x_i) instead of the median, which re-introduces outlier sensitivity into the vertical offset.