Approximating L1-Norm Best-Fit Lines

Sufficient conditions are provided for a deterministic algorithm for estimating an L1-norm best-fit one-dimensional subspace. To prove the conditions are sufficient, fundamental properties of the L1-norm projection of a point onto a one-dimensional subspace are derived. Also, an equivalence is established between the algorithm, which involves the calculation of several weighted medians, and independently-derived algorithms based on finding L1-norm solutions to overdetermined system of linear equations, each of which may be calculated via the solution of a linear program. The equivalence between the algorithms implies that each is a 2-factor approximation algorithm, which is the best-known factor among deterministic algorithms, and that the method based on weighted medians has the smallest worst-case computational requirements.



View Approximating L1-Norm Best-Fit Lines