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 p0, ..., pn, LMS finds a line q0, q1 that minimizes the median of the square of distances of p0, ..., pn. 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.

Comments