CUR matrix decompositions for improved data analysis

By Michael W. Mahoney, Petros Drineas. 2009

931 citations recorded by the source corpus.

Subfields: Computational Mathematics, Computational Mechanics, Signal Processing

How researchers see this paper

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

In Computational Mathematics

In Computational Mechanics

In Signal Processing

Citations in the corpus

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “…Nyström method (Williams and Seeger, 2001), sparse greedy approximations (Smola and Schölkopf, 2000), incomplete Cholesky decomposition (Fine and Scheinberg, 2001), Gram-Schmidt orthonormalization (Shawe-Taylor and Cristianini, 2004) or CUR matrix decompositions (Mahoney and Drineas, 2009).”
Fast approximation of matrix coherence and statistical leverage (2011, methodology): “(7) To construct an ǫ-JLT with high probability, simply choose every entry of Π independently, equal to ± √ 3/r with probability 1/6 each and zero otherwise (with probability 2/3) [1].”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, background): “By exploiting and extending recent work on “fast” random projections and related recent work on “fast” approximation of the statistical leverage scores, we illustrate that high-quality leverage-based random sampling and high-quality random projection algorithms have comparable running times.”
Machine-learned potentials for next-generation matter simulations (2021, methodology): “…from simple approaches employing the Pearson correlation coefficient as selection criterion 79 to more advanced techniques such as CUR decomposition 80 , a modified version of farthest-point sampling, or automatic relevance determination 81 , a Bayesian method that estimates the relevance of…”
Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “table than a generic 67 low rank approximation, or even the SVD, whose column and row spaces are spanned by arbitrary linear combinations of all of the columns and rows of A, respectively, see, e.g., [86] for a discussion of this. Before discussing the details of some of the available CUR algorithms”
Randomized Matrix Decompositions using R (2016, methodology): “However, the CUR decomposition is not unique, and diﬀerent computational strategies lead to diﬀerent subsets of columns and rows, for instance, see Mahoney and Drineas (2009) and Boutsidis and Woodruﬀ (2017).”
Network Flow Algorithms for Structured Sparsity (2010, neutral): “CUR Matrix Decomposition [Mairal, Jenatton, Obozinski, and Bach, 2011] CUR matrix decomposition [Mahoney and Drineas, 2009] Let X in R.”
Training Mixture Models at Scale via Coresets (2017, background): “…et al., 2007), k-center (Har-Peled and Varadarajan, 2004), k-line median (Feldman et al., 2006a), subspace approximation (Feldman et al., 2006a; Mahoney and Drineas, 2009), (k,m)-segment mean (Feldman et al., 2012), PCA and projective clustering (Feldman et al., 2013b), distributed k-means and…”
A Randomized Algorithm for Principal Component Analysis (2008, neutral): “However, other algorithms, such as those of [1], [2], [3], [5], [7], [8], [10], [11], [12], [13], [14], [15], [16], [17], [18], [21], [22], [23], [24], [25], [27], [28], [30], [32], [33], [34], [35], and [37], also yield accuracies involving factors of at least √ m when the singular values σk+1, σk+”
A statistical perspective on algorithmic leveraging (2013, methodology): “3 Illustration of the Method on Real Data Here, we provide an illustration of our methods on two real data sets drawn from two problems in genetics with which we have prior experience [9, 28].”
Scalable Training of Mixture Models via Coresets (2011, methodology): “They have been used to great effect for a host of geometric and graph problems, including k-median [6], k-mean [8], k-center [21], k-line median [10] subspace approximation [10, 22], etc.”
Stat260/cs294: Randomized Algorithms for Matrices and Data (methodology): “; and Random Projections Today, we will use the concentration results of the last few classes to go back and make statements about approximating the product of two matrices; and we will also describe an important topic we will spend a great deal more time on, i.e., random projections and…”
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (2012, background): “See [20, 15] for details; and note that they can be generalized to `1 and other `p norms [10] as well as to arbitrary n×d matrices, with both n and d large [21, 15].”
Handbook of Big Data (2016, methodology): “The reader may left-drag the mouse in the plot to see a ﬁrst real-time response.”
Efficient Volume Sampling for Row/Column Subset Selection (2010, background): “The same rows and projection as in the previous point give a √ (k + 1)(n− k)-approximation to the matrix of rank k closest to A under the spectral norm.”