Sparsity lower bounds for dimensionality reducing maps
Sparsity lower bounds for dimensionality reducing maps
复制标题
降维映射的稀疏下界
DOI：
10.1145/2488608.2488622
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Jelani Nelson;Huy L. Nguyen
我们给出了几个降维线性映射所需的稀疏性的近紧下界。首先，考虑Johnson-Lindenstrauss （JL）引理，该引理指出，对于R<sup>d</sup>中的任何<i>n</i>向量集，存在一个A∈R<sup>m x d</sup>，且m = O(ε<sup>-2</sup>log n)，使得<i>A</i>的映射保留了最大1 pm ε因子的对向欧氏距离。我们证明了存在一个n个向量的集合，使得当m < 0 （n/log(1/ε)）时，每列最多有s个非零元素的a必须有s = Ω（ε<sup>-1</sup>log n/log(1/ε)）。这改进了[Dasgupta-Kumar-Sarlos， STOC 2010]的Ω（min{ε<sup>-2</sup>, ε<sup>-1</sup>√(log<sub>m</sub> d)）的下界，该下界仅适用于分布JL的更强性质，并且仅适用于某些受限类分布。同时，我们的下界与JL引理本身相反，没有任何限制。我们的下界与[Kane-Nelson， SODA 2012]的稀疏JL上界匹配到O（log(1/ε)）因子。接下来，我们证明任何具有<i>k</i>限制等距性质（RIP）的m x n矩阵，如果m=O(k log(n/k))，则每列必须具有Ω（k log(n/k)）非零，这是RIP的最佳行数，并且k< n/polylog <i>n</i>。这改进了先前[Chandar， 2010]的Ω（min{k, n/m}）的下界，并表明对于大多数<i>k</i>，不可能有一个具有最优行数的稀疏RIP矩阵。
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the Johnson-Lindenstrauss (JL) lemma which states that for any set of <i>n</i> vectors in R<sup>d</sup> there is an A∈R<sup>m x d</sup> with m = O(ε<sup>-2</sup>log n) such that mapping by <i>A</i> preserves the pairwise Euclidean distances up to a 1 pm ε factor. We show there exists a set of n vectors such that any such A with at most s non-zero entries per column must have s = Ω(ε<sup>-1</sup>log n/log(1/ε)) if m < O(n/log(1/ε)). This improves the lower bound of Ω(min{ε<sup>-2</sup>, ε<sup>-1</sup>√(log<sub>m</sub> d)) by [Dasgupta-Kumar-Sarlos, STOC 2010], which only held against the stronger property of distributional JL, and only against a certain restricted class of distributions. Meanwhile our lower bound is against the JL lemma itself, with no restrictions. Our lower bound matches the sparse JL upper bound of [Kane-Nelson, SODA 2012] up to an O(log(1/ε)) factor. Next, we show that any m x n matrix with the <i>k</i>-restricted isometry property (RIP) with constant distortion must have Ω(k log(n/k)) non-zeroes per column if m=O(k log (n/k)), the optimal number of rows for RIP, and k < n/polylog <i>n</i>. This improves the previous lower bound of Ω(min{k, n/m}) by [Chandar, 2010] and shows that for most <i>k</i> it is impossible to have a sparse RIP matrix with an optimal number of rows.
Both lower bounds above also offer a tradeoff between sparsity and the number of rows.
Lastly, we show that any oblivious distribution over subspace embedding matrices with 1 non-zero per column and preserving distances in a d dimensional-subspace up to a constant factor must have at least Ω(d<sup>2</sup>) rows. This matches an upper bound in [Nelson-Nguyên, arXiv abs/1211.1002] and shows the impossibility of obtaining the best of both of constructions in that work, namely 1 non-zero per column and d ⋅ polylog <i>d</i> rows.