An algorithm for quantile smoothing splines

For p = 1 and ∞, Koenker, Ng and Portnoy (Statistical Data Analysis Based on the L₁ Norm and Related Methods (North-Holland, New York, 1992); Biometrika, 81 (1994)) proposed the τth L_p quantile smoothing spline, ĝ_τ,Lp, defined to solve min "fidelity" + λ "L_p roughness" g∈script G sign_p as a simple, nonparametric approach to estimating the τth conditional quantile functions given 0 ≤ τ ≤ 1. They defined "fidelity" = ∑ⁿ_i-1 ρ_τ(γ_i - g(x_i)) with ρ_τ(u) = (τ - I(u < 0))u, "L_i roughness" = ∑^n-1_i=1 |g′ (x_{i + 1}) - g′ (x_i)|, "L_∞, roughness" = max_x g″ (x), λ ≥ 0 and script G sign_p to be some appropriately defined functional space. They showed ĝ_τ, L_p to be a linear spline for p = 1 and parabolic spline for p = ∞, and suggested computations using conventional linear programming techniques. We describe a modification to the algorithm of Bartels and Conn (ACM Trans. Math. Software, 6 (1980)) for linearly constrained discrete L₁ problems and show how it can be utilized to compute the quantile smoothing splines. We also demonstrate how monotonicity and convexity constraints on the conditional quantile functions can be imposed easily. The parametric linear programming approach to computing all distinct τth quantile smoothing splines for a given penalty parameter λ, as well as all the quantile smoothing splines corresponding to all distinct λ values for a given τ, also are provided.