CUR matrix decompositions for improved data analysis

DOI10.1073/pnas.0803205106zbMath1202.68480OpenAlexW2141696759WikidataQ33399394 ScholiaQ33399394MaRDI QIDQ134075

Petros Drineas, Michael W. Mahoney, Michael W. Mahoney, Petros Drineas

Publication date: 20 January 2009

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1073/pnas.0803205106

zbMATH Keywords

singular value decomposition randomized algorithms interpretation principal components analysis statistical leverage

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Pass-efficient methods for compression of high-dimensional turbulent flow data, Efficient algorithms for CUR and interpolative matrix decompositions, Feature selection with SVD entropy: some modification and extension, Randomized numerical linear algebra: Foundations and algorithms, Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems, Spectral estimation from simulations via sketching, Relaxed leverage sampling for low-rank matrix completion, A fast block low-rank dense solver with applications to finite-element matrices, Randomized Local Model Order Reduction, Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Unnamed Item, A Generalized CUR Decomposition for Matrix Pairs, Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format, Far-field compression for fast kernel summation methods in high dimensions, Tensor CUR Decomposition under T-Product and Its Perturbation, On expected error of randomized Nyström kernel regression, A fast, provably accurate approximation algorithm for sparse principal component analysis reveals human genetic variation across the world, Structure-preserving reduced-order modeling of Korteweg-de Vries equation, Fast Deterministic Approximation of Symmetric Indefinite Kernel Matrices with High Dimensional Datasets, Pseudo-skeleton approximations with better accuracy estimates, A convex semi-nonnegative matrix factorisation approach to fuzzy $c$-means clustering, Asymptotic error bounds for kernel-based Nyström low-rank approximation matrices, Feature selection for linear SVM with provable guarantees, One-pass additive-error subset selection for $\ell_p$ subspace approximation and $(k, p)$-clustering, A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems, Structural conditions for projection-cost preservation via randomized matrix multiplication, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Coseparable Nonnegative Matrix Factorization, A literature survey of matrix methods for data science, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, Randomized Low-Rank Approximation for Symmetric Indefinite Matrices, A Hybrid DEIM and Leverage Scores Based Method for CUR Index Selection, Randomized Quasi-Optimal Local Approximation Spaces in Time, Optimal subsampling for softmax regression, Unnamed Item, Adaptive sparse interpolation for accelerating nonlinear stochastic reduced-order modeling with time-dependent bases, Unnamed Item, Computing Localized Representations of the Kohn--Sham Subspace Via Randomization and Refinement, Inexact proximal stochastic gradient method for convex composite optimization, Interpolative Decomposition Butterfly Factorization, Generalized pseudoskeleton decompositions, Online Interpolation Point Refinement for Reduced-Order Models using a Genetic Algorithm, Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1., Literature survey on low rank approximation of matrices, A GPU parallel randomized CUR compression method for the method of moments, Optimal CUR Matrix Decompositions, System Identification via CUR-Factored Hankel Approximation, FaIMS: a fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation, Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition, Practical acceleration for computing the HITS expertrank vectors, Lower bounds on the rank and symmetric rank of real tensors, Regularized greedy column subset selection, Analytical Low-Rank Compression via Proxy Point Selection, Interpolation-Based Model Order Reduction for Polynomial Systems, Forecasting using random subspace methods, A parametric and non-intrusive reduced order model of car crash simulation, Fast quantum algorithms for least squares regression and statistic leverage scores, A continuous analogue of the tensor-train decomposition, Reduced order modelling of nonlinear cross-diffusion systems, Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning, Fast construction of hierarchical matrix representation from matrix-vector multiplication, The nonequilibrium quantum many-body problem as a paradigm for extreme data science, Generalizing the column-row matrix decomposition to multi-way arrays, Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization, Unnamed Item, Fast randomized matrix and tensor interpolative decomposition using countsketch, Practical error bounds for a non-intrusive bi-fidelity approach to parametric/stochastic model reduction, Geometric component analysis and its applications to data analysis, dCUR, Linear-time CUR approximation of BEM matrices, Optimal Subsampling for Large Sample Logistic Regression, A DEIM Induced CUR Factorization, The Fast Cauchy Transform and Faster Robust Linear Regression, Perspectives on CUR decompositions, An extended DEIM algorithm for subset selection and class identification, ORCA: outlier detection and robust clustering for attributed graphs, 6 The Loewner framework for system identification and reduction, HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation, Hierarchical Decompositions for the Computation of High-Dimensional Multivariate Normal Probabilities, A reduced model using random forest: application on car crash optimization, Allocation Strategies for High Fidelity Models in the Multifidelity Regime, Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, Optimal Column-Based Low-Rank Matrix Reconstruction, Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements, High-dimensional model recovery from random sketched data by exploring intrinsic sparsity, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions, Unnamed Item, Perturbations of CUR Decompositions, Deep composition of tensor-trains using squared inverse Rosenblatt transports, Robust CUR Decomposition: Theory and Imaging Applications, CUR LRA at Sublinear Cost Based on Volume Maximization, Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion, Butterfly Factorization, Hybrid CUR-type decomposition of tensors in the Tucker format, A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization, An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation, $\mathrm{C_{enet}Biplot}$: a new proposal of sparse and orthogonal biplots methods by means of elastic net CSVD, Localized Model Reduction for Nonlinear Elliptic Partial Differential Equations: Localized Training, Partition of Unity, and Adaptive Enrichment, Scalable conditional deep inverse Rosenblatt transports using tensor trains and gradient-based dimension reduction, Exemplar-based large-scale low-rank matrix decomposition for collaborative prediction, Link Prediction for Egocentrically Sampled Networks, A Model-free Variable Screening Method Based on Leverage Score

Uses Software

Algorithm 844

Cites Work