On the Least Median Square Problem

Jeff Erickson, Sariel Har-Peled, David M. Mount · SCG '04 · 2004

Summary

This work considers the exact and approximate computational complexity of the multivariate LMS linear regression estimator, and provides nearly matching lowerbounds for these problems, under the assumption that deciding whether n given points in ℝ d are affinely nondegenerate requires Ω(nd) time.

Type: article
Published: 2004-06-08
Cited by: 42
References: 32
Access: Open access
DOI: https://doi.org/10.1145/997817.997859
OpenAlex: https://openalex.org/W2012297307
Semantic Scholar: https://api.semanticscholar.org/CorpusID:10998314

Keywords

Estimator, Hyperplane, Bounded function, Mathematics, Multivariate statistics

References

On the relative complexities of some geometric problemsJeff Erickson — 1995
Lower bounds for algebraic computation treesMichael Ben-Or — 1983
Lower bounds for linear satisfiability problemsJeff Erickson — 1995
Data structures for mobile dataJulien Basch, Leonidas Guibas, John Hershberger — 1997
Computational geometry - an introduction through randomized algorithmsK. Mulmuley — 1993
The Discrepancy Method: Randomness and ComplexityB. Chazelle — 2000
New lower bounds for convex hull problems in odd dimensionsJeff Erickson — 1996
On geometric optimization with few violated constraintsJiřı́ Matoušek — 1994
Geometric Applications of a Randomized Optimization TechniqueTimothy M. Chan — 1998
An Approximation Algorithm for Least Median of Squares RegressionClark F. Olson — 1997
On the Complexity of Approximating Extremal Determinants in MatricesLeonid Khachiyan — 1995
Computing Least Median of Squares Regression Lines and Guided Topological SweepHerbert Edelsbrunner, Diane L. Souvaine — 1990
Robust regression methods for computer vision: A reviewPeter Meer, Doron Mintz, Azriel Rosenfeld — 1991
HIGH BREAKDOWN-POINT AND HIGH EFFICIENCY ROBUST ESTIMATES FOR REGRESSIONVı́ctor J. Yohai — 1987
Randomized Optimal Algorithm for Slope SelectionJiřı́ Matoušek — 1991
Shape fitting with outliersSariel Har-Peled, Yusu Wang — 2003
A practical approximation algorithm for the LMS line estimatorDavid M. Mount, Nathan S. Netanyahu, Kathleen Romanik — 1997
Efficient Perturbations for Handling Geometric DegeneraciesIoannis Z. Emiris, John Canny, Raimund Seidel — 1997
A randomized algorithm for slope selectionMichael B. Dillencourt, David M. Mount, Nathan S. Netanyahu — 1992
Low-dimensional linear programming with violationsTimothy M. Chan — 2002

Cited by

View Synthesis from Image and Video for Object Recognition ApplicationsZhanfeng Yue — 2007
Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related ProblemsHu Ding, Jinhui Xu — 2014
Extended least trimmed squares estimator in semiparametric regression models with correlated errorsMahdi Roozbeh, Saman Babaie–Kafaki — 2016
Least quantile regression via modern optimizationDimitris Bertsimas, Rahul Mazumder — 2013
Fitting a Step Function to a Point Set with Outliers Based on Simplicial thickness Data StructuresDanny Z. Chen, Haitao Wang — 2012
A Robust Least Mean Square Algorithm for Adaptive Array Signal ProcessingRana Liaqat Ali, Shahid Khan, Anum Ali — 2013
NBS: A new representation for point surfaces based on genetic clustering algorithm: CAD and GraphicsYanci Zhang, Hanqiu Sun, Enhua Wu — 2008
On the Least Trimmed Squares EstimatorDavid M. Mount, Nathan S. Netanyahu, Christine Piatko — 2014
Fitting Flats to Points with OutliersGuilherme D. da Fonseca — 2011
SOCP relaxation bounds for the optimal subset selection problem applied to robust linear regressionSalvador Flores — 2015
Moving Object Verification in Airborne Video SequencesZhanfeng Yue, D. Guarino, Rama Chellappa — 2009
REGRESYON ANALİZİNDE KULLANILAN EN KÜÇÜK KARELER VE EN KÜÇÜK MEDYAN KARELER YÖNTEMLERİNİN KARŞILAŞTIRILMASIÖzgül Vupa, Özlem Gürünlü Alma — 2008
Segmentation and wake removal of seafaring vessels in optical satellite imagesHenri Bouma, Rob J. Dekker, Robin Schoemaker — 2013
Effiziente Algorithmen und Komplexität in der robusten StatistikThorsten Bernholt — 2006
VIDEO DENOISING USING SWITCHING ADAPTIVE DECISION BASED ALGORITHM WITH ROBUST MOTION ESTIMATION TECHNIQUEV. Jayaraj, D. D. Ebenezer, Manikandan S — 2010
GPU-Based Computation of 2D Least Median of Squares with Applications to Fast and Robust Line DetectionGil Shapira, Tal Hassner — 2015
Robust ridge estimator in restricted semiparametric regression modelsMahdi Roozbeh — 2016
Feasible robust estimator in restricted semiparametric regression models based on the LTS approachMahdi Roozbeh, Nor Aishah Hamzah — 2017
Least-trimmed squares: asymptotic normality of robust estimator in semiparametric regression modelsMahdi Roozbeh, ‎M‎ohammad Arashi — 2017
Efficient and Robust Median-of-Means Algorithms for Location and RegressionAlexander Kogler, Patrick Traxler — 2016

On the Least Median Square Problem

Summary

Keywords

References

Cited by

Related papers