Abstract
We show that, for any set of $n$ points in $d$ dimensions, there exists a hyperplane with regression depth at least $\lceil n/(d+1) \rceil$, as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of $n$ hyperplanes in $d$ dimensions there exists a point that cannot escape to infinity without crossing at least $\lceil n/(d+1) \rceil$ hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
Introduction: The Challenge of Robust Regression
In statistical modeling, the "least-squares" method is the ubiquitous standard for linear regression. However, it suffers from a significant vulnerability: a lack of robustness. A single outlier—a data point far removed from the general trend—can disproportionately influence the resulting model, pulling the regression line away from the majority of the data.
To address this, robust statistics introduces measures like regression depth. Proposed by Rousseeuw and Hubert, regression depth quantifies how "central" a hyperplane is relative to a point cloud. Geometrically, the regression depth of a hyperplane is defined as the minimum number of data points it must encounter as it is rotated into a vertical position. A high regression depth indicates that the hyperplane is well-supported by the data from all directions, making it a more stable and robust estimator.
The Rousseeuw-Hubert Conjecture
For years, it was conjectured that for any set of $n$ points in $d$ dimensions, there always exists a hyperplane with a regression depth of at least $\lceil n/(d+1) \rceil$. While this was proven for two dimensions, a general proof for higher dimensions remained elusive until this work. This paper provides the definitive proof of this conjecture, establishing a fundamental lower bound for regression depth.
Methodology: Bridging Geometry and Topology
The authors employ a sophisticated blend of computational geometry and algebraic topology to tackle the problem:
- Projective Duality: The problem is first transformed. Finding a "deep" hyperplane for a set of points is shown to be dually equivalent to finding a "deep" point within an arrangement of hyperplanes.
- Topological Fixed-Point Theorems: The core proof utilizes Brouwer’s Fixed Point Theorem. By applying a specific projective transformation, the authors map the "point at infinity" to a center point of the data distribution.
- Smoothing and Measure Theory: A significant challenge in applying topological theorems to discrete point sets is the lack of continuity; moving a point slightly can cause the "center" to jump. The authors overcome this by "smoothing" the discrete data into a continuous measure, allowing for the use of calculus-based arguments and ensuring the continuity required for Brouwer's theorem.
- Central Projection: The proof navigates between Euclidean space and a $d$-dimensional sphere using a sequence of projections, facilitating the handling of projective transformations.
Key Insights
The most significant insight is the formal unification of location depth (the centrality of a point) and regression depth (the centrality of a plane). Through the lens of projective geometry, these two concepts are revealed to be different views of the same underlying geometric property.
The proof demonstrates that the existence of deep regression planes is a topological necessity. If one attempts to map the "vertical" direction to the "center" of the data, the mathematics of fixed-point theorems guarantees that at least one such stable mapping—and thus one such deep plane—must exist.
Results and Complexity
- Proof of Conjecture 1: The authors successfully prove that for any set of $n$ points in $\mathbb{R}^d$, there exists a hyperplane with regression depth $\ge \lceil n/(d+1) \rceil$. This result is tight, matching known upper bounds.
- Partitioning Bounds: The paper improves bounds for the related problem of partitioning data into subsets that share a common deep hyperplane. They show that data can be partitioned into $\lceil n/d(d+1) \rceil$ such subsets.
- Computational Hardness: While deep planes are guaranteed to exist, the authors prove that determining if a hyperplane meets a specific depth threshold is coNP-complete when the dimension $d$ is variable. This suggests that finding the optimal (deepest) hyperplane in high-dimensional space is computationally difficult.
Conclusion and Future Directions
This work settles a major open question in robust statistics by proving the existence of deep regression hyperplanes in arbitrary dimensions. However, several avenues for future research remain. While existence is proven, the coNP-completeness result highlights the need for efficient approximation algorithms to find these planes in practice. Additionally, while the bounds for data partitioning were improved, a full proof for all dimensions in the partitioning conjecture (Conjecture 2) remains an open challenge.
Summary updated