A randomized algorithm for the decomposition of matrices

By Per-Gunnar Martinsson, Vladimir Rokhlin, Mark Tygert. 2011

370 citations recorded by the source corpus.

Subfields: Computational Mechanics, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5f57084ce85330766906c1f8ccdfd9544902e9ce

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

In Signal Processing

Citations in the corpus

Deriving reproducible biomarkers from multi‐site resting‐state data: An Autism‐based example (2016, methodology): “Hence, for KMeans and ICA, we reduced the length of the time series by applying PCA dimensionality reduction with efficient randomized SVD (Martinsson et al., 2011).”
Handbook of Big Data (2016, background): “Combined pan/zoom based on focus rectangles is described in Section 6.4.3.”
Approximate Separability of the Green's Function of the Helmholtz Equation in the High Frequency Limit (2018, methodology): “If a matrix is known to have a low-rank approximation a priori, fast algorithms [17, 27] are available to compute a low-rank approximation.”
Multidimensional simultaneous random plus erratic noise attenuation and interpolation for seismic data by joint low-rank and sparse inversion (2015, methodology): “Here, we make use of Algorithm 1, described and analyzed in Halko et al. (2011) and Martinsson et al. (2011).”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, background): “Third, in recent years several high-quality numerical implementations of randomized matrix algorithms for least-squares and low-rank approximation problems have been developed (Avron et al., 2010; Meng et al., 2014; Woolfe et al., 2008; Rokhlin et al., 2009; Martinsson et al., 2011).”
Randomized Matrix Decompositions using R (2016, methodology): “Originally formulated by Pearson (1901), principal component analysis (PCA)3 still plays an important role in modern statistics due to its simple geometric interpretation.”
MNE software for processing MEG and EEG data (2013, methodology): “To reduce the computation time and to improve the unmixing performance, dimensionality reduction can be achieved using the randomized PCA algorithm (Martinsson et al., 2011).”
Evaluation of a Tree-based Pipeline Optimization Tool for Automating Data Science (2016, methodology): “We implemented RandomizedPCA, a variant of Principal Component Analysis that uses randomized Singular Value Decomposition (SVD) [13].”
De-biasing the dynamic mode decomposition for applied Koopman spectral analysis of noisy datasets (2015, methodology): “) On a side note, the formulation here allows one to use efficient randomized SVD algorithms [36] to expedite de-biased DMD computations—an option that would not be directly available via a “more traditional” formulation of the total least-squares problem [52]; here, we require the singular vectors ”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, methodology): “This simplified estimate is very similar to the major results in [92].”
TAU-REX I: A NEXT GENERATION RETRIEVAL CODE FOR EXOPLANETARY ATMOSPHERES (2014, methodology): “Due to the large size of the matrices involved, we approximate equation 9 with a randomised, truncated SVD algorithm (Halko et al. 2011; Martinsson et al. 2011).”
Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds (2013, background): “Recent work [6] introduced a randomized algorithm for matrix factorization with lower computational complexity.”