CoChat

Randomized algorithms for the low-rank approximation of matrices

Open access
Liberty, Edo, Woolfe, Franco, Martinsson, Per-Gunnar, Rokhlin, Vladimir, Tygert, Mark · 2007 · Proceedings of the National Academy of Sciences

The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.

Abstract

We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application ( inter alia ) to the evaluation of the singular value decompositions of numerically low-rank matrices. Being probabilistic, the schemes described here have a finite probability of failure; in most cases, this probability is rather negligible (10 −17 is a typical value). In many situations, the new procedures are considerably more efficient and reliable than the classical (deterministic) ones; they also parallelize naturally. We present several numerical examples to illustrate the performance of the schemes.

Overview

Integrity signals

Registry

Crossref · 10.1073/pnas.0709640104

Cites

14 of 14 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

The text we found for this paper looks like another document, so its claims and self-check weren’t run. The registry and citation checks still apply.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The text we found for this paper looks like another document, so the self-check wasn’t run.

Citations

Cites

Show all 14 references

Research works printed but not linked: 1

  1. N Ailon B Chazelle (ACM Press New York) pp. 557–563 (2006).

Cited by

Items 401–500 of 541

Metadata

Authors
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M.
Affiliations
  • Yale University (US)
  • University of Colorado Boulder (US)
  • Department of Computer Science and
Venue
Proceedings of the National Academy of Sciences
Published
2007-12-18
Volume
104
Issue
51
Pages
20167-20172
ISSN
  • 0027-8424 (ISSN-L)
  • 1091-6490
OpenAlex
W1968691112
Cited by
559
References
14
Citations by year
2026: 25 · 2025: 22 · 2024: 21 · 2023: 29 · 2022: 26 · 2021: 35 · 2020: 44 · 2019: 56 · 2018: 37 · 2017: 41 · 2016: 44 · 2015: 41 · 2014: 33 · 2013: 27 · 2012: 27
FWCI
8.96
Type
journal article
Language
en
Open access
Locations
  • Proceedings of the National Academy of Sciences (publishedVersion)
  • PubMed Central (publishedVersion)
  • PubMed (publishedVersion)
  • ePubWU Institutional Repository (Wirtschaftsuniversität Wien) (submittedVersion)
  • WU Research (submittedVersion, other-oa)
Funders
  • Japan Society for the Promotion of Science (26820298, 25000003, 16H00923)
  • National Institute of Environmental Health Sciences (27302C0031)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
  • Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
  • Physical Sciences › Mathematics › Applied Mathematics › Statistical and numerical algorithms
Keywords
low-rank approximation, randomized algorithms, singular value decomposition, parallel algorithms, matrix approximation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.