Sparsity lower bounds for dimensionality reducing maps
From MaRDI portal
Abstract: We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the JL lemma which states that for any set of n vectors in R there is a matrix A in R^{m x d} with m = O(eps^{-2}log n) such that mapping by A preserves pairwise Euclidean distances of these n vectors up to a 1 +/- eps factor. We show that there exists a set of n vectors such that any such matrix A with at most s non-zero entries per column must have s = Omega(eps^{-1}log n/log(1/eps)) as long as m < O(n/log(1/eps)). This bound improves the lower bound of Omega(min{eps^{-2}, eps^{-1}sqrt{log_m 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 Johnson-Lindenstrauss upper bound of [Kane-Nelson, SODA 2012] up to an O(log(1/eps)) factor. Next, we show that any m x n matrix with the k-restricted isometry property (RIP) with constant distortion must have at least Omega(klog(n/k)) non-zeroes per column if the number of the rows is the optimal value m = O(klog (n/k)), and if k < n/polylog n. This improves the previous lower bound of Omega(min{k, n/m}) by [Chandar, 2010] and shows that for virtually all k it is impossible to have a sparse RIP matrix with an optimal number of rows. Lastly, we show that any oblivious distribution over subspace embedding matrices with 1 non-zero per column and preserving all distances in a d dimensional-subspace up to a constant factor with constant probability must have at least Omega(d^2) rows. This matches one of the upper bounds in [Nelson-Nguyen, 2012] and shows the impossibility of obtaining the best of both of constructions in that work, namely 1 non-zero per column and ~O(d) rows.
Recommendations
Cited in
(18)- Random projections for Bayesian regression
- Lower bounds for Haar projections: deterministic examples
- Randomized LU decomposition using sparse projections
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- A unified framework for linear dimensionality reduction in L1
- Sparser Johnson-Lindenstrauss transforms
- Sparsity and non-Euclidean embeddings
- The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Bounds on Dimension Reduction in the Nuclear Norm
- Lower bounds for oblivious subspace embeddings
- Tight bounds for _p oblivious subspace embeddings
- Sparser Johnson-Lindenstrauss transforms
- A lower bound on the error in dimensionality reduction resulting from projection onto a restricted subspace
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Training multi-layer over-parametrized neural network in subquadratic time
This page was built for publication: Sparsity lower bounds for dimensionality reducing maps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495780)
