Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
From MaRDI portal
DOI10.1137/090771806zbMath1269.65043arXiv0909.4061OpenAlexW2117756735WikidataQ46236603 ScholiaQ46236603MaRDI QIDQ93618
Per-Gunnar Martinsson, Nathan Halko, Joel A. Tropp, Per-Gunnar Martinsson, Joel A. Tropp, Nathan Halko
Publication date: 22 September 2009
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0909.4061
numerical examplessingular value decompositionprincipal component analysisdimension reductionrandomized algorithmdata analysisparallel algorithmrandom matrixKrylov subspace methodsscientific computingeigenvalue decompositionmatrix approximationinterpolative decompositionstreaming algorithmrank-revealing QR factorizationJohnson-lindenstrauss lemmapass-efficient algorithmsparse input matrix
Symbolic computation and algebraic computation (68W30) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Random matrices (probabilistic aspects) (60B20) Parallel numerical computation (65Y05) Random matrices (algebraic aspects) (15B52) Randomized algorithms (68W20)
Related Items (only showing first 100 items - show all)
Fast Algorithms for Hyperspectral Diffuse Optical Tomography ⋮ Scalable Low-Rank Representation ⋮ Probabilistic Bounds for the Matrix Condition Number with Extended Lanczos Bidiagonalization ⋮ A fast block low-rank dense solver with applications to finite-element matrices ⋮ Numerical methods for high-dimensional probability density function equations ⋮ Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction ⋮ Randomized Local Model Order Reduction ⋮ Optimal Low-rank Approximations of Bayesian Linear Inverse Problems ⋮ Randomized algorithms for the approximations of Tucker and the tensor train decompositions ⋮ Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case ⋮ An approximate linear solver in least square support vector machine using randomized singular value decomposition ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations ⋮ Computing Fundamental Matrix Decompositions Accurately via the Matrix Sign Function in Two Iterations: The Power of Zolotarev's Functions ⋮ Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems ⋮ Quantum machine learning: a classical perspective ⋮ Compressed Absorbing Boundary Conditions via Matrix Probing ⋮ Far-field compression for fast kernel summation methods in high dimensions ⋮ Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization ⋮ An approximate empirical Bayesian method for large-scale linear-Gaussian inverse problems ⋮ An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem ⋮ Structure-preserving reduced-order modeling of Korteweg-de Vries equation ⋮ Golub-Kahan vs. Monte Carlo: a comparison of bidiagonlization and a randomized SVD method for the solution of linear discrete ill-posed problems ⋮ Randomized matrix-free trace and log-determinant estimators ⋮ Randomized generalized singular value decomposition ⋮ MERACLE: constructive layer-wise conversion of a tensor train into a MERA ⋮ Coupled and uncoupled dynamic mode decomposition in multi-compartmental systems with applications to epidemiological and additive manufacturing problems ⋮ A Probabilistic Subspace Bound with Application to Active Subspaces ⋮ Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD ⋮ Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation ⋮ On preconditioners for the Laplace double-layer in 2D ⋮ Exploring the common principal subspace of deep features in neural networks ⋮ H2Opus: a distributed-memory multi-GPU software package for non-local operators ⋮ Nyström-based approximate kernel subspace learning ⋮ Efficient algorithm for proper orthogonal decomposition of block-structured adaptively refined numerical simulations ⋮ Error-controlled model approximation for Gaussian process morphable models ⋮ A fast SVD-hidden-nodes based extreme learning machine for large-scale data analytics ⋮ A kernel-independent sum-of-exponentials method ⋮ On convergence rates of adaptive ensemble Kalman inversion for linear ill-posed problems ⋮ Structural conditions for projection-cost preservation via randomized matrix multiplication ⋮ A singular value \(p\)-shrinkage thresholding algorithm for low rank matrix recovery ⋮ A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices ⋮ Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox ⋮ Bayesian operator inference for data-driven reduced-order modeling ⋮ Randomized algorithms in numerical linear algebra ⋮ New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem ⋮ Efficient estimation of eigenvalue counts in an interval ⋮ A nonconvex approach to low-rank matrix completion using convex optimization ⋮ Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Low-rank nonnegative tensor approximation via alternating projections and sketching ⋮ Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games ⋮ DeepCyto: a hybrid framework for cervical cancer classification by using deep feature fusion of cytology images ⋮ Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations ⋮ Literature survey on low rank approximation of matrices ⋮ A fast direct solver for non-intrusive reduced order modeling of vibroacoustic problems ⋮ A GPU parallel randomized CUR compression method for the method of moments ⋮ A Robust Multilevel Approximate Inverse Preconditioner for Symmetric Positive Definite Matrices ⋮ Optimal CUR Matrix Decompositions ⋮ A randomized singular value decomposition for third-order oriented tensors ⋮ Matrices with Hierarchical Low-Rank Structures ⋮ Learning elliptic partial differential equations with randomized linear algebra ⋮ Paved with good intentions: analysis of a randomized block Kaczmarz method ⋮ Parallelization of the inverse fast multipole method with an application to boundary element method ⋮ TeNeS: tensor network solver for quantum lattice systems ⋮ Fast structured LU factorization for nonsymmetric matrices ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Optimal experimental design under irreducible uncertainty for linear inverse problems governed by PDEs ⋮ Geometric Methods on Low-Rank Matrix and Tensor Manifolds ⋮ Randomization and Reweighted $\ell_1$-Minimization for A-Optimal Design of Linear Inverse Problems ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Unnamed Item ⋮ Estimating the norms of random circulant and Toeplitz matrices and their inverses ⋮ An \(O(N)\) direct solver for integral equations on the plane ⋮ Random Projections for Low Multilinear Rank Tensors ⋮ Randomized Oversampling for Generalized Multiscale Finite Element Methods ⋮ Stochastic boundary methods of fundamental solutions for solving PDEs ⋮ A DEIM Induced CUR Factorization ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations ⋮ Tikhonov Regularization and Randomized GSVD ⋮ 6 The Loewner framework for system identification and reduction ⋮ Randomized Alternating Least Squares for Canonical Tensor Decompositions: Application to A PDE With Random Data ⋮ HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation ⋮ Hierarchical Decompositions for the Computation of High-Dimensional Multivariate Normal Probabilities ⋮ A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models ⋮ Multidimensional Scaling With Very Large Datasets ⋮ Compressed and Penalized Linear Regression ⋮ On the Stability of Some Hierarchical Rank Structured Matrix Algorithms ⋮ An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling ⋮ A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices ⋮ Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems ⋮ ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations ⋮ Fast and accurate propagation of coherent light ⋮ IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM ⋮ Clustered Matrix Approximation ⋮ A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks ⋮ Active Subspace: Toward Scalable Low-Rank Learning ⋮ Cost-efficient cutoff method for tensor renormalization group with randomized singular value decomposition ⋮ A Randomized Maximum A Posteriori Method for Posterior Sampling of High Dimensional Nonlinear Bayesian Inverse Problems ⋮ A literature survey of low-rank tensor approximation techniques ⋮ Efficiency of randomised dynamic mode decomposition for reduced order modelling
This page was built for publication: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
