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

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$$)?

• Hi Zaira. Welcome to Cross Validated. If you are quoting a result from any literature(s), it would be appreciable if you mention them. Not that the question, as of now, is ill-posed, but it would rather be more informative. Sep 25, 2022 at 8:27
• @User1865345 they're actually from some handwritten notes i have, not aware if they were dictated from a book. but the context was proving that a minimizing solution exists for a LAD minimization problem. Sep 25, 2022 at 8:58
• There must be typographical errors in this question, because unless $\theta=1/2,$ there is no minimum of this objective function: it can be made arbitrarily negative. A valid loss for quantile regression is given at stats.stackexchange.com/questions/251600.
– whuber
Sep 25, 2022 at 15:30

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$$.

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

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