@Article{souvaine87time,
  author   = {Diane L. Souvaine and J. Michael Steele},
  title    = {Time- and Space-Efficient Algorithms for Least Median of Squares Regression},
  journal  = {J Am Stat Assoc},
  year     = {1987},
  volume   = {82},
  number   = {399},
  pages    = {794--801},
  abstract = {The least median of squared residuals regression line (or LMS line) is that line $y = ax + b$ for which the median of the residuals $|y_i - ax_i - b|^2$ is minimized over all choices of $a$ and $b$. If we rephrase the traditional ordinary least squares (OLS) problem as finding the $a$ and $b$ that minimize the mean of $|y_i - ax_i - b|^2$, one can see that in a formal sense LMS just replaces a ``mean'' by a ``median.'' \dots Two algorithms are given here that determine the LMS regression line for $n$ points in the plane, using $O(n^2 \log n)$ time and $O(n)$ space and $O(n^2)$ time $O(n^2)$ space, respectively.},
  keywords = {phylogenetics},
}

{"_id":"ftmZyRCzbHxMngkEx","bibbaseid":"souvaine-steele-timeandspaceefficientalgorithmsforleastmedianofsquaresregression-1987","authorIDs":[],"author_short":["Souvaine, D. L.","Steele, J. M."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Diane","L."],"propositions":[],"lastnames":["Souvaine"],"suffixes":[]},{"firstnames":["J.","Michael"],"propositions":[],"lastnames":["Steele"],"suffixes":[]}],"title":"Time- and Space-Efficient Algorithms for Least Median of Squares Regression","journal":"J Am Stat Assoc","year":"1987","volume":"82","number":"399","pages":"794–801","abstract":"The least median of squared residuals regression line (or LMS line) is that line $y = ax + b$ for which the median of the residuals $|y_i - ax_i - b|^2$ is minimized over all choices of $a$ and $b$. If we rephrase the traditional ordinary least squares (OLS) problem as finding the $a$ and $b$ that minimize the mean of $|y_i - ax_i - b|^2$, one can see that in a formal sense LMS just replaces a ``mean'' by a ``median.'' ṡ Two algorithms are given here that determine the LMS regression line for $n$ points in the plane, using $O(n^2 łog n)$ time and $O(n)$ space and $O(n^2)$ time $O(n^2)$ space, respectively.","keywords":"phylogenetics","bibtex":"@Article{souvaine87time,\n author = {Diane L. Souvaine and J. Michael Steele},\n title = {Time- and Space-Efficient Algorithms for Least Median of Squares Regression},\n journal = {J Am Stat Assoc},\n year = {1987},\n volume = {82},\n number = {399},\n pages = {794--801},\n abstract = {The least median of squared residuals regression line (or LMS line) is that line $y = ax + b$ for which the median of the residuals $|y_i - ax_i - b|^2$ is minimized over all choices of $a$ and $b$. If we rephrase the traditional ordinary least squares (OLS) problem as finding the $a$ and $b$ that minimize the mean of $|y_i - ax_i - b|^2$, one can see that in a formal sense LMS just replaces a ``mean'' by a ``median.'' \\dots Two algorithms are given here that determine the LMS regression line for $n$ points in the plane, using $O(n^2 \\log n)$ time and $O(n)$ space and $O(n^2)$ time $O(n^2)$ space, respectively.},\n keywords = {phylogenetics},\n}\n\n","author_short":["Souvaine, D. L.","Steele, J. M."],"key":"souvaine87time","id":"souvaine87time","bibbaseid":"souvaine-steele-timeandspaceefficientalgorithmsforleastmedianofsquaresregression-1987","role":"author","urls":{},"keyword":["phylogenetics"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.688Z","downloads":0,"keywords":["phylogenetics"],"search_terms":["time","space","efficient","algorithms","median","squares","regression","souvaine","steele"],"title":"Time- and Space-Efficient Algorithms for Least Median of Squares Regression","year":1987,"dataSources":["C5FtkvWWggFfMJTFX"]}