1
$\begingroup$

Suppose we want to find coefficients $b$ in $\underset{b}{\operatorname{argmin}} \displaystyle\sum\limits_{i=1}^n | y_{i}-b_{1}x_{i}-b_{0}\mid$.

If we rewrite this problem in terms of linear programming, we can use two different ways: 1. $$min \displaystyle\sum\limits_{i=1}^n |z_{i}|$$ subject to $z_{i}>=y_{i}-b_{1}x_{i}-b_{0}$; $z_{i}>=-y_{i}+b_{1}x_{i}+b_{0}$
or another way: . $$min \displaystyle\sum\limits_{i=1}^n |z_{i}^{+}+z_{i}^{-}|$$ subject to $z_{i}^{+}-z_{i}^{-}=y_{i}-b_{1}x_{i}-b_{0}$

My question is which way is "better" in terms of computational performance for a standard linear solver for large number of b coefficients and observations.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The problem is also known as a median regression which is a special case of a quantile regression. “For large number of $b$ coefficients and observations” using a standard solver is not going to be efficient. There are freely available tools to perform a median regression – e.g. R see http://hosho.ees.hokudai.ac.jp/~kubo/Rdoc/library/quantreg/html/rq.html The Barrodale and Roberts algorithm is a modified simplex method. If the problem is not too large, confidence intervals can be easily obtained.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The reason I've asked this question is that I want to use LAD LASSO regression $\min_{\beta} \left| \mathbb{y} - \mathbb{X} \boldsymbol{\beta}\right|_1 + \lambda \left|\boldsymbol{\beta}\right|_1$ and be able to have constraints on coefficients. I've asked it here: stats.stackexchange.com/questions/76538/… $\endgroup$
    – Math_manul
    Commented Dec 10, 2013 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .