Time- and Space-Efficient Algorithms for Least Median of Squares Regression
最小平方残差中位数回归的时间与空间高效算法AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要研究一般稳健回归的计算算法，残差取中位数并不直接构成条件分位数或分布效应研究。
反馈分类问题正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
最小平方残差中位数回归的时间与空间高效算法
- 研究问题
- 最小平方残差中位数回归的目标可能存在大量局部极小值，如何为平面样本计算全局最优直线并控制计算成本？
- 方法与思路
- 作者借助仿射对偶构造两种算法，分别使用扫描线技术与直线排列的搜索数据结构，以不同空间开销完成优化。
- 材料陈述的贡献
- 摘要称两种算法均能求得最优回归直线，并提供不同的时间与空间权衡，同时通过示例展示该回归处理异常群组的用途。
- 阅读关注点
- 应核对全局最优性的论证、仿射对偶的实现、并列残差等情形的处理，以及复杂度界和应用维度的限制。
- 阅读边界
- 依据版本未注明的索引摘要；复杂度表达的上标疑似丢失，需查原PDF确认，不能据此重构精确阶数或推断高维适用性。
原文摘要
The least median of squared residuals regression line (or LMS line) is that line y = ax + b for which the median of the residuals |yi - axi - b |2 is minimized over all choices of a and b. If we rephrase the traditional ordinary least squares (OLS) problem as finding the a and b that minimize the mean of | yi - axi - b |2, one can see that in a formal sense LMS just replaces a “mean” by a “median.” This way of describing LMS regression does not do justice to the remarkable properties of LMS. In fact, LMS regression behaves in ways that distinguish it greatly from OLS as well as from many other methods for robustifying OLS (see, e.g., Rousseeuw 1984). As illustrations given here show, the LMS regression line should provide a valuable tool for studying those data sets in which the usual linear model assumptions are violated by the presence of some (not too small) groups of data values that behave distinctly from the bulk of the data. This feature of LMS regression is illustrated by the fit given in Figure 1 and the residual plots of Figures 2a and 2b. The LMS regression line is an attractive tool for data analysis, but it is not easy to compute. Steele and Steiger (1986) established that the function f(a, b) = median {| yi - axi - b |2} can have on the order of n 2 local minima, so typical local methods have little hope of finding the global minimum of f. The main objective of this article is to provide algorithms that do minimize f and are efficient in terms of both time and space. Two algorithms are given here that determine the LMS regression line for n points in the plane. Both of these algorithms draw their strength from the systematic use of affine duality, and one objective pursued here is the exposition of the technique of affine duality so that it will become more commonly considered by statisticians. The first algorithm uses the so-called sweep-line technique, and it runs in worst-case time complexity O(n 2 log n), using only O(n) space. The second algorithm depends on the recent development of data structures that permit the economical searching of the arrangement determined by n lines. It requires only O(n 2) time, but the space needed is raised to O(n 2).