# Paper Review: A practical approximation algorithm for LMS line estimator

## Authors: David M. Mount, Nathan S. Netanyahu, Kathleen Romanik, Ruth

Silverman, Angela Y. Wue

## Keywords:

- LMS estimator
- O(n logn)
- bracelet
- slab
- random
- approximation
- quantiles

## Q1: What is LMS?

Given a set of points *p*_{0}, ..., *p*_{n}, LMS finds a line
*q*_{0}, *q*_{1} that minimizes the *median* of the square of distances
of *p*_{0}, ..., *p*_{n}. This is in contrast with summing up all the
squared distances and minimize them as in OLS (Ordinary Least Squares.)

## Q2: How approximations are done using LMS?

There are exact solutions for the LMS problem. This paper presents an
algorithm with lower complexity. It tries to find an LMS approximation
in a band defined by a parameter *ϵ*_{r}.

## Q3: Which parameters does the algorithm depend?

The algorithm *approxLMS* depends of a set of lines, a set of quantiles,
and two error bounds *ϵ*_{r} and *ϵ*_{q}.

## Q4: How can this help in our line approximations?

This paper is aimed towards providing an efficient algorithm for random
approximations. Since we need *repeatability* in our keypoint detection,
it might be harder (or impossible) to prove that the algorithm produces
exact same line endings in each run with similar set of points. Hence,
it's not usable in our studies.