Abstract
Random projection methods give distributions over k ×d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a vector the norm of the resulting vector, , 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 . 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 ℓ2 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 ℓ2 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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics 26, 189–206 (1984)
Frankl, P., Maehara, H.: The Johnson-Lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory Series A 44, 355–362 (1987)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 604–613 (1998)
DasGupta, S., Gupta, A.: An elementary proof of the Johnson-Lindenstrauss lemma. Technical Report, UC Berkeley 99-006 (1999)
Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671–687 (2003)
Matousek, J.: On variants of the Johnson-Lindenstrauss lemma. Private communication (2006)
Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Sampling algorithms for ℓ2 regression and applications. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, Florida, United States (2006)
Sarlós, T.: Improved approximation algorithms for large matrices via random projections. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA (2006)
Frieze, A.M., Kannan, R., Vempala, S.: Fast monte-carlo algorithms for finding low-rank approximations. In: IEEE Symposium on Foundations of Computer Science, pp. 370–378 (1998)
Peled, S.H.: A replacement for voronoi diagrams of near linear size. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, Nevada, USA, pp. 94–103 (2001)
Achlioptas, M.: Fast computation of low rank matrix approximations. In: STOC: ACM Symposium on Theory of Computing (STOC) (2001)
Drineas, P., Kannan, R.: Fast monte-carlo algorithms for approximate matrix multiplication. In: IEEE Symposium on Foundations of Computer Science, pp. 452–459 (2001)
Liberty, E., Woolfe, F., Martinsson, P.G., Rokhlin, V., Tygert, M.: Randomized algorithms for the low-rank approximation of matrices. In: Proceedings of the National Academy of Sciences (2007)
Dasgupta, A., Drineas, P., Harb, B., Kumar, R., Mahoney, M.W.: Sampling algorithms and coresets for ℓ p regression. In: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008)
Drineas, P., Mahoney, M.W., Muthukrishnan, S., Sarlos, T.: Faster least squares approximation. TR arXiv:0710.1435 (submitted for publication) (2007)
Drineas, P., Mahoney, M., Muthukrishnan, S.: Relative-error cur matrix decompositions. TR arXiv:0708.3696 (submitted for publication) (2007)
Candes, E.J., Tao, T.: Near-optimal signal recovery from random projections: Universal encoding strategies? Information Theory. IEEE Transactions 52(12), 5406–5425 (2006)
Donoho, D.L.: Compressed sensing. IEEE Transactions on Information Theory 52(4), 1289–1306 (2006)
Elad, M.: Optimized projections for compressed sensing. IEEE Transactions on Signal Processing 55(12), 5695–5702 (2007)
Paschou, P., Ziv, E., Burchard, E., Choudhry, S., Rodriguez-Cintron, W., Mahoney, M.W., Drineas, P.: Pca-correlated snps for structure identification in worldwide human populations. PLOS Genetics 3, 1672–1686 (2007)
Paschou, P., Mahoney, M.W., Javed, A., Pakstis, A., Gu, S., Kidd, K.K., Drineas, P.: Intra- and inter-population genotype reconstruction from tagging snps. Genome Research 17(1), 96–107 (2007)
Ailon, N., Chazelle, B.: Approximate nearest neighbors and the fast johnson-lindenstrauss transform. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 557–563. ACM Press, New York (2006)
Ailon, N., Liberty, E.: Fast dimension reduction using rademacher series on dual bch codes. In: SODA, pp. 1–9 (2008)
Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liberty, E., Ailon, N., Singer, A. (2008). Dense Fast Random Projections and Lean Walsh Transforms. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)