What is the most efficient way to solve linear Least absolute deviation regression problem?

I know it can be solved using linear programming, is there a better/faster method?

Edit: I'm interested in the more theoretical aspect, hence by "efficient" I mean that it have some type of upper bound on its run-time.

  • $\begingroup$ If you are going to use a non-linear solver such as Levenberg-Marquardt or Gradient Descent, you will need good initial parameter estimates for the solver. If you can use standard OLS to get the sum-of-squared-error solution, this is usually close to the LAD solution and can be used as initial parameter estimates. $\endgroup$ – James Phillips Feb 10 at 21:35
  • $\begingroup$ Is your answer based on rigorous bounds for the running time or by empirical observations? $\endgroup$ – Meni Feb 11 at 4:58
  • 1
    $\begingroup$ My comment was intended as a potentially helpful suggestion regarding initial parameter estimates only. $\endgroup$ – James Phillips Feb 11 at 9:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.