Apr, 2010

稀疏的 Johnson--Lindenstrauss 变换

PDF
TL;DR本文提出了在流模型中使用哈希和本地密集方法构造的 Johnson-Lindenstrauss 变换的稀疏版本，其每列仅具有 $\tilde {O}(\frac {1}{\epsilon})$ 非零条目，可以实现 $(1±\epsilon)$- 近似投影的更新时间为 $\tilde {O}(\frac {1}{\epsilon})$，这大大优于以前的方法所需的 $\tilde {O}(\frac {1}{\epsilon^2})$ 更新时间。
dimension reductionjohnson-lindenstrauss transformsparse projection matrixalgorithmstreaming model
发现论文，激发创造
  • Sparser Johnson-Lindenstrauss 变换

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

    Dec, 2010

  • 欧几里德空间稀疏降维统一理论探索

    研究了一个基于稀疏 Johnson-Lindenstrauss 变换的几何设置，它在 T 上保存每个 x 的范数，从而推导出一种关于几何复杂度的新参数，并且该参数可以帮助限制需要 M、S 的大小。这一结果是 Gordon 定理的稀疏模拟，并且该方法可应用于经典和基于模型的压缩感知、流形学习和约束最小二乘问题等领域。

    Nov, 2013

  • 几乎最优的无限制快速 Johnson-Lindenstrauss 变换

    利用 Banach 空间中的概率新工具，将随机投影问题的研究推进到一个新的水平。其主要结果是可以线性映射任意 $N$ 个 $n$ 维实向量到一个 $O (log N polylog (n))$ 线性空间中，并在保持向量之间距离一定畸变的同时，对每个向量的映射可以在 $O (n log n)$ 时间内完成。

    May, 2010

  • Johnson-Lindenstrauss 变换本身保持差分隐私

    此篇论文证明了经典的 Johnson-Lindenstrauss 变换具备保护差分隐私的新途径，同时将其应用于近似割查询和矩阵方向方差的估计，并提供了一种公开的方式来保证矩阵的奇异值满足上界。

    Apr, 2012

  • 通过约翰逊 - 林登斯特劳斯变换实现隐私保护

    通过使用稀疏约翰逊 - 林登斯特劳斯变换和高斯噪声对低维用户表示进行发布，以实现差分隐私，并利用这些数据来计算用户之间的距离。

    Apr, 2012

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

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

    Oct, 2014

  • Johnson-Lindenstrauss 变换在 k-Means 和 k-Medians 聚类中的表现

    通过投影到随机的 O (log (k/ ε) / ε²) 维子空间上，可以近似保持欧几里得 k-means 或 k-medians 聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得 k - 聚类。

    Nov, 2018

  • 一种去随机化的稀疏 Johnson-Lindenstrauss 变换

    本文提出一种替代方法，利用有界独立哈希函数和谱矩估计性质，对 Dasgupta-Kumar-Sarlos (STOC 2010) 提出的基于稀疏 Johnson-Lindenstrauss 变换的深入研究，并得到了更好的稀疏限制。

    Jun, 2010

  • 子高斯矩阵的降维：一种统一的理论

    本文提出了利用次高斯矩阵进行欧几里德降维的理论，该理论统一了先前针对特定数据集获得的几个限制等距性和约翰逊 - 林登斯特劳斯类型结果。特别是，我们恢复了并在多种情况下改进了关于稀疏向量、结构化稀疏向量、低秩矩阵和张量、平滑流形集合的结果。此外，本文还为采用 Hilbert 空间子空间无限并形式的数据集建立了新的约翰逊 - 林登斯特劳斯嵌入。

    Feb, 2014

  • 通过 Kronecker 积实现更快的 Johnson-Lindenstrauss 变换

    这项研究提出了一种基于 Kronecker 序列的嵌入矩阵快速生成技术，名为 Kronecker 快速 Johnson-Lindenstrauss 变换（KFJLT），能用于大规模 Kronecker 结构的最小二乘问题拟合的高效求解。

    Sep, 2019