随机投影的精确表达式：低秩逼近与随机牛顿

MMJun, 2020

随机投影的精确表达式：低秩逼近与随机牛顿

Precise expressions for random projections: Low-rank approximation and randomized Newton

Michał Dereziński, Feynman Liang, Zhenyu Liao, Michael W. Mahoney

TL;DR利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。

Abstract

It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. matrix sketching has emerged as a powerful technique for performing such dimensionality reduction

matrix sketching dimensionality reduction random projection matrices spectral analysis machine learning

发现论文，激发创造

低秩矩阵近似的实用素描算法

该论文介绍了构建输入矩阵的低秩近似的算法套件，这些算法使用矩阵的随机线性图像（称为草图）。这些方法可以保留输入矩阵的结构特性，如半正定性，并且可以生成具有用户指定秩的近似值。此外，每种方法都伴随着一个信息性误差界，允许用户预先选择参数以实现所需的近似质量。这些论断受真实和合成数据的数字实验支持。

Aug, 2016

具有统计保证的随机降维

研究论文通过研究快速执行和数据利用的算法，探索了大型模型和数据利用的有效维度减少策略，以及提高泛化和分布鲁棒性的数据增强方法。

Oct, 2023

草图作为数值线性代数工具

本文综述了数值线性代数算法领域的最新进展，着重介绍了利用线性草图技术来进行矩阵压缩的方法，以加速解决原问题。文章讨论了最小二乘、鲁棒回归、低秩逼近和图稀疏化的问题，并优化了这些问题的不同变体。最后，文章探讨了草图方法的局限性。

Nov, 2014

k-Means 聚类和低秩逼近的降维

研究采用缩略图替代数据矩阵来加速 k - 均值聚类和约束 k - 秩近似问题的精确、近似或启发式算法，并提供降维和草图技术及近似算法来解决这些普遍问题。

Oct, 2014

普通最小二乘问题中基于随机草图的统计角度分析

对大规模最小二乘问题的解决方法采用随机草图算法的统计和算法方面进行了考虑，提出了算法和统计两种框架并比较其性能，并且证明了在使用随机投影和随机抽样算法的情况下，当样本数为 $r$，且 $p<r<n$ 时，算法误差与原始问题的误差相同。

Jun, 2014

迭代 Hessian 草图：约束最小二乘问题的快速准确解近似

本文研究了随机草图方法，以近似解决带有一般凸约束的最小二乘问题，并提出了一种名为迭代 Hessian 草图的新方法，同时提供了数值模拟实验，包括面部表情分类实验。

Nov, 2014

具有尖锐保证的凸规划的随机草图

该研究探讨了使用随机投影进行维度降低的方法来近似解决具有凸性质的问题，在计算有限的情况下具有广泛的应用，同时还可以提高隐私保护和降低存储和计算成本。研究证明了该方法的近似比率可以用约束集合的几何特性来界定，对于一类广泛的随机投影，其投影结果数据矩阵的维度相对于原始问题的维度相对较小，该理论还与降噪、压缩感知等领域有关系。

Apr, 2014

草图算法的统计性质

该论文介绍了一种称为 “sketching” 的数据压缩技术，该技术通过随机投影将大型数据集压缩成较小的替代数据集，然后进行统计分析，该方法特别适用于大规模的线性回归问题。

Jun, 2017

正则化数据拟合的更锐利界限

研究针对线性回归、低秩逼近和规范相关分析的正规化变体的矩阵草图方法，主要关注能够保留规范问题目标函数值的草图技术，为 ridge regularization 在这些问题上展示了算法资源界限，其中统计维度总是小于秩，并随着规范化程度的增加而减少

Nov, 2016

一种解决降秩算子回归的随机算法

我们提出并分析了一种算法，用于解决涉及可能是无限维输入和输出空间的矢量值回归问题。该算法是降低秩回归的随机化改进，通过带有秩约束的正则化经验风险最小化来优化学习低秩矢量值函数（即运算符）与采样数据之间的关系。我们提出了基于高斯草图技术的原始和对偶优化目标，产生了高效准确的随机降秩回归（R4）估计器。对于我们的每个 R4 算法，我们证明了在适当调整超参数的情况下，随机草图的随机性的期望下，所得到的正则化经验风险将任意接近最优值。数值实验证明了我们界限的紧凑性，并展示了两种不同情景的优势：（i）使用合成和大规模神经科学数据集解决矢量值回归问题，以及（ii）回归非线性随机动力系统的 Koopman 运算符。

Dec, 2023