任意集合的二元嵌入的近似最优界限
本文提出了一种基于二进制编码的非线性降维方法,能够在保留原始空间结构的同时,将高维数据嵌入到汉明立方体中,实现对任意集合中点的编码,并在理论上证明了该方法的最优位数下界及哈明距离下的非遗忘式编码,同时针对一般点集甚至无限点集提供了分析结果,并通过实验验证了理论结论的有效性。
Feb, 2015
本文提出了一种基于量化的快速 Johnson-Lindenstrauss 嵌入法,该方法使用有界正交系统和部分循环集合进行快速的嵌入,并利用噪声整形实现积极的降噪机制,该方法的误差多项式和指数衰减,是当前二进制嵌入和汉明距离所能达到的巅峰效果;此外,本文还提出了一种基于噪声整形机制的量化压缩感知度量方法,该方法在测量值的数量和比特数上实现了误差的多项式和指数衰减,是目前处理有限正交系统的最优表现。
Jan, 2018
本文介绍了如何使用 Fourier 转换,尤其是环移矩阵来进行二进制嵌入,即将高维空间中的点映射到低维的 Hamming 立方体中以保留成对距离。作者提出了优化的方法,可以通过使用 k ~ δ^(-3) logN 个样本将 N 个 R^n 中的点正确地嵌入到 Hamming 立方体中,优于最优距离依赖关系 δ^(-2),适用于标准条件 logN≲n^(1/3)。此外,如果满足 logN≲sqrt (n) 的较宽松条件,则可以将除随机小分数以外的所有点置于最优位置。该文认为此任务可以应用于其他非线性嵌入问题,并提出它可能有用的保证改进技术。
Mar, 2016
给定 $n$ 个 $d$ 维实向量,存在一个嵌入函数将这些向量映射到更低的维度 $m$,满足它保留这些向量之间的欧几里得距离并且它需要的最低维度是 $O (\epsilon^{-2} \log n)$,其中 $\epsilon$ 是距离阈值,这个结果匹配 Johnson-Lindenstrauss 引理的上界。
Sep, 2016
给定任意正实数 θ,我们证明对于 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
本文考虑使用随机矩阵将具有边界的流形嵌入到低维空间中,进而得出一类新的结构化矩阵分布,其在嵌入低维流形方面具有优势,并且可以用于构造 log^cN 维的 Johnson-Lindenstrauss 嵌入矩阵,并且在计算矩阵乘法的复杂度上仅仅是 O (N log (logN))。
Oct, 2021
介绍了一种针对线性子空间的随机映射方法 ——Oblivious Subspace Embedding (OSE),通过稀疏性限制,证明了 m 与 s 之间存在权衡下限。
Aug, 2013
本文研究如何通过二进制嵌入方法在保留向量之间的角度距离信息的同时,将一个有限向量集编码为少量比特位。通过推导出与二元高斯循环嵌入相关的改进方差界,我们基本上解决了最佳快速二进制嵌入方法的证明中的漏洞。我们的界限也表明,早期关于方差界的工作中需要的数据向量分散的假设是不必要的。此外,我们提出了一种在稀疏数据上具有更快运行时间的二元嵌入方法。
Aug, 2016