Nothing Special   »   [go: up one dir, main page]

Skip to main content

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics 26, 189–206 (1984)

    MATH  MathSciNet  Google Scholar 

  2. Frankl, P., Maehara, H.: The Johnson-Lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory Series A 44, 355–362 (1987)

    MathSciNet  Google Scholar 

  3. 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)

    Google Scholar 

  4. DasGupta, S., Gupta, A.: An elementary proof of the Johnson-Lindenstrauss lemma. Technical Report, UC Berkeley 99-006 (1999)

    Google Scholar 

  5. Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671–687 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Matousek, J.: On variants of the Johnson-Lindenstrauss lemma. Private communication (2006)

    Google Scholar 

  7. 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)

    Google Scholar 

  8. 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)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. Achlioptas, M.: Fast computation of low rank matrix approximations. In: STOC: ACM Symposium on Theory of Computing (STOC) (2001)

    Google Scholar 

  12. Drineas, P., Kannan, R.: Fast monte-carlo algorithms for approximate matrix multiplication. In: IEEE Symposium on Foundations of Computer Science, pp. 452–459 (2001)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. 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)

    Google Scholar 

  15. Drineas, P., Mahoney, M.W., Muthukrishnan, S., Sarlos, T.: Faster least squares approximation. TR arXiv:0710.1435 (submitted for publication) (2007)

    Google Scholar 

  16. Drineas, P., Mahoney, M., Muthukrishnan, S.: Relative-error cur matrix decompositions. TR arXiv:0708.3696 (submitted for publication) (2007)

    Google Scholar 

  17. Candes, E.J., Tao, T.: Near-optimal signal recovery from random projections: Universal encoding strategies? Information Theory. IEEE Transactions 52(12), 5406–5425 (2006)

    MathSciNet  Google Scholar 

  18. Donoho, D.L.: Compressed sensing. IEEE Transactions on Information Theory 52(4), 1289–1306 (2006)

    Article  MathSciNet  Google Scholar 

  19. Elad, M.: Optimized projections for compressed sensing. IEEE Transactions on Signal Processing 55(12), 5695–5702 (2007)

    Article  Google Scholar 

  20. 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)

    Article  Google Scholar 

  21. 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)

    Article  Google Scholar 

  22. 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)

    Chapter  Google Scholar 

  23. Ailon, N., Liberty, E.: Fast dimension reduction using rademacher series on dual bch codes. In: SODA, pp. 1–9 (2008)

    Google Scholar 

  24. Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes. Springer, Heidelberg (1991)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Ashish Goel Klaus Jansen José D. P. Rolim Ronitt Rubinfeld

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics