论文标题
快速的约翰逊·林斯特劳斯的变换甚至更快
The Fast Johnson-Lindenstrauss Transform is Even Faster
论文作者
论文摘要
由Ailon和Chazelle（Sicomp'09）转换的开创性Johnson-Lindenstrauss（Fast JL）将一组$ n $嵌入$ d $ d $二维的Euclidean Space中的空间中的$ k = o（\ varepsilon^{-2}} \ varepsilon）$。快速JL变换支持计算$ O（d \ ln d +k \ ln^2 n）$时间的数据点的嵌入，其中$ d \ ln d $项来自带有$ d \ times d $ d $ hadamard matrix和$ k \ ln^2 n $ termplication的乘法，来自少量$ k \ k \ plication。尽管快速的JL转换已有十多年的历史，但它是$ \ varepsilon，d $和$ n $的许多权衡方面的最快降低技术之一。 在这项工作中，我们对快速JL变换进行了令人惊讶的新分析，表明嵌入时间中的$ k \ ln^2 n $项可以提高到$（k \ ln^2 n）/α$，用于$α=ω（\ min \ min \ \ min \ \ {\ varepsilon^{\ varepsilon^{ - 1} { - 1} { - 1} \ ln（1/\ ln）（1/\ n（1/\ \ n \ n）$ n（1/\ \ n \ n \ n \ n \ n（1/\ n \ n \ n）$ n（1/\ \ n \ n \ \ n（1/\ n）。通过使用更稀疏的矩阵来改进。我们还通过下限进行补充，表明我们的新分析实际上很紧张。
The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of $n$ points in $d$-dimensional Euclidean space into optimal $k=O(\varepsilon^{-2} \ln n)$ dimensions, while preserving all pairwise distances to within a factor $(1 \pm \varepsilon)$. The Fast JL transform supports computing the embedding of a data point in $O(d \ln d +k \ln^2 n)$ time, where the $d \ln d$ term comes from multiplication with a $d \times d$ Hadamard matrix and the $k \ln^2 n$ term comes from multiplication with a sparse $k \times d$ matrix. Despite the Fast JL transform being more than a decade old, it is one of the fastest dimensionality reduction techniques for many tradeoffs between $\varepsilon, d$ and $n$. In this work, we give a surprising new analysis of the Fast JL transform, showing that the $k \ln^2 n$ term in the embedding time can be improved to $(k \ln^2 n)/α$ for an $α= Ω(\min\{\varepsilon^{-1}\ln(1/\varepsilon), \ln n\})$. The improvement follows by using an even sparser matrix. We also complement our improved analysis with a lower bound showing that our new analysis is in fact tight.
