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. We also show how to compute the regression depth in time 0 (n(d-2) + n log n) when 1 less than or equal to k less than or equal to d - 2.