介绍了一种针对线性子空间的随机映射方法 ——Oblivious Subspace Embedding (OSE)，通过稀疏性限制，证明了 m 与 s 之间存在权衡下限。

Aug, 2013

给定任意正实数 θ，我们证明对于 m≥(1+θ) d 且具有每列 O (log^4 (d)) 非零元素的 m×n 随机矩阵 S，它是一个 ε=O_θ(1) 的忽略子空间嵌入。这个结果解答了 Nelson 和 Nguyen（FOCS 2013）提出的问题，并改进了 Cohen（SODA 2016）的结果，我们将其应用于比当前矩阵乘法更快的 O (d) 嵌入维度的嵌入以及最佳单次通过最小二乘回归的算法。此外，我们还将结果扩展到构造非忽略嵌入，产生具有低失真 ε=o (1) 和最佳嵌入维度 m=O (d/ε^2) 的子空间嵌入。

Nov, 2023

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

Jul, 2012

用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

Jul, 2015

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

Oct, 2012

本文从子空间嵌入的角度出发，提出了一种构造常数扭曲率子空间嵌入的新方法，并将其应用于线性回归问题以及分布式计算中。

May, 2013

本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。

Jun, 2018

本研究讨论了滑动窗口模型下的数值线性代数问题，提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题，同时通过与在线模型的联系，提出了正文算法，并应用于列 / 行选择、主成分分析等问题。此外，研究还提出了一种新的框架，包括了融合和减少范式和在线核的概念，并且通过行到达在线模型给出了在线核，最终得到了差不多最优空间的定向算法。

May, 2018

本研究提供了两种简单的 $l_2$ 线性映射降维构造方法，通过使用稀疏嵌入矩阵使扭曲度达到 $1 + \varepsilon$，并在行数方面达到渐近优化，从而实现子常数稀疏，在所有参数值方面均优于先前的研究，并可用于加速应用程序中的 $l_2$ 维度约减。

Dec, 2010

研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。

Oct, 2015