本文章介绍了一种改进基于核方法的机器学习方法运行时间的方法，并提出了一个计算算法，该算法可以用来在不需要生成全核矩阵的情况下，对特征向量矩阵进行采样，并在统计表现和运行时间方面提供了新的保证。

Nov, 2014

本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。

Jul, 2012

提出了一种低失真度嵌入方法，在线性代数问题中得到广泛应用，支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入，包括一种基于输入稀疏性的 l_p 子空间采样过程。

Oct, 2012

本文研究了计算有效的低秩核近似的限制，证明计算相对误差 k 秩逼近 K 对于广泛类别的核，包括高斯和多项式核，至少与将输入数据矩阵 A 乘以任意矩阵 C 一样困难，并给出了一些希望：首次证明对于一般的径向基函数核， 如高斯核，存在 $O (nnz (A))$ 的时间近似方法。

Nov, 2017

论文提出了一种基于 rank minimization 算法的在线优化方法，通过追踪低维度子空间、揭示潜在结构以及使用核范数正则化来实现低维矩阵数据和低秩张量数据的缺失值插补，模拟测试显示该方法在数据明显含噪、不完整的情况下表现突出。

Apr, 2014

提出了一种新的高维随机优化方法，将坐标下降法推广到随机子空间，证明了使用自适应采样策略的随机子空间可以显著优于最近文献中常见的盲目采样方法，可以通过相关随机矩阵集合有效生成自适应子空间；在具有不同谱衰减的数据矩阵上验证了该方法在机器学习问题中的速度优势，包括逻辑回归、带随机卷积层的核分类和具有修正线性单元的浅神经网络。

Jun, 2019

提出了一种通用方法，可将数值线性代数中的随意草图解决方案应用于数据点的张量，从而根据多项式内核函数的大小开发了第一个仅在目标维度上具有多项式依赖性的多项式内核的忽略草图，并且无需因输入数据维数而遭受指数依赖。

Sep, 2019

这篇论文研究数据分析中的线性回归和数据素描技术，探讨在样本量有限的情况下如何选择行列子集对数据进行估计和推断，发现虽然算法上的优化子集无法适用于预测和推断，但通过统计学方法可以提供建议的子集大小，并通过实验表明，使用不同的子集来估计结果可以将预测结果效率与使用全样本的方法几乎相同。

Jul, 2019

介绍了一种名为 SQUEAK 的基于 RLS 抽样的核逼近算法，可以在线性时间内生成精确的核矩阵近似，并且只需处理数据集一次；同时还提出了一个并行和分布式版本，可在对数时间内线性扩展到多台机器上。

Mar, 2018

该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近，相较于之前基于随机投影的算法，该方法可适用于稀疏结构等场景，并在核矩阵逼近算法方面表现最优。

Nov, 2015