关于忽略子空间嵌入的下界
给定任意正实数 θ，我们证明对于 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
本研究提出了一种 Oblivious Subspace Embedding (OSE) 技术以及两种 Oblivious Sparse Norm-Approximating Projections (OSNAPs) 技术，基于随机矩阵理论，用于加速数值线性代数问题解决，诸如近似最小二乘回归，低秩逼近和逼近杠杆分数。
Nov, 2012
研究了将单位球面子集嵌入到 Hamming 立方体中的方法，利用高斯宽度表征了失真和样本复杂度之间的权衡关系，并提供了嵌入点的局部嵌入以及更快的二进制嵌入等改进方案。
Dec, 2015
通过对具有 k 阶和级别 δ 的稀疏矩阵 Phi 进行列符号随机化，该结果可以很好地嵌入 R^N 中的任何固定点集至 R^m 中，是 Johnson-Lindenstrauss 嵌入的最优算法，在部分 Fourier 和部分 Hadamard 矩阵中，该算法优于各种最优算法。此外，该研究结果在冗余字典的压缩感知中也具有直接应用。
Sep, 2010
提出了一种低失真度嵌入方法，在线性代数问题中得到广泛应用，支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入，包括一种基于输入稀疏性的 l_p 子空间采样过程。
Oct, 2012
给定 $n$ 个 $d$ 维实向量，存在一个嵌入函数将这些向量映射到更低的维度 $m$，满足它保留这些向量之间的欧几里得距离并且它需要的最低维度是 $O (\epsilon^{-2} \log n)$，其中 $\epsilon$ 是距离阈值，这个结果匹配 Johnson-Lindenstrauss 引理的上界。
Sep, 2016
本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。
Jul, 2012
研究子空间草图问题，通过构建一个小空间数据结构压缩给定矩阵，讨论其压缩方案和所需存储空间以及相应的下界，探讨其在矩阵乘积中的应用，展示了对内积基于任意数构建数据结构的不可行性以及 l1 奇异值分解的不同情况下的空间复杂度变化。
Apr, 2019