Optimization Online


Approximating L1-Norm Best-Fit Lines

JP Brooks(jpbrooks***at***vcu.edu)
JH Dulá(jhdula***at***cba.ua.edu)

Abstract: 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.

Keywords: L1-norm line fitting; L1-norm location; L1-norm subspace estimation; weighted median; L1-norm principal component analysis

Category 1: Applications -- Science and Engineering (Data-Mining )


Download: [PDF]

Entry Submitted: 01/09/2019
Entry Accepted: 01/09/2019
Entry Last Modified: 01/09/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society