Electronic Colloquium on Computational Complexity, Report No. 70 (2007) Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

Citations in the corpus

Distributed Mean Estimation with Limited Communication (2016, background): “To measure the minimax performance, without loss of generality, we restrict ourselves to the scenario where each Xi ∈ Sd, the ball of radius 1 in Rd, i.e., X ∈ Sd iff ||X||2 ≤ 1, where ||X||2 denotes the ℓ2 norm of the vector X.”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, unknown): “Note that in the range p & e N 1 / 2 not covered by the constructions in [1, 2], a logarithmic factor in N is bounded by log(log( p )), and thus plays a minor role.”
Optimal principal component analysis in distributed and streaming models (2015, unknown): “1 in [6]).”
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering (2018, background): “…satisfy a variant of Theorem 1.1 (sometimes with somewhat worse bound on d ) but do not necessarily satisfy Deﬁnition 1.2: most notably, “sparse” constructions [DKS10, KN14] as well as “fast” constructions based on sub-sampled randomized Fourier-like transforms [AC06, AL09, KW11, AL13, NPW14].”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “1 of [3] for details on obtaining this time complexity, which is a slight improvement to the O(nd logn) time mentioned above), which up to the logarithmic factor, is optimal in the matrix dimensions of A ∈ Rn×d.”
Near Optimal Dimensionality Reductions That Preserve Volumes (2008, background): “See also [15,4,13] for a related treatment and extensions.”
A sparse Johnson: Lindenstrauss transform (2010, methodology): “Then the running time of the block-Hadamard based hashing is Note that if δ is not too small then the running time of Theorem 3 is comparable to the best existing methods for dense vectors [3] yet it is much faster for sparse vectors.”
Fast locality-sensitive hashing (2011, methodology): “Note that it is possible to get a set of L independent buckets in O(Ld log k) time by repeatedly invoking a O(d log k) subroutine [2, 26] for computing k elements out of the randomized Hadamard transform.”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, background): “For instance, see Ailon and Liberty [1] and [23] for further details.”