Weighted median algorithms for \(L_ 1\) approximation

DOI10.1007/BF02017350zbMath0704.65044OpenAlexW1542365154MaRDI QIDQ917229

Chaya Gurwitz

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02017350

zbMATH Keywords

line searchComputational experiments\(L_ 1\) approximationlinear-time methodpartial heapsort methodpartial quicksort methodsorting methodsweighted median algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Numerical approximation and computational geometry (primarily algorithms) (65D99) Approximation by arbitrary linear expressions (41A45)

Related Items (11)

Off-diagonal symmetric nonnegative matrix factorization ⋮ Weighted Median of the Data in Solving Least Absolute Deviations Problems ⋮ The Kantorovich metric for probability measures on the circle ⋮ A linear time algorithm for a matching problem on the circle ⋮ Transportation distances on the circle ⋮ Laplace random effects models for interlaboratory studies ⋮ Searching for a best least absolute deviations solution of an overdetermined system of linear equations motivated by searching for a best least absolute deviations hyperplane on the basis of given data ⋮ Least absolute deviations problem for the Michaelis-Menten function ⋮ Three points method for searching the best least absolute deviations plane ⋮ Center-based l1–clustering method ⋮ THE BEST LEAST ABSOLUTE DEVIATIONS LINE – PROPERTIES AND TWO EFFICIENT METHODS FOR ITS DERIVATION

Uses Software

• Find
• Algorithm 489

Cites Work

• Unnamed Item
• Unnamed Item
• A linear selection algorithm for sets of elements with weights
• Time bounds for selection
• A quadratically convergent method for minimizing a sum of euclidean norms
• A Stable Algorithm for Solving the Multifacility Location Problem Involving Euclidean Distances
• Least Absolute Deviations Curve-Fitting
• Expected time bounds for selection
• Minimization Techniques for Piecewise Differentiable Functions: The $l_1$ Solution to an Overdetermined Linear System
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• An Improved Algorithm for Discrete $l_1 $ Linear Approximation

This page was built for publication: Weighted median algorithms for \(L_ 1\) approximation