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
In the field of robust statistics, traditional linear regression methods like least-squares are notoriously sensitive to outliers; even a single extreme data point can significantly skew the resulting fit. To address this, Rousseeuw and Hubert introduced the concept of regression depth. Intuitively, the regression depth of a hyperplane measures how well it is supported by a data set by determining the minimum number of points it must "cross" to be rotated into a vertical position (a "non-fit"). A high regression depth indicates a robust fit that is resistant to outliers.
A long-standing conjecture in this field posited that for any set of $n$ points in $d$ dimensions, there always exists a regression hyperplane with a depth of at least $\lceil n/(d+1) \rceil$. This matches the bound established by the "Center Point Theorem" for location depth. While this conjecture was proven for two dimensions, a general proof for higher dimensions remained elusive until the work presented in this paper.
Methodology
The authors establish their proof by bridging computational geometry and robust linear regression through a combination of projective geometry and topological fixed-point theorems. As a theoretical study, the results are derived mathematically and apply to any arbitrary set of $n$ points in $d$-dimensional Euclidean space.
Projective Duality and Crossing Distance
The core of the approach involves projective duality, which transforms the problem of finding a deep hyperplane into a dual problem of finding a point with high "undirected depth" within an arrangement of hyperplanes. To unify these concepts, the authors introduce "crossing distance," a generalized metric that encompasses both location depth (centrality of a point in a cloud) and regression depth (centrality of a plane to a trend).
Topological Proof
The proof leverages Brouwer’s Fixed Point Theorem. The authors demonstrate that there exists a projective transformation mapping the "point at vertical infinity" to a center point of the transformed data. To ensure the continuity required for the fixed-point theorem, discrete point sets are approximated with "smooth measures." These results are then translated back to discrete sets using "sharpening" lemmas.
Theoretical Framework
The paper's primary contribution is the formalization of the analogy between Center Points (location) and Deep Hyperplanes (regression). By viewing these through different projective lenses, the authors show they are fundamentally the same concept. This suggests that the existence of deep regressions is not merely a combinatorial coincidence but a fundamental topological property of Euclidean space.
Furthermore, the authors establish a complexity equivalence between testing regression depth and testing location depth. Given that identifying a center point is NP-hard in high dimensions, it follows that testing regression depth is also NP-hard.
Key Results
The research yields several significant findings:
- Confirmation of the Rousseeuw-Hubert Conjecture: The authors provide a definitive proof that for any $n$ points in $d$ dimensions, a hyperplane with regression depth $\geq \lceil n/(d+1) \rceil$ always exists.
- Improved Partitioning Bounds: The paper improves the lower bounds for "Tverberg-like" partitions. It is shown that data can always be partitioned into $\lceil n/d(d+1) \rceil$ subsets such that a single hyperplane maintains non-zero regression depth in every subset. For the specific case of 3D space, this bound is improved to $\lfloor (n+1)/6 \rfloor$.
- Computational Hardness: The authors prove that determining whether a hyperplane achieves a specific regression depth is coNP-complete when the dimension $d$ is variable.
Discussion and Future Work
While the paper proves the existence of deep hyperplanes, finding the optimal fit efficiently in high dimensions remains an open algorithmic challenge. Although linear-time approximations are available for fixed dimensions, the problem's NP-hard nature in higher dimensions limits exact solutions.
Additionally, the second conjecture by Rousseeuw and Hubert—suggesting a partition into $\lceil n/(d+1) \rceil$ subsets—remains partially open. While this work improved the lower bounds, the tight bound for $d > 2$ has yet to be finalized. Future research may also explore extending these proofs to a continuous version of Tverberg’s theorem, a task the authors identified as a significant topological challenge.
Summary updated