Quantile regression necessarily has a solution with $r$ residuals equal to 0: why/how

Question

Given data $\{(Y_i,X_{1,i},X_{2,i}\dots X_{p,i}):1\le i\le n\}$. let $\theta\in(0,1)$ and $\beta=(\beta_1,\beta_2\dots\beta_p)^T$. Then, the quantile regression problem $$\underset{\alpha,\beta}{\min}\sum_{i=1}^n\{|Y_i-\alpha-\beta_1X_{1,i}-\dots-\beta_pX_{p,i}|+(2\theta-1)(Y_i-\alpha-\beta_1X_{1,i}-\dots-\beta_pX_{p,i})\}$$ has a solution such that at least $r$ of the residuals are $0$ if rank of the $n\times1$ matrix formed by rows of $\{(1,X_{1,i},X_{2,i}\dots X_{p,i}):1\le i\le n\}$ is $r$.

What is the logic behind this result? Why should a minimizer with $r$ residuals 0 exist? To understand this better I looked at one case where rank of the matrix is $p+1$. Then, it says a minimizer should exist such that all residuals are $0$. How does that make sense if $(1,X_{1,i},X_{2,i}\dots X_{p,i})$ is a linearly independent set (for rank to be $p+1$)?

Answer 1

Here's a proof sketch.

For convenience, we'll drop the explicit intercept $\alpha$. (You can always set one of the columns of $X$ to $1$ to add an intercept term back into the model.)

The loss function for quantile regression is piecewise linear. Unless it is globally constant (implying $X = 0$), its minimum must be able to be achieved at one of the boundaries between pieces, i.e. joints of the terms $|Y_i - X_i \beta|$. Hence, unless $X$ has rank zero, there must be a quantile regression solution for which at least one residual $Y_i - X_i \beta$ is zero.

Next, fix $X$ and $Y$ such that $X$ has rank $r$, and suppose solutions to the quantile regression $Q_{Y|X}(\theta) = X \beta$ have at most $k$ zero residuals. Choose a solution achieving this bound. This solution will remain optimal if $\beta$ is restricted to the subspace (of dimension $\geq p-k$) defined by setting the $k$ residuals to zero. Over this subspace, it will continue to be optimal if we drop the $k$ data points with zero residuals, yielding a new design matrix (of rank $\geq r-k$), and a new quantile regression (over this design matrix) possessing no solutions with zero residuals. But by our previous result, this is impossible unless $r - k \leq 0$, proving $k \geq r$.

Answer 2

I don't have time for a full answer now, but this is too much for a comment.

Quantile regression is solved via linear programming, so you will find some background at

• Formulating quantile regression as Linear Programming problem?
• How does quantile regression "work"?
  and I believe the result about zero residuals is effectively proved in many linear programming texts.

The following post is close to a proof: Residual using absolute loss linear regression