通过简单的迭代行抽样算法和加权少数行使每个矩阵的相干度低,我们能够使用随机抽取行的方式进行矩阵近似,以大大提高数据处理速度。
Aug, 2014
该研究提出新的算法解决回归问题中的稀疏数据,基于迭代法中计算行重要性(行杠杆力分数)的方法,达到比现有技术更好的理论保证。
Nov, 2012
提出一种随机算法来处理大规模数据量的分位数回归问题,该算法在近线性时间内计算给定分位数回归问题的(1+ϵ)近似解,并计算量子回归损失函数的低失真子空间保持嵌入。
May, 2013
本文提出了针对 Quantile Regression 的多个高效确定性和随机多项式算法,连接到 k 集的几何概念和随机分治算法,分别解决了二维和多维 Quantile Regression 问题。
Jul, 2023
本论文构建了一个高效的量子矩阵反演算法(HHL)的经典模拟器,基于 Tang 的最近研究成果,通过对输入数据进行长度平方采样,实现了低秩矩阵的伪逆并使用快速抽样技术从问题 $Ax=b$ 的解中采样。本文通过子采样来找到 $A$ 的近似奇异值分解,从而实现伪逆。该方法也可用于把任何期望的 “平滑” 函数应用到奇异值上。既然许多量子算法可以表示为奇异值变换问题,我们的结果表明更多的低秩量子算法可以有效地 “去量子化” 成为使用长度平方采样的经典算法。
Nov, 2018
本文研究了具有重尾噪声的高维线性回归模型的分布式估计和支持恢复,并采用分位数回归损失函数来处理噪声。我们提出了一种计算和通信效率高的分布式估计器,理论上表明该方法在少数迭代后即能达到近乎理想的收敛速度,并且还为支持恢复提供了理论保证。
Jun, 2019
分布式估计和支持恢复在高维线性分位数回归中具有重要意义,本文通过将原始分位数回归转化为最小二乘优化问题,并应用双平滑方法,提出了一种新的分布式方法来解决此类问题,在保证计算和通信效率的同时能够实现接近 Oracle 收敛速度和高支持恢复精度的估计结果。通过对合成实例和真实数据应用的大量实验,验证了该方法的有效性。
May, 2024
本研究讨论了滑动窗口模型下的数值线性代数问题,提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题,同时通过与在线模型的联系,提出了正文算法,并应用于列 / 行选择、主成分分析等问题。此外,研究还提出了一种新的框架,包括了融合和减少范式和在线核的概念,并且通过行到达在线模型给出了在线核,最终得到了差不多最优空间的定向算法。
May, 2018
这篇论文详细介绍了基于体积采样技术的线性回归问题解决方案,实验证明该算法不仅可行,而且精度较高。
Jun, 2018
探讨了在普通最小二乘回归中,找到或推翻删除数据集中的小子集会反转系数符号的实用算法;通过实证研究了用于此任务的成熟算法技术在一般线性回归问题和特殊情况下的精确贪婪方法方面的性能,证明这些方法在几个维度的回归问题中优于现有技术并提供了实用的鲁棒性检查;但对于维度为 3 或更高的回归问题中推翻这种小型影响样本存在性的重要任务仍存在显著的计算瓶颈;通过使用源自算法稳健统计的最新创新思想的谱算法在这一挑战中取得了一些进展;总结了在几个挑战数据集中,已知技术的限制,以促进进一步的算法创新。