Multivariate quantiles and multiple-output regression quantiles: From $L_1$ optimization to halfspace depth

Marc Hallin; Davy Paindaveine; Miroslav Šiman

Source-linked AI summary

Multivariate quantiles and multiple-output regression quantiles: From $L_1$ optimization to halfspace depth

Marc Hallin, Davy Paindaveine, Miroslav Šiman

arXiv:1002.4486v1Feb 24, 2010math.ST

TL;DR

The paper addresses the lack of an agreed multivariate quantile concept and its unresolved relation to halfspace depth. It constructs directional regression-style quantiles with multivariate L1 optimization, then shows that their contours coincide with Tukey depth regions and inherit useful asymptotic and computational properties.

Problem
Multivariate quantiles lacked an agreed definition with a clear, established relation to halfspace depth.
Method
The paper defines directional multivariate and multiple-output regression quantiles using Koenker–Bassett-style hyperplanes and fully multivariate L1 optimization.
Results
The quantile contours coincide with Tukey halfspace depth contours, with consistency, Bahadur representations, and asymptotic normality established for the quantiles.
Takeaways & Limitations
The connection enables parametric linear-programming computation of depth contours and transfers quantile-based asymptotic results to the depth setting.
Takeaways & Limitations
The multiple-output regression extension is only briefly indicated and requires further study of asymptotics, robustness, and nonlinear quantile regression.

Abstract

from arXiv · show

A new multivariate concept of quantile, based on a directional version of Koenker and Bassett's traditional regression quantiles, is introduced for multivariate location and multiple-output regression problems. In their empirical version, those quantiles can be computed efficiently via linear programming techniques. Consistency, Bahadur representation and asymptotic normality results are established. Most importantly, the contours generated by those quantiles are shown to coincide with the classical halfspace depth contours associated with the name of Tukey. This relation does not only allow for efficient depth contour computations by means of parametric linear programming, but also for transferring from the quantile to the depth universe such asymptotic results as Bahadur representations. Finally, linear programming duality opens the way to promising developments in depth-related multivariate rank-based inference.

1. Introduction: Multivariate quantiles and statistical depth.

The paper introduces multivariate and multiple-output regression quantiles designed to retain quantile-like analytical properties while connecting fundamentally to halfspace depth. This connection supports asymptotic transfer, geometric characterization, and linear-programming computation.

1. Introduction: Multivariate quantiles and statistical depth.: The proposed quantiles extend directional Koenker–Bassett regression quantiles to multivariate location and multiple-output regression settings.They use fully multivariate L1 optimization rather than projection-only univariate arguments.
1. Introduction: Multivariate quantiles and statistical depth.: The fixed-τ regions generated by the proposed quantile hyperplanes coincide with Tukey halfspace depth regions.Empirically, Tukey contour faces form a finite subcollection of the quantile hyperplanes.
1. Introduction: Multivariate quantiles and statistical depth.: The framework provides consistency, Bahadur representations, and asymptotic normality while yielding convex, nested, affine-equivariant contours.The depth connection transfers geometric and asymptotic properties between the two concepts.
1. Introduction: Multivariate quantiles and statistical depth.: Empirical quantile hyperplanes inherit linear-programming algorithms, enabling efficient computation of Tukey depth contours through parametric linear programming.The paper identifies this computational access as a major practical advantage.
1. Introduction: Multivariate quantiles and statistical depth.: Linear programming duality yields directional regression rank scores and motivates multivariate rank-based inference.The resulting scores are presented as a natural extension of methods developed for regression rank inference.

2. Definition and notation.

The paper defines a directional multivariate quantile as a Koenker–Bassett regression hyperplane indexed by a magnitude and direction. Its population and empirical versions support equivalent optimization formulations, uniqueness under regularity, and linear-programming computation.

2. Definition and notation.: For τ = τu in the open unit ball, the multivariate quantile is a (k−1)-dimensional hyperplane obtained by regressing u′Z on coordinates orthogonal to u.The direction u specifies the reference vertical axis, while Γu supplies an orthonormal basis of its orthogonal complement.
2. Definition and notation.: The objective function is the expected univariate τ-quantile check loss ρτ applied to Zu−b′Z⊥u−a.Finite first-order moments are tacitly required for the population definition.
2. Definition and notation.: Under Assumption (A), the distribution is absolutely continuous with connected support and finite first-order moments, and the population quantile hyperplane is unique.The assumption also prevents multiple minimizers of the defining optimization problem.
2. Definition and notation.: The family of quantile hyperplanes admits fixed-direction regression interpretations and fixed-magnitude contour interpretations.These two views organize the directional quantiles and the quantile contours generated across directions.
2. Definition and notation.: The constrained optimization definition is strictly equivalent to the original formulation, including the associated lower and upper quantile halfspaces.This alternative formulation is used for analytical and computational developments.
2. Definition and notation.: Empirical quantiles are sample analogs that coincide with standard single-output Koenker–Bassett hyperplanes for fixed u and require no moment assumption.Their convex minimizer sets may be nonunique in finite samples but shrink toward the unique population quantile under the stated conditions.
2. Definition and notation.: Empirical quantile hyperplanes inherit Koenker–Bassett linear-programming features, supporting efficient computation.A two-dimensional illustration shows the hyperplanes forming a polygonal central region coinciding with a Tukey depth region.

3. Multivariate quantiles as directional quantiles.

The paper characterizes multivariate quantiles through directional regression-quantile optimization, with probabilistic interpretations, equivariance, subgradient conditions, and asymptotic behavior.

Probabilistic interpretation: The lower halfspace of a multivariate τ-quantile has probability τ, providing its probabilistic interpretation.The corresponding upper and lower halfspace probability centers lie on a line parallel to u.
Subgradient conditions: The optimization admits necessary-and-sufficient subgradient conditions, including empirical conditions derived from linear programming and standard quantile regression.Under general position, empirical quantile hyperplanes can fit exactly k observations; strict inequalities ensure uniqueness.
Equivariance: The quantiles satisfy affine equivariance, including translation equivariance, so they do not depend on an arbitrary origin.The intercepts are coordinate-system independent, although slope coefficients depend on the chosen orthonormal basis.
Asymptotic results: Sample τ-quantiles are strongly consistent, while stronger assumptions yield asymptotic normality and Bahadur-type representations.Theorem 3.1 provides the main asymptotic result and supports confidence regions and tests of linear coefficient restrictions.

4. Multivariate quantiles as depth contours.

The paper defines multivariate quantile regions as upper envelopes of directional quantile halfspaces and proves that they coincide with Tukey halfspace-depth regions. This equivalence transfers geometric, distributional, and computational properties between the two frameworks.

Multivariate quantiles as depth contours: Quantile regions R(τ) are formed by intersecting all closed upper (τu)-quantile halfspaces, making them closed, convex, and nested.The nesting relation is R(τ1) ⊆ R(τ2) whenever τ1 ≥ τ2.
Connection with halfspace depth: R(τ) equals the Tukey halfspace-depth region D(τ) for every τ ∈ [0,1) under Assumption (A).The depth region collects points whose halfspace depth is at least τ.
Empirical regions: Empirical quantile regions are closed convex polyhedral sets, and under Assumption (A_n) they coincide almost surely with empirical depth regions when the interior is nonempty.Their faces are contained in empirical quantile hyperplanes of order τ.
Computational consequence: The empirical depth-contour faces are parts of empirical quantile hyperplanes, enabling depth-contour computation through linear programming.The equivalence provides a quantile-based interpretation of depth contours and imports efficient computational procedures.
Illustration: Figure 3 displays green Tukey contours from uniform, Gaussian, and t distributions using samples of size n = 449.The caption identifies the distributions and the common sample size but does not state a numerical comparison among them.
Relation with projection quantiles: The proposed approach contrasts with projection quantiles whose contours lack expected properties such as affine-equivariance and nestedness.Projection-based envelopes can require approximation and do not readily provide feasible computation of empirical depth regions.

5. Computational aspects.

The paper computes directional quantiles through standard quantile-regression machinery and aggregates fixed-τ solutions with parametric linear programming. Duality additionally supplies a route toward rank-based inference.

Dual formulation: Linear programming duality generalizes regression rank scores to multiple outputs, suggesting depth-related rank-based inference for future work.This inference development is explicitly left outside the paper’s scope.
Computing directional quantiles: The associated Lagrange multiplier can be obtained as a by-product of solving the primal problem.The constrained formulation retains multiplier information relevant for statistical inference.
Computing directional quantiles: Directional sample quantiles can be computed as standard single-output regression quantiles in a transformed regression problem.The transformation regresses Z_u on the marginals of Z_⊥u and a constant.
Computing directional quantiles: Quantile-regression software provides fast tools for computing sample τ-quantiles and corresponding multipliers in fixed directions, potentially for all τ values at once.The paper points to implementations in R and Matlab.
Computing quantile contours: The contour computation identifies a finite set of upper quantile halfspaces relevant for constructing consecutive Tukey depth contours.The method restricts to τ values with nτ integer without loss of generality under the stated theorem.
Computing quantile contours: For fixed τ, parametric linear programming partitions the unit sphere into finitely many cones, each associated with one quantile hyperplane.Within each cone, the relevant optimization statistics are piecewise constant.
Computing quantile contours: Adjacent cones can be explored efficiently because a neighboring optimal basis is recoverable from the previous basis using at most a few primal-simplex iterations.Breadth-first search handles general dimensions, while counter-clockwise traversal applies in two dimensions.

6. Multiple-output quantile regression.

The paper extends its directional quantile construction to multiple-output regression by embedding regressors and responses in a joint vector. Regression quantile regions are upper envelopes of directional hyperplanes, but may be nonnested when the response dimension exceeds one.

Contribution: The proposed multiple-output regression quantiles retain the desirable properties associated with classical single-output quantiles.The paper presents this as a principal extension of its multivariate quantile framework.
Definition: Multiple-output regression quantiles are obtained by applying the multivariate definition to Z := (W′, Y′)′, with directions restricted to encode response-space vertical directions.Here Y is an m-variate response and W contains the nonconstant regressors.
Definition: The auxiliary matrix Γu supplies an orthonormal basis for the subspace orthogonal to the response-direction vector.Its choice does not affect the directional regression quantile hyperplane.
Regression quantile regions: Regression τ-quantile regions are defined as upper envelopes of the directional regression τ-quantile hyperplanes.The construction is the regression analogue of the location quantile regions.
Regression quantile regions: Unlike location quantile regions, multiple-output regression quantile regions may be nonnested when p > 1.The paper identifies this as a multivariate version of regression quantile crossing.
Finite-sample computation: Finite-sample regression concepts use sample analogues of the population definitions and can be computed with the location-case procedure after substituting m and u_y for k and u.Figures 5 and 6 illustrate the resulting regression regions.

7. A real data application.

The real-data application uses multiple-output regression quantile contours to describe how body girth distributions vary with weight, age, BMI, and height. The resulting contour cuts reveal changes in location, dispersion, principal directions, variability, and asymmetry.

Data and setup: The dataset contains joint measurements from 507 physically active young men and women, but is not representative of a well-defined population.The authors therefore treat the regression quantile contours as descriptive and illustrative rather than population-representative.
Data and setup: The analysis models calf and thigh maximum girths jointly using a constant and one regressor: weight, age, height, or BMI.Contours are computed for τ = 0.01, 0.03, 0.10, 0.25, and 0.40 and cut at empirical regressor quantiles.
Results by regressor: Weight shows a positive location trend across contours, increasing dispersion, and a shift in principal variability direction from calf-dominant at lighter weights to thigh-dominant at heavier weights.The lighter-weight contours are oriented horizontally first, whereas heavier-weight contours tend toward a vertical first principal direction.
Results by regressor: Age shows little apparent location trend, while outer contours indicate increasing simultaneous variability of large calf and thigh girths with age.The inner contours nearly coincide across age cuts, but outer-contour shapes vary substantially.
Results by regressor: BMI produces results similar to weight, whereas height reveals height-dependent asymmetry, with stronger asymmetry at lower heights.For height, some inner contours show regression effects while others do not.
Interpretation: Variation in location, scale, shape, and asymmetry yields a richer analysis of body-measurement relationships than traditional regression methods provide.The conclusion concerns the descriptive information supplied by the contour analysis.

8. Final comments.

The paper closes by emphasizing its contribution to multivariate quantiles, halfspace depth, and multiple-output regression while identifying extensions needed for broader inference and robustness. It also points to rank-based inference and symmetry testing as promising directions.

Contributions: The proposed L1-based multivariate quantiles clarify the quantile interpretation of halfspace depth contours and provide an efficient way to compute them.The same framework extends quantile regression to multiple-output settings.
Open problems: A detailed study of multiple-output regression extensions remains open, including limiting distributions, Bahadur representations, breakdown points, and influence functions.The paper also identifies nonlinear quantile regression, such as local linear methods, as an unresolved direction.
Open problems: Linear programming duality may support a broader body of multivariate, depth-related rank-based inference methods.The paper presents this direction as promising rather than established.
Symmetry and inference: Symmetry in the distribution of Z is reflected in mappings involving λτu and cτu, motivating a functional for testing spherical symmetry.Deriving asymptotic properties for such statistics requires uniform versions of the theorem’s asymptotic results.

APPENDIX

The appendix supports the paper’s theoretical and computational claims by deriving asymptotic results and characterizing population and empirical halfspace-depth regions through quantile hyperplanes. It also identifies how collections of empirical quantile hyperplanes generate multiple depth contours.

Asymptotic arguments: The asymptotic derivations use differentiability and moment conditions for the objective, followed by central-limit-theorem arguments for the limiting distributions.The appendix invokes external asymptotic theorems to establish the displayed results.
Population depth regions: Under the stated assumptions, the population depth region D(τ) equals the intersection of closed halfspaces having probability at least 1 − τ.An equivalent characterization uses closed halfspaces with probability exactly 1 − τ.
Population depth regions: The proof connects quantile halfspaces to the halfspace representation of D(τ), establishing equality between the resulting quantile and depth regions.The argument uses the probability characterization of quantile halfspaces and arbitrary halfspaces of probability 1 − τ.
Empirical depth regions: Empirical depth regions are intersections of closed halfspaces containing at least n − ℓ + 1 observations and, under general-position conditions, can be represented using boundary hyperplanes spanning k observations.The relevant regions are assumed to have nonempty interior in the stated characterization.
Empirical depth regions: For admissible empirical levels, each halfspace in the depth-region characterization coincides with an upper sample quantile halfspace, yielding the correspondence between empirical quantile and depth regions.The proof compares the number of observations retained by quantile halfspaces with the empirical depth-region definition.
Computational characterization: Quantile hyperplanes containing k observations coincide with hyperplanes through k observations that cut off between ⌈nτ⌉ − k and ⌊nτ⌋ observations.This collection can compute min(k + η_nτ, ⌊nτ⌋ + 1) Tukey depth contours simultaneously.