Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Randomized algorithms for the low-rank approximation of matrices.

Edo Liberty1, Franco Woolfe, Per-Gunnar Martinsson

  • 1Department of Computer Science and Program in Applied Math, Yale University, 51 Prospect Street, New Haven, CT 06511, USA.

Proceedings of the National Academy of Sciences of the United States of America
|December 7, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Streaming Quantiles Algorithms with Small Space and Update Time.

Sensors (Basel, Switzerland)·2022
Same author

On the efficient evaluation of the azimuthal Fourier components of the Green's function for Helmholtz's equation in cylindrical coordinates.

Journal of computational physics·2022
Same author

Randomized algorithms for distributed computation of principal component analysis and singular value decomposition.

Advances in computational mathematics·2021
Same author

A Fast Summation Method for Oscillatory Lattice Sums.

Journal of mathematical physics·2020
Same author

A FAST SIMPLE ALGORITHM FOR COMPUTING THE POTENTIAL OF CHARGES ON A LINE.

Applied and computational harmonic analysis·2020
Same author

A hierarchical loss and its problems when classifying non-hierarchically.

PloS one·2019
Same journal

Tau protein as a regulator of mitochondrial function and dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

A scalable, dividing cell model for the robust propagation and quantification of human sporadic Creutzfeldt-Jakob disease prions.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Epigenetic regulation of mesenchymal BMP signaling directs postnatal organ innervation.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Single-shot wide-field biochemical imaging at 1 kHz frame rate.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Morphogenesis and topological evolution of a frustrated nematic liquid crystal under confinement.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

B cell-intrinsic CXCR3 drives efficient generation of ectopic pulmonary germinal center responses to influenza A virus infection.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles

New randomized algorithms offer efficient and reliable low-rank matrix approximations and singular value decomposition for large datasets. These probabilistic methods present a negligible failure rate, outperforming traditional techniques.

Area of Science:

  • Numerical Analysis
  • Linear Algebra
  • Computational Mathematics

Background:

  • Low-rank approximation is crucial for dimensionality reduction and data compression.
  • Singular value decomposition (SVD) is a fundamental tool in linear algebra with broad applications.
  • Classical deterministic algorithms for these tasks can be computationally expensive for large matrices.

Purpose of the Study:

  • To introduce and evaluate two novel randomized algorithms for constructing low-rank matrix approximations.
  • To demonstrate the application of these algorithms to singular value decomposition (SVD) of numerically low-rank matrices.
  • To compare the efficiency and reliability of the proposed randomized methods against classical deterministic approaches.

Main Methods:

  • Implementation of two recently proposed randomized algorithms.

Related Experiment Videos

  • Application of these algorithms to compute low-rank approximations.
  • Evaluation of their performance in singular value decomposition (SVD).
  • Numerical experiments to illustrate the algorithms' behavior.

    • Main Results:

    • The randomized algorithms efficiently construct low-rank matrix approximations.
    • They are effective in evaluating singular value decompositions (SVD) for low-rank matrices.
    • The probabilistic methods exhibit a negligible failure rate (e.g., 10^-17).
    • The new procedures are often more efficient and reliable than deterministic methods.
    • The algorithms demonstrate natural parallelization capabilities.

    Conclusions:

    • Randomized algorithms provide a powerful and efficient alternative for low-rank matrix approximation and SVD.
    • These methods offer significant advantages in terms of speed and reliability for large-scale numerical problems.
    • The probabilistic nature of the algorithms ensures high accuracy with minimal failure probability.