Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

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

Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures, Low-Rank Covariance Function Estimation for Multidimensional Functional Data, Efficient Identification of Butterfly Sparse Matrix Factorizations, An Offline-Online Decomposition Method for Efficient Linear Bayesian Goal-Oriented Optimal Experimental Design: Application to Optimal Sensor Placement, Randomized Algorithms for Rounding in the Tensor-Train Format, Randomized numerical linear algebra: Foundations and algorithms, Learning physics-based models from data: perspectives from inverse problems and model reduction, Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data, Regularization via Mass Transportation, Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA, State-Based Adjoint Method for Reduced Order Modeling, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners, Randomized QR with Column Pivoting, Cubature, Approximation, and Isotropy in the Hypercube, Sketching for a low-rank nonnegative matrix approximation: numerical study, Scalable subspace methods for derivative-free nonlinear least-squares optimization, Dynamically Orthogonal Runge–Kutta Schemes with Perturbative Retractions for the Dynamical Low-Rank Approximation, PLSS: A Projected Linear Systems Solver, A fast direct boundary element method for 3D acoustic problems based on hierarchical matrices, A compact heart iteration for low-rank approximations of large matrices, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, Recompression of Hadamard Products of Tensors in Tucker Format, The engine behind (wall) turbulence: perspectives on scale interactions, Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems, Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method, Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces, Sketching for Principal Component Regression, Fast Estimation of Approximate Matrix Ranks Using Spectral Densities, Continuous-time Random Walks for the Numerical Solution of Stochastic Differential Equations, The Golden-Thompson inequality: Historical aspects and random matrix applications, Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations, Preconditioning Orbital Minimization Method for Planewave Discretization, Exploring the Locally Low Dimensional Structure in Solving Random Elliptic PDEs, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Interpolative Butterfly Factorization, The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems, Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT), An inverse‐free ADI algorithm for computing Lagrangian invariant subspaces, Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion, Computing with Functions in Spherical and Polar Geometries I. The Sphere, Compressing Rank-Structured Matrices via Randomized Sampling, Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions, Parameter Selection and Verification Techniques Based on Global Sensitivity Analysis Illustrated for an HIV Model, Block classical Gram–Schmidt-based block updating in low-rank matrix approximation, Block Basis Factorization for Scalable Kernel Evaluation, A spectral series approach to high-dimensional nonparametric regression, Randomized Dynamic Mode Decomposition, Fast Coulomb Matrix Construction via Compressing the Interactions Between Continuous Charge Distributions, PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations, Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition, Gradient-Free Construction of Active Subspaces for Dimension Reduction in Complex Models with Applications to Neutronics, Matrix Completion With Covariate Information, Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably, The Steerable Graph Laplacian and its Application to Filtering Image Datasets, Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation, Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations, Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, CoordinateWise Descent Methods for Leading Eigenvalue Problem, Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion, Parallel Transport Unfolding: A Connection-Based Manifold Learning Approach, A scalable estimator of sets of integral operators, Efficient Marginalization-Based MCMC Methods for Hierarchical Bayesian Inverse Problems, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Multiway Monte Carlo Method for Linear Systems, Coupled Canonical Polyadic Decompositions and (Coupled) Decompositions in Multilinear Rank- $(L_{r,n},L_{r,n},1)$ Terms---Part II: Algorithms, An Efficient Gauss--Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations, Computationally Efficient Decompositions of Oblique Projection Matrices, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions, Subspace Iteration Randomization and Singular Value Problems, Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUs, Inverse Heat Source Problem and Experimental Design for Determining Iron Loss Distribution, Butterfly Factorization Via Randomized Matrix-Vector Multiplications, Perturbations of CUR Decompositions, A Block Bidiagonalization Method for Fixed-Accuracy Low-Rank Matrix Approximation, Data-Driven Algorithms for Signal Processing with Trigonometric Rational Functions, PDE-Aware Deep Learning for Inverse Problems in Cardiac Electrophysiology, Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion, Gaussian Process Subspace Prediction for Model Reduction, Randomized Gram--Schmidt Process with Application to GMRES, Optimal Local Approximation Spaces for Parabolic Problems, Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition, An accelerated randomized Kaczmarz method via low-rank approximation, Butterfly Factorization, A Tale of Two Bases: Local-Nonlocal Regularization on Image Patches with Convolution Framelets, Fast state tomography with optimal error bounds, Accurate Low-Rank Approximations Via a Few Iterations of Alternating Least Squares, Fast approximate computations with Cauchy matrices and polynomials, Efficient global resolvent analysis via the one-way Navier–Stokes equations, Spectral decomposition of atomic structures in heterogeneous cryo-EM, Computing with Functions in Spherical and Polar Geometries II. The Disk, Generative modeling via tensor train sketching, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Model Reduction for Nonlinear Systems by Balanced Truncation of State and Gradient Covariance, Full-rank and low-rank splitting methods for the Swift-Hohenberg equation, Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations, Statistical Inference, Learning and Models in Big Data, Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches, Gradient-Preserving Hyper-Reduction of Nonlinear Dynamical Systems via Discrete Empirical Interpolation, A literature survey of matrix methods for data science, Classification and image processing with a semi‐discrete scheme for fidelity forced Allen–Cahn on graphs, Deep learning methods for partial differential equations and related parameter identification problems, Deep learning‐based reduced order models for the real‐time simulation of the nonlinear dynamics of microstructures, Subsampling spectral clustering for stochastic block models in large-scale networks, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, Streaming Tensor Train Approximation, Interpolatory input and output projections for flow control, Quantum-inspired canonical correlation analysis for exponentially large dimensional data, An efficient randomized fixed-precision algorithm for tensor singular value decomposition, Online Principal Component Analysis in High Dimension: Which Algorithm to Choose?, Scalable methods for computing sharp extreme event probabilities in infinite-dimensional stochastic systems, Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization, Krylov-Aware Stochastic Trace Estimation, Randomized Low-Rank Approximation for Symmetric Indefinite Matrices, Randomized algorithms for orthogonal nonnegative matrix factorization, Parallel Algorithms for Computing the Tensor-Train Decomposition, Randomized Quasi-Optimal Local Approximation Spaces in Time, An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation, Practical sketching algorithms for low-rank Tucker approximation of large tensors, A new matrix maximization model for computing ratios of generalized singular values from high-order GSVD, Principled interpolation of Green's functions learned from data, Low tubal rank tensor completion based on singular value factors, Localized Model Reduction for Nonlinear Elliptic Partial Differential Equations: Localized Training, Partition of Unity, and Adaptive Enrichment, Optimal Reaction Coordinates: Variational Characterization and Sparse Computation, A Fast and Scalable Computational Framework for Large-Scale High-Dimensional Bayesian Optimal Experimental Design, Front transport reduction for complex moving fronts, Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations, Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems, A Predictor-Corrector Strategy for Adaptivity in Dynamical Low-Rank Approximations, CECM: a continuous empirical cubature method with application to the dimensional hyperreduction of parameterized finite element models, Haar-like wavelets on hierarchical trees, Pass-efficient truncated UTV for low-rank approximations, Universal Features for High-Dimensional Learning and Inference, HODLR\(d\)D: a new black-box fast algorithm for \(N\)-body problems in \(d\)-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines, A preconditioned iterative interior point approach to the conic bundle subproblem, A parallel low rank matrix optimization method for recovering Internet traffic network data via link flow measurement, Accelerated matrix completion algorithm using continuation strategy and randomized SVD, Solution of the EEG inverse problem by random dipole sampling, Stable probability of reduced matrix obtained by Gaussian random projection, A low-rank update for relaxed Schur complement preconditioners in fluid flow problems, A randomized algorithm for tensor singular value decomposition using an arbitrary number of passes, Randomized singular value decomposition for integrative subtype analysis of `omics data' using non-negative matrix factorization, Admissible subspaces and the subspace iteration method, Fast randomized numerical rank estimation for numerically low-rank matrices, Stable Rank-Adaptive Dynamically Orthogonal Runge–Kutta Schemes, Efficient Error and Variance Estimation for Randomized Matrix Computations, PyAlbany: a Python interface to the C++ multiphysics solver Albany, Spectral deviation of concentration operators for the short-time Fourier transform, A fast randomized algorithm for computing an approximate null space, Explicit deflation in Golub-Kahan-Lanczos bidiagonalization methods, On randomized sketching algorithms and the Tracy-Widom law, Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Randomized Low-Rank Approximation of Monotone Matrix Functions, Learning to Forecast Dynamical Systems from Streaming Data, A data-driven and model-based accelerated Hamiltonian Monte Carlo method for Bayesian elliptic inverse problems, Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems, Enabling Hyper-Differential Sensitivity Analysis for Ill-Posed Inverse Problems, PCA Sparsified, Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices, Large Deviation Theory-based Adaptive Importance Sampling for Rare Events in High Dimensions, XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation, UTV decomposition of dual matrices and its applications, Space-Time Reduced Basis Methods for Parametrized Unsteady Stokes Equations, Projection-based reduced order models for parameterized nonlinear time-dependent problems arising in cardiac mechanics, Fast macroscopic forcing method, Derivative-informed neural operator: an efficient framework for high-dimensional parametric derivative learning, Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition, Piecewise DMD for oscillatory and Turing spatio-temporal dynamics, Randomized low rank approximation for nonnegative pure quaternion matrices, Adaptive symplectic model order reduction of parametric particle-based Vlasov–Poisson equation, Unnamed Item, Accurate and fast matrix factorization for low-rank learning., Efficiency of randomised dynamic mode decomposition for reduced order modelling, Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Data-Driven Balancing of Linear Dynamical Systems, Active Subspace of Neural Networks: Structural Analysis and Universal Attacks, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Approximating Matrix Eigenvalues by Subspace Iteration with Repeated Random Sparsification, Manifold Learning and Nonlinear Homogenization, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, A Distance-Preserving Matrix Sketch, Structured Matrix Approximations via Tensor Decompositions, A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data, Modern Koopman Theory for Dynamical Systems, A machine learning approach to optimal Tikhonov regularization I: Affine manifolds, On expected error of randomized Nyström kernel regression, Improved Variants of the Hutch++ Algorithm for Trace Estimation, Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation, Selecting Regularization Parameters for Nuclear Norm--Type Minimization Problems, Subspaces Analysis for Random Projection UTV Framework, Fast deflation sparse principal component analysis via subspace projections, hm-toolbox: MATLAB Software for HODLR and HSS Matrices, Trading Beams for Bandwidth: Imaging with Randomized Beamforming, Unnamed Item, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Interpolative Decomposition Butterfly Factorization, Scalable Optimization-Based Sampling on Function Space, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, Analysis of amplification mechanisms and cross-frequency interactions in nonlinear flows via the harmonic resolvent, Randomized Sampling for Basis Function Construction in Generalized Finite Element Methods, Randomized matrix approximation to enhance regularized projection schemes in inverse problems, Regularized Linear Inversion with Randomized Singular Value Decomposition, Variational Gaussian approximation for Poisson data, Variable Projection Methods for an Optimized Dynamic Mode Decomposition, Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting, Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms, Concentration of the Frobenius Norm of Generalized Matrix Inverses, On the Best Approximation of the Hierarchical Matrix Product, Random Sampling and Efficient Algorithms for Multiscale PDEs, Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs, Sparse Solutions in Optimal Control of PDEs with Uncertain Parameters: The Linear Case, Spatio-temporal proper orthogonal decomposition of turbulent channel flow, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Globally Constructed Adaptive Local Basis Set for Spectral Projectors of Second Order Differential Operators, Randomized Approach to Nonlinear Inversion Combining Random and Optimized Simultaneous Sources and Detectors, Randomized Residual-Based Error Estimators for Parametrized Equations, Analytical Low-Rank Compression via Proxy Point Selection, Krylov Methods for Low-Rank Regularization, Tensor Train Construction From Tensor Actions, With Application to Compression of Large High Order Derivative Tensors, The AZ Algorithm for Least Squares Systems with a Known Incomplete Generalized Inverse, Estimating Higher-Order Moments Using Symmetric Tensor Decomposition, On Soft Errors in the Conjugate Gradient Method: Sensitivity and Robust Numerical Detection, Optimization-Based Markov Chain Monte Carlo Methods for Nonlinear Hierarchical Statistical Inverse Problems, A Data-Driven Approach for Multiscale Elliptic PDEs with Random Coefficients Based on Intrinsic Dimension Reduction, Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron, Norm and Trace Estimation with Random Rank-one Vectors, Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations, FANOK: Knockoffs in Linear Time, On the Numerical Rank of Radial Basis Function Kernels in High Dimensions, Singular Value Decomposition Approximation via Kronecker Summations for Imaging Applications, A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error, Adapting Regularized Low-Rank Models for Parallel Architectures, Unnamed Item, Uniform Error Estimates for the Lanczos Method, Taylor Approximation for Chance Constrained Optimization Problems Governed by Partial Differential Equations with High-Dimensional Random Parameters, Shallow neural networks for fluid flow reconstruction with limited sensors, Robust and Effective eSIF Preconditioning for General Dense SPD Matrices, Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning, An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity, Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization, Two-Level Nyström--Schur Preconditioner for Sparse Symmetric Positive Definite Matrices, The nonequilibrium quantum many-body problem as a paradigm for extreme data science, Acoustic full-waveform inversion and its uncertainty estimation based on a vector-version square-root variable metric method, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, Distributed Robust Subspace Recovery, Hierarchical Approximate Proper Orthogonal Decomposition, Low-Rank Independence Samplers in Hierarchical Bayesian Inverse Problems, Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic, Sharp error bounds for Ritz vectors and approximate singular vectors, Randomized singular spectrum analysis for long time series, Unnamed Item, Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices, Data-driven resolvent analysis, Randomized Sketching Algorithms for Low-Memory Dynamic Optimization, A Low-Rank Schwarz Method for Radiative Transfer Equation With Heterogeneous Scattering Coefficient, Hierarchical algorithms on hierarchical architectures, Numerical algorithms for high-performance computational science, Efficient Algorithms for Eigensystem Realization Using Randomized SVD, Scalable Semidefinite Programming, Sampled limited memory methods for massive linear inverse problems, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Sublinear Cost Low Rank Approximation via Subspace Sampling, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format, A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity, 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, 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, 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