Streaming low-rank matrix approximation with an application to scientific simulation
From MaRDI portal
(Redirected from Publication:5230655)
Abstract: This paper argues that randomized linear sketching is a natural tool for on-the-fly compression of data matrices that arise from large-scale scientific simulations and data collection. The technical contribution consists in a new algorithm for constructing an accurate low-rank approximation of a matrix from streaming data. This method is accompanied by an a priori analysis that allows the user to set algorithm parameters with confidence and an a posteriori error estimator that allows the user to validate the quality of the reconstructed matrix. In comparison to previous techniques, the new method achieves smaller relative approximation errors and is less sensitive to parameter choices. As concrete applications, the paper outlines how the algorithm can be used to compress a Navier--Stokes simulation and a sea surface temperature dataset.
Recommendations
- Practical sketching algorithms for low-rank matrix approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Low-rank Tucker approximation of a tensor from streaming data
- Fast low rank approximations of matrices and tensors
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
Cites work
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A fast randomized algorithm for the approximation of matrices
- A randomized algorithm for principal component analysis
- A randomized algorithm for the decomposition of matrices
- A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
- Algorithm 799: revolve
- An algorithm for the principal component analysis of large data sets
- Climate modeling for scientists and engineers
- Compression and Conditional Emulation of Climate Model Output
- Data streams: algorithms and applications.
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Dimensionality reduction for k-means clustering and low rank approximation
- Estimating Extremal Eigenvalues and Condition Numbers of Matrices
- Extensions of Lipschitz mappings into a Hilbert space
- Fast low-rank modifications of the thin singular value decomposition
- Fast monte-carlo algorithms for finding low-rank approximations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Frequent directions: simple and deterministic matrix sketching
- Geometric subspace updates with applications to online adaptive nonlinear model reduction
- scientific article; zbMATH DE number 3825358 (Why is no real title available?)
- scientific article; zbMATH DE number 1256715 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- scientific article; zbMATH DE number 4115838 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved bounds for small-sample estimation
- Improved bounds on sample size for implicit matrix trace estimators
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Large Eddy Simulation for Compressible Flows
- Large Eddy Simulation for Incompressible Flows
- Latent semantic indexing: A probabilistic analysis
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Low-rank Tucker approximation of a tensor from streaming data
- Lower bounds for oblivious subspace embeddings
- Model-based scaling of the streamwise energy density in high-Reynolds-number turbulent channels
- Nearly tight oblivious subspace embeddings by trace inequalities
- Numerical linear algebra in the streaming model
- Optimal principal component analysis in distributed and streaming models
- Practical sketching algorithms for low-rank matrix approximation
- Principal component analysis.
- Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
- Randomized Algorithms for Matrices and Data
- Sketching as a tool for numerical linear algebra
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- Tracking join and self-join sizes in limited storage
- Turnstile streaming algorithms might as well be linear sketches
Cited in
(42)- Single-pass randomized QLP decomposition for low-rank approximation
- Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
- Pass-efficient methods for compression of high-dimensional turbulent flow data
- Spectral estimation from simulations via sketching
- A stable parareal-like method for the second order wave equation
- Single-pass randomized algorithms for LU decomposition
- Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition
- Randomized sketching algorithms for low-memory dynamic optimization
- Scalable semidefinite programming
- Low-rank Tucker approximation of a tensor from streaming data
- A nonlinear matrix decomposition for mining the zeros of sparse data
- A multilevel Monte Carlo estimator for matrix multiplication
- Memory-efficient structured convex optimization via extreme point sampling
- Perturbations of CUR Decompositions
- Randomized numerical linear algebra: Foundations and algorithms
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
- Finding robust minimizer for non-convex phase retrieval
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Practical sketching algorithms for low-rank Tucker approximation of large tensors
- Principled interpolation of Green's functions learned from data
- Pass-efficient truncated UTV for low-rank approximations
- Fast Metric Embedding into the Hamming Cube
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Efficient Error and Variance Estimation for Randomized Matrix Computations
- A fast randomized algorithm for computing an approximate null space
- A streaming approach for sparse matrix products and its application in Galerkin multigrid methods
- Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- Single-pass Nyström approximation in mixed precision
- Scalable symmetric Tucker tensor decomposition
- Fast and forward stable randomized algorithms for linear least-squares problems
- Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
- Subspace method of moments for \textit{ab initio} 3-D single particle cryo-EM reconstruction
- Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Optimal backward error of a total least squares and its randomized algorithms
- Combining randomized and deterministic iterative algorithms for high accuracy solution of large linear systems and boundary integral equations
- Randomized low-rank approximations beyond Gaussian random matrices
- Efficient estimate for the optimal backward error of the multidimensional total least squares
- Ascend to Science: Exploration of AI Chips for Scientific Computing
- librla: Randomized Linear Algebra Library
This page was built for publication: Streaming low-rank matrix approximation with an application to scientific simulation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230655)
