Randomized algorithms for the low-rank approximation of matrices

By Edo Liberty, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, Mark Tygert. Proceedings of the National Academy of Sciences of the United States of America, 2007

596 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/51a20365c3440ec49747d867b49e244e051abb84

How researchers see this paper

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

In Atomic and Molecular Physics, and Optics

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Randomized Matrix Decompositions using R (2016, background): “Several probabilistic strategies have been proposed to find a ‘good’ smaller matrix, and we refer the reader to the surveys by Mahoney (2011), Liberty (2013), and Halko, Martinsson, and Tropp (2011b) for an in-depth discussion, and theoretical results.”
An Algorithm for the Principal Component Analysis of Large Data Sets (2010, unknown): “Variants of the fast Fourier transform (FFT) permit additional accelerations; see [5], [7], and [14].”
A fast reduced-rank interpolation method for prestack seismic volumes that depend on four spatial dimensions (2013, methodology): “A second category groups methods based on prediction filters (Spitz, 1991; Porsani, 1999; Gulunay, 2003; Naghizadeh and Sacchi, 2007, 2009) which use the predictability of linear events in the frequencyspace domain to interpolate aliased data at high frequencies with filters derived from nonaliased…”
Online Learning of Multiple Tasks and Their Relationships (2011, methodology): “The SVD step can be performed using efficient eigendecomposition algorithms such as the randomized SVD algorithm [Liberty et al., 2007].”
Ising formulations of many NP problems (2013, background): “Typical instances approach the asymptotic bounds on worst-case runtimes, in contrast to the case for some NP problems; many recent developments focus on randomized algorithms [62, 63, 64].”
Simple and deterministic matrix sketching (2012, background): “The second approach is to randomly combine matrix rows [25][28][27][21].”
Efficient matrix completion for seismic data reconstruction (2015, methodology): “…seismic data reconstruction with the method of projection onto convex sets, where they use a low-rank approximation of the Hankel matrix via the randomized singular value decomposition (Liberty et al., 2007; Halko et al., 2011; Mahoney, 2011) to interpolate seismic temporal frequency slices.”
A Randomized Algorithm for Principal Component Analysis (2008, methodology): “Compute the m × l product matrix where ˜ U is a real m × l matrix whose columns are orthonormal, W is a real l × l matrix whose columns are orthonormal, and ˜ Σ is a real diagonal l × l matrix whose only nonzero entries are nonnegative and appear in nonincreasing order on the diagonal.”
A Co-training Approach for Multi-view Spectral Clustering (2011, background): “This can be of great advantage in large scale problems, since there exist efficient randomized algorithms for doing SVD if the original matrix is low rank and a good upper bound on the rank is known in advance (Liberty et al., 2007).”