Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
From MaRDI portal
Abstract: Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. Firstly, a mechanism for calculating the approximation error in Frobenius norm is proposed, which enables efficient adaptive rank determination for large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by P.-G. Martinsson and S. Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem.
Recommendations
- Randomized algorithms for the low-rank approximation of matrices
- A fast randomized algorithm for the approximation of matrices
- A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Randomized methods for matrix computations
Cites work
- A randomized algorithm for principal component analysis
- A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
- Algorithm 971
- ARPACK Users' Guide
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Householder QR factorization with randomization for column pivoting (HQRRP)
- scientific article; zbMATH DE number 5161643 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval
- Practical sketching algorithms for low-rank matrix approximation
- Randomized Algorithms for Matrices and Data
- Randomized QR with column pivoting
Cited in
(47)- 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
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
- Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
- Randomized quaternion QLP decomposition for low-rank approximation
- Learning mean-field equations from particle data using WSINDy
- Randomized QLP decomposition
- Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation
- scientific article; zbMATH DE number 7008333 (Why is no real title available?)
- Reliable Krylov-based algorithms for matrix null space and rank
- Efficient algorithms for eigensystem realization using randomized SVD
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
- scientific article; zbMATH DE number 7525476 (Why is no real title available?)
- Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
- Compressing Rank-Structured Matrices via Randomized Sampling
- A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
- An efficient randomized QLP algorithm for approximating the singular value decomposition
- Randomized algorithms for the computation of multilinear rank-(_1,_2,_3) approximations
- Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
- An efficient randomized fixed-precision algorithm for tensor singular value decomposition
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Fast randomized numerical rank estimation for numerically low-rank matrices
- A fast randomized algorithm for computing an approximate null space
- RA-HOOI: rank-adaptive higher-order orthogonal iteration for the fixed-accuracy low multilinear-rank approximation of tensors
- SVD-based algorithms for fully-connected tensor network decomposition
- An L-DEIM induced high order tensor interpolatory decomposition
- SVD-based algorithms for tensor wheel decomposition
- Efficient randomized algorithms for computing an approximation of the tensor train decomposition
- RTSMS: randomized Tucker with single-mode sketching
- A hybrid algorithm for computing a partial singular value decomposition satisfying a given threshold
- Space-time isogeometric analysis of cardiac electrophysiology
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Efficient quaternion CUR decomposition based on discrete empirical interpolation method
- Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
- Randomized algorithms for computing the generalized tensor SVD based on the tensor product
- Adaptive, Matrix-Free Low-Rank Approximation
- Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation
- A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition
- Exact quantum dynamics of Fermi-Hubbard systems using the Gaussian phase-space representation with diffusion gauges
- Incremental Column Subset Selection via Conditional Determinantal Point Processes
- Robust multidimensional data completion via tensor fully connected networks: a nonconvex nonnegative framework
This page was built for publication: Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584924)
