Publication:93618

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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)

Numerically safe Gaussian elimination with no pivoting ⋮ Multi-dimensional functional principal component analysis ⋮ Pass-efficient methods for compression of high-dimensional turbulent flow data ⋮ Wavelet adaptive proper orthogonal decomposition for large-scale flow data ⋮ Efficient algorithms for CUR and interpolative matrix decompositions ⋮ Optimal design of acoustic metamaterial cloaks under uncertainty ⋮ Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems ⋮ On condition numbers of the total least squares problem with linear equality constraint ⋮ Spectral estimation from simulations via sketching ⋮ Approximate inversion of discrete Fourier integral operators ⋮ Physics-informed machine learning for reduced-order modeling of nonlinear problems ⋮ Sparse data-driven quadrature rules via \(\ell^p\)-quasi-norm minimization ⋮ Reduced multidimensional scaling ⋮ A fast regression via SVD and marginalization ⋮ Multilinear POD-DEIM model reduction for 2D and 3D semilinear systems of differential equations ⋮ Functional principal subspace sampling for large scale functional data analysis ⋮ Variational inference at glacier scale ⋮ Effective matrix-free preconditioning for the augmented immersed interface method ⋮ Dimension-independent likelihood-informed MCMC ⋮ On the best approximation algorithm by low-rank matrices in Chebyshev's norm ⋮ Error analysis of a model order reduction framework for financial risk analysis ⋮ Model order reduction method based on (r)POD-ANNs for parameterized time-dependent partial differential equations ⋮ Randomized quaternion QLP decomposition for low-rank approximation ⋮ An efficient algorithm for computing the approximate t-URV and its applications ⋮ Sparse latent factor regression models for genome-wide and epigenome-wide association studies ⋮ Randomized approximate class-specific kernel spectral regression analysis for large-scale face verification ⋮ Multiscale regression on unknown manifolds ⋮ A dynamic mode decomposition technique for the analysis of non-uniformly sampled flow data ⋮ Randomized QLP decomposition ⋮ On variable and random shape Gaussian interpolations ⋮ A sketched finite element method for elliptic models ⋮ Multiscale-spectral GFEM and optimal oversampling ⋮ The stability of the first Neumann Laplacian eigenfunction under domain deformations and applications ⋮ An optimization problem based on a Bayesian approach for the 2D Helmholtz equation ⋮ Revisiting the low-rank eigenvalue problem ⋮ Reduction of multivariate mixtures and its applications ⋮ Taylor approximation and variance reduction for PDE-constrained optimal control under uncertainty ⋮ Fast and accurate pseudoinverse with sparse matrix reordering and incremental approach ⋮ A unified framework for oscillatory integral transforms: when to use NUFFT or butterfly factorization? ⋮ Adaptive dimension reduction to accelerate infinite-dimensional geometric Markov chain Monte Carlo ⋮ An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries ⋮ Random batch methods (RBM) for interacting particle systems ⋮ Fast multiscale contrast independent preconditioners for linear elastic topology optimization problems ⋮ Randomized algorithms for the low multilinear rank approximations of tensors ⋮ An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. I: Fundamentals ⋮ Effective implementation to reduce execution time of a low-rank matrix approximation problem ⋮ Reduced rank regression with matrix projections for high-dimensional multivariate linear regression model ⋮ On the convergence of Krylov methods with low-rank truncations ⋮ Hierarchical matrix approximations for space-fractional diffusion equations ⋮ Domain-decomposition least-squares Petrov-Galerkin (DD-LSPG) nonlinear model reduction ⋮ Reduced order modelling of nonlinear cross-diffusion systems ⋮ Matrix recipes for hard thresholding methods ⋮ Recursions on the marginals and exact computation of the normalizing constant for Gibbs processes ⋮ A randomized method for solving discrete ill-posed problems ⋮ On spectral and numerical properties of random butterfly matrices ⋮ Distributed estimation of principal eigenspaces ⋮ A randomized balanced proper orthogonal decomposition technique ⋮ A cross-product approach for low-rank approximations of large matrices ⋮ A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization ⋮ A fast neural network learning algorithm with approximate singular value decomposition ⋮ Perspectives on CUR decompositions ⋮ Provable accelerated gradient method for nonconvex low rank optimization ⋮ Randomized linear algebra for model reduction. I. Galerkin methods and error estimation ⋮ Single-pass randomized algorithms for LU decomposition ⋮ Low rank tensor methods in Galerkin-based isogeometric analysis ⋮ Randomized core reduction for discrete ill-posed problem ⋮ Stochastic sampling for deterministic structural topology optimization with many load cases: density-based and ground structure approaches ⋮ Hessian-based adaptive sparse quadrature for infinite-dimensional Bayesian inverse problems ⋮ Matrix completion for cost reduction in finite element simulations under hybrid uncertainties ⋮ ALORA: affine low-rank approximations ⋮ Tikhonov regularization with MTRSVD method for solving large-scale discrete ill-posed problems ⋮ Faster tensor train decomposition for sparse data ⋮ An adaptation for iterative structured matrix completion ⋮ Detecting localized eigenstates of linear operators ⋮ A harmonic FEAST algorithm for non-Hermitian generalized eigenvalue problems ⋮ Enabling numerically exact local solver for waveform inversion -- a low-rank approach ⋮ Intrusive and data-driven reduced order modelling of the rotating thermal shallow water equation ⋮ Space-fractional diffusion with variable order and diffusivity: discretization and direct solution strategies ⋮ Generalized self-concordant functions: a recipe for Newton-type methods ⋮ A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill's global convergence ⋮ Triad second renormalization group ⋮ Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions ⋮ Small-deviation inequalities for sums of random matrices ⋮ An enhanced algorithm for online proper orthogonal decomposition and its parallelization for unsteady simulations ⋮ Local Lagrangian reduced-order modeling for the Rayleigh-Taylor instability by solution manifold decomposition ⋮ Sensitivity of low-rank matrix recovery ⋮ A class of Laplacian multiwavelets bases for high-dimensional data ⋮ Deep-HyROMnet: a deep learning-based operator approximation for hyper-reduction of nonlinear parametrized PDEs ⋮ Randomized algorithms for low-rank matrix factorizations: sharp performance bounds ⋮ Nonlinear matrix recovery using optimization on the Grassmann manifold ⋮ Approximate kernel PCA: computational versus statistical trade-off ⋮ Forward and inverse modeling of fault transmissibility in subsurface flows ⋮ Single-pass randomized QLP decomposition for low-rank approximation ⋮ On the de-randomization of space-bounded approximate counting problems ⋮ Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching ⋮ Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation ⋮ A high-order accurate accelerated direct solver for acoustic scattering from surfaces ⋮ Robust computation of linear models by convex relaxation ⋮ A probabilistic algorithm for aggregating vastly undersampled large Markov chains ⋮ Real polynomial root-finding by means of matrix and polynomial iterations

This page was built for publication: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions