Simple analyses of the Sparse Johnson-Lindenstrauss transform

Abstract

For every n-point subset X of Euclidean space and target distortion 1+ϵ for 0 < ϵ < 1, the Sparse Johnson Lindenstrauss Transform (SJLT) of [19] provides a linear dimensionality-reducing map f: X → ℓm2 where f(x) = Πx for Π a matrix with m rows where (1) m = O(ϵ-2 log n), and (2) each column of Π is sparse, having only O(ϵm) non-zero entries. Though the constructions given for such Π in [19] are simple, the analyses are not, employing intricate combinatorial arguments. We here give two simple alternative proofs of the main result of [19], involving no delicate combinatorics. One of these proofs has already been tested pedagogically, requiring slightly under forty minutes by the third author at a casual pace to cover all details in a blackboard course lecture.