In this paper, we study a fast approximation method for large-scale high-dimensional sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to the data matrix and the target vector and then to solve a sparse least-squares problem on the compressed data with a slightly larger regularization parameter . Theoretically, we establish the optimization error bound of the learned model for two different sparsity-inducing regularizers, i.e., the elastic net and the @math norm. Compared with previous relevant work, our analysis is non-asymptotic and exhibits more insights on the bound, the sample complexity and the regularization. As an illustration, we also provide an error bound of the Dantzig selector under JL transforms.
@cite_22: Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a sparse version of the fundamental tool in dimension reduction -- the Johnson-Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just O(1 e) non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of Ω(1 e2) both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. Using this, we achieve an O(1 e) update time per non-zero element for a (1 e)-approximate projection, thereby substantially outperforming the O(1 e2) update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its O(d) worst case running time matches the best approach of Ailon and Liberty.
@cite_29: 
@cite_3: A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n e2)-dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± e). In this note, we prove this theorem using elementary probabilistic techniques.
@cite_16: A classic result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded into k-dimensional Euclidean space---where k is logarithmic in n and independent of d--so that all pairwise distances are maintained within an arbitrarily small factor. All known constructions of such embeddings involve projecting the n points onto a spherically random k-dimensional hyperplane through the origin. We give two constructions of such embeddings with the property that all elements of the projection matrix belong in -1, 0, +1 . Such constructions are particularly well suited for database environments, as the computation of the embedding reduces to evaluating a single aggregate over k random partitions of the attributes.
@cite_13: We introduce a new low-distortion embedding of l2d into lpO(log n) (p=1,2), called the Fast-Johnson-Linden-strauss-Transform. The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the "Heisenberg principle" of the Fourier transform, ie, its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in l1 and l2. We consider the case of approximate nearest neighbors in l2d. We provide a faster algorithm using classical projections, which we then further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.
@cite_17: We give two different and simple constructions for dimensionality reduction in e2 via linear mappings that are sparse: only an O(e)-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1 + e with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas [2003] and [2010]. Such distributions can be used to speed up applications where e2 dimensionality reduction is used.
* -0.1in The JL transforms refer to a class of transforms that obey the JL lemma @cite_29 , which states that any @math points in Euclidean space can be embedded into @math dimensions so that all pairwise Euclidean distances are preserved upto @math . Since the original Johnson-Lindenstrauss result, many transforms have been designed to satisfy the JL lemma, including Gaussian random matrices @cite_3 , sub-Gaussian random matrices @cite_16 , randomized Hadamard transform @cite_13 , sparse JL transforms by random hashing @cite_22 @cite_17 . The analysis presented in this work builds upon the JL lemma and therefore our method can enjoy the computational benefits of sparse JL transforms including less memory and fast computation.