Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
From MaRDI portal
Publication:5470749
DOI10.1137/S0097539704442684zbMath1111.68147OpenAlexW2042465463MaRDI QIDQ5470749
Michael W. Mahoney, Petros Drineas, Ravindran Kannan
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704442684
Related Items
Randomized numerical linear algebra: Foundations and algorithms, Functional principal subspace sampling for large scale functional data analysis, Unnamed Item, A randomized algorithm for a tensor-based generalization of the singular value decomposition, Far-field compression for fast kernel summation methods in high dimensions, Optimal projection of observations in a Bayesian setting, A randomized approach to sensor placement with observability assurance, Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps, Pseudo-skeleton approximations with better accuracy estimates, A sketched finite element method for elliptic models, Asymptotic error bounds for kernel-based Nyström low-rank approximation matrices, Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument, Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, Model order reduction with oblique projections for large scale wave propagation, Structural conditions for projection-cost preservation via randomized matrix multiplication, A literature survey of matrix methods for data science, Pass-efficient randomized LU algorithms for computing low-rank matrix approximation, A hybrid stochastic interpolation and compression method for kernel matrices, A nonconvex approach to low-rank matrix completion using convex optimization, Optimal sampling algorithms for block matrix multiplication, Faster least squares approximation, Optimal subsampling for softmax regression, Unnamed Item, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, A block-randomized stochastic method with importance sampling for CP tensor decomposition, CUR and Generalized CUR Decompositions of Quaternion Matrices and their Applications, Solution of the EEG inverse problem by random dipole sampling, Exemplar-based large-scale low-rank matrix decomposition for collaborative prediction, Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory, A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality, Detecting the large entries of a sparse covariance matrix in sub-quadratic time, Optimal CUR Matrix Decompositions, Fast matrix multiplication and its algebraic neighbourhood, A Multilevel Monte Carlo Estimator for Matrix Multiplication, 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, Sub-sampled Newton methods, Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions, Finite dimensional approximation and Newton-based algorithm for stochastic approximation in Hilbert space, Projected Landweber iteration for matrix completion, Unnamed Item, Unnamed Item, Unnamed Item, Random matrices: The distribution of the smallest singular values, Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification, Proximal algorithms and temporal difference methods for solving fixed point problems, A way for low ranking matrices and its stochastic computations using Monte Carlo method, Stochastic iterative projection methods for large linear systems, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, Stochastic boundary methods of fundamental solutions for solving PDEs, Less is More: Sparse Graph Mining with Compact Matrix Decomposition, Multiplicative Approximations of Random Walk Transition Probabilities, Algorithms and applications for approximate nonnegative matrix factorization, Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably, Randomized signal processing with continuous frames, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, New hybrid Monte Carlo methods and computing the dominant generalized eigenvalue, Fast Randomized Algorithms for t-Product Based Tensor Operations and Decompositions with Applications to Imaging Data, Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements, Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method, Subsampling Algorithms for Semidefinite Programming, Multiway Monte Carlo Method for Linear Systems, Low-Rank Matrix Approximations Do Not Need a Singular Value Gap, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching, Subdata selection algorithm for linear model discrimination
