找平面上最优的k个点以最大化R²，提出高效组合优化算法。
Combinatorial optimization of the coefficient of determination
- 将点投影到R⁵，用二次可分性寻找最优子集
- 在n≤30时实验验证无错误，时间复杂度O(n⁵ log n)
- 适合需要鲁棒相关性分析的统计与数据科学场景
稳健的相关性分析是统计学中最关键的挑战之一。本文提出一种高效算法，用于从平面上n个点中选出使决定系数（R²）最大的k-子集。基于组合几何，我们设计了名为‘二次扫掠’（quadratic sweep）的方法：首先将数据点投影至ℝ⁵，然后遍历所有线性可分的k-子集。其核心思想是：最优异常值集与其余点在ℝ²中可由二次曲线分离，该分离在ℝ⁵中可通过拓扑扫掠在Θ(n⁵ log n)时间内完成。尽管二次可分性的严格证明仍在进行中，但我们建立了强数学直觉，并通过数百万次实验在n≤30范围内验证了方法的最优性且未出现错误。Julia实现及完全可复现的实验代码已公开于https://github.com/marc-harary/QuadraticSweep。
原文摘要 · Abstract (English)
Robust correlation analysis is among the most critical challenges in statistics. Herein, we develop an efficient algorithm for selecting the $k$- subset of $n$ points in the plane with the highest coefficient of determination $\left( R^2 \right)$. Drawing from combinatorial geometry, we propose a method called the \textit{quadratic sweep} that consists of two steps: (i) projectively lifting the data points into $\mathbb R^5$ and then (ii) iterating over each linearly separable $k$-subset. Its basis is that the optimal set of outliers is separable from its complement in $\mathbb R^2$ by a conic section, which, in $\mathbb R^5$, can be found by a topological sweep in $Θ\left( n^5 \log n \right)$ time. Although key proofs of quadratic separability remain underway, we develop strong mathematical intuitions for our conjectures, then experimentally demonstrate our method's optimality over several million trials up to $n=30$ without error. Implementations in Julia and fully seeded, reproducible experiments are available at https://github.com/marc-harary/QuadraticSweep.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。