Publication:93618

DOI10.48550/arXiv.0909.4061zbMath1269.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)

On principal components regression, random projections, and column subsampling ⋮ A multi-resolution approximation via linear projection for large spatial datasets ⋮ Regularization properties of Krylov iterative solvers CGME and LSMR for linear discrete ill-posed problems with an application to truncated randomized SVDs ⋮ Stable estimation of a covariance matrix guided by nuclear norm penalties ⋮ Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel ⋮ Sum of Kronecker products representation and its Cholesky factorization for spatial covariance matrices from large grids ⋮ Efficient alternating least squares algorithms for low multilinear rank approximation of tensors ⋮ A new method of moments for latent variable models ⋮ Randomized algorithms for distributed computation of principal component analysis and singular value decomposition ⋮ A unified framework for linear dimensionality reduction in L1 ⋮ Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations ⋮ New studies of randomized augmentation and additive preprocessing ⋮ Accelerating large partial EVD/SVD calculations by filtered block Davidson methods ⋮ Principal components: a descent algorithm ⋮ Computationally efficient estimators for sequential and resolution-limited inverse problems ⋮ Subspace learning for unsupervised feature selection via matrix factorization ⋮ A simple spectral algorithm for recovering planted partitions ⋮ Local convergence of an algorithm for subspace identification from partial data ⋮ Fast dimension-reduced climate model calibration and the effect of data aggregation ⋮ Model order reduction with oblique projections for large scale wave propagation ⋮ A low-rank control variate for multilevel Monte Carlo simulation of high-dimensional uncertain systems ⋮ Application of the inverse fast multipole method as a preconditioner in a 3D Helmholtz boundary element method ⋮ Accuracy of singular vectors obtained by projection-based SVD methods ⋮ Randomized LU decomposition ⋮ Matrix probing: a randomized preconditioner for the wave-equation Hessian ⋮ A dynamical polynomial chaos approach for long-time evolution of SPDEs ⋮ Compression approaches for the regularized solutions of linear systems from large-scale inverse problems ⋮ A new fast direct solver for the boundary element method ⋮ The mechanism of additive composition ⋮ A fast direct solver for boundary value problems on locally perturbed geometries ⋮ Video denoising via empirical Bayesian estimation of space-time patches ⋮ Approximation of integral operators using product-convolution expansions ⋮ Demystifying the asymptotic behavior of global denoising ⋮ Compressed labeling on distilled labelsets for multi-label learning ⋮ FaIMS: a fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation ⋮ On computing distributions of products of non-negative independent random variables ⋮ On the exponential of semi-infinite quasi-Toeplitz matrices ⋮ Wild binary segmentation for multiple change-point detection ⋮ Randomized recompression of \(\mathcal {H}\)-matrices for BEM ⋮ Multidimensional butterfly factorization ⋮ Block conjugate gradient algorithms for least squares problems ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ A boundary integral equation approach to computing eigenvalues of the Stokes operator ⋮ Low-rank updates of balanced incomplete factorization preconditioners ⋮ Layer potential approach for fast eigenvalue characterization of the Helmholtz equation with mixed boundary conditions ⋮ Matrix completion under interval uncertainty ⋮ Gradient free active subspace construction using Morris screening elementary effects ⋮ A novel modified TRSVD method for large-scale linear discrete ill-posed problems ⋮ A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction ⋮ Clustering in block Markov chains ⋮ An efficient and highly accurate solver for multi-body acoustic scattering problems involving rotationally symmetric scatterers ⋮ Randomized estimation of spectral densities of large matrices made accurate ⋮ Energy preserving model order reduction of the nonlinear Schrödinger equation ⋮ Randomized model order reduction ⋮ Generalized multiscale finite element methods for space-time heterogeneous parabolic equations ⋮ Randomized SVD methods in hyperspectral imaging ⋮ Numerical evaluation of methods approximating the distribution of a large quadratic form in normal variables ⋮ User-friendly tail bounds for sums of random matrices ⋮ Reduced basis decomposition: a certified and fast lossy data compression algorithm ⋮ An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths ⋮ Fast construction of hierarchical matrix representation from matrix-vector multiplication ⋮ A Fast Algorithm for Maximum Likelihood Estimation of Mixture Proportions Using Sequential Quadratic Programming ⋮ Structure preserving reduced order modeling for gradient systems ⋮ Adaptive nonnegative matrix factorization and measure comparisons for recommender systems ⋮ Randomized LU decomposition using sparse projections ⋮ SPECK ⋮ Fast randomized matrix and tensor interpolative decomposition using countsketch ⋮ Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification ⋮ Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation ⋮ Diffusion representations ⋮ Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory ⋮ An accelerated IRNN-iteratively reweighted nuclear norm algorithm for nonconvex nonsmooth low-rank minimization problems ⋮ A locally optimal rank revealing product decomposition ⋮ An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures ⋮ Practical error bounds for a non-intrusive bi-fidelity approach to parametric/stochastic model reduction ⋮ Sparse Principal Component Analysis via Variable Projection ⋮ Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the antarctic ice sheet ⋮ Randomized interpolative decomposition of separated representations ⋮ A heterogeneous stochastic FEM framework for elliptic PDEs ⋮ Geometric component analysis and its applications to data analysis ⋮ Correlations between random projections and the bivariate normal ⋮ New applications of matrix methods ⋮ On the accuracy of cross and column low-rank maxvol approximations in average ⋮ Low-rank approximation algorithms for matrix completion with random sampling ⋮ ROML: a robust feature correspondence approach for matching objects in a set of images ⋮ Random projections for Bayesian regression ⋮ A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators ⋮ Randomized block Krylov subspace methods for trace and log-determinant estimators ⋮ An efficient randomized algorithm for computing the approximate Tucker decomposition ⋮ A model reduction approach for inverse problems with operator valued data ⋮ Fast subspace approximation via greedy least-squares ⋮ Fast Cadzow's algorithm and a gradient variant ⋮ Bayesian random projection-based signal detection for Gaussian scale space random fields ⋮ POD-DL-ROM: enhancing deep learning-based reduced order models for nonlinear parametrized PDEs by proper orthogonal decomposition ⋮ Derivative-informed projected neural networks for high-dimensional parametric maps governed by PDEs ⋮ Extreme event probability estimation using PDE-constrained optimization and large deviation theory, with application to tsunamis ⋮ Randomized block Krylov methods for approximating extreme eigenvalues ⋮ Multidimensional phase recovery and interpolative decomposition butterfly factorization ⋮ Recurrent neural network closure of parametric POD-Galerkin reduced-order models based on the Mori-Zwanzig formalism ⋮ High-dimensional model recovery from random sketched data by exploring intrinsic sparsity

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