Multivariate Regression Depth
<|reference_start|>Multivariate Regression Depth: The regression depth of a hyperplane with respect to a set of n points in R^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d-1. The k=0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat.<|reference_end|>
@article{bern1999multivariate,
    title={Multivariate Regression Depth},
    author={Marshall Bern and David Eppstein},
    journal={Discrete Comput. Geom. 28(1):1-17, July 2002},
    year={1999},
    doi={10.1007/s00454-001-0092-1},
    archivePrefix={arXiv},
    eprint={cs/9912013},
    primaryClass={cs.CG math.CO}
}