Dense fast random projections and lean Walsh transforms

Random projection methods give distributions over k × d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a vector x ∈ ℝ^d the norm of the resulting vector, Ψ x ∈ ℝ^k, is up to distortion ε equal to the norm of x w.p. at least 1 - δ. The Johnson Lindenstrauss lemma shows that such distributions exist over dense matrices for k (the target dimension) in O(log(1/δ)/fε²). Ailon and Chazelle and later Matousek showed that there exist entry-wise i.i.d. distributions over sparse matrices Ψ which give the same guaranties for vectors whose ℓ_∞ is bounded away from their ℓ₂ norm. This allows to accelerate the mapping x → Ψx. We claim that setting Ψ as any column normalized deterministic dense matrix composed with random ±1 diagonal matrix also exhibits this property for vectors whose ℓ_p (for any p > 2) is bounded away from their ℓ₂ norm. We also describe a specific tensor product matrix which we term lean Walsh. It is applicable to any vector in in O(d) operations and requires a weaker ℓ_∞ bound on x then the best current result, under comparable running times, using sparse matrices due to Matousek.