This paper deals with the randomized construction of efficiently computable Johnson-Lindenstrauss transforms. The paper greatly improves previous results in the literature by establishing an almost optimal result in terms of the dimension reduced and the complexity when applying such transforms.
Given a finite subset Y⊂ Rn of size N, a Johnson-Lindenstrauss transform is a map Φ: Rn → Rk, with the dimension k being much smaller than n, that approximately preserves the relative distances between any two elements in Y in the sense that (1-δ)|| y1-y2||22 ≤ || Φ(y1)-Φ(y2)||22 ≤ (1+δ)||y1-y2||22, with a fixed distortion parameter δ. Several random constructions of linear Johnson-Lindenstrauss transforms have been established that are optimal in the parameter k, that is, .
The authors of this paper, as well as Bernard Chazelle, study the fast Johnson-Lindenstrauss transform. They are interested in constructing a distribution of k × n matrices Φ, such that, in addition to approximately preserving distances for any pair of vectors in Y, the vector Φ x can be computed in O(n log n) steps for each vector x.
The main result of this paper is to prove that such a class of matrices can be obtained when the cardinality of Y is N=eÕ(n). This greatly improves previous results where the cardinality of Y was (due to Ailon and Chazelle [1]) and (due to Ailon and Liberty [2]). The reduced dimension k is bounded by
.The key ingredient in proving this result is to refine Rudelson and Veshynin’s powerful technique for constructing a compressed sensing matrix from an n × n orthogonal matrix (with entries of magnitude ) by randomly selecting k rows. The refinement enables the authors to treat both sparse vectors and vectors with small norms.
Each of the Johnson-Lindenstrauss transforms constructed in this paper is of the following form: it is the product of a matrix whose k rows are drawn uniformly at random from the n × n Hadamard matrix, and an n × n diagonal matrix with each diagonal element drawn uniformly from the set {-1, 1}.
