Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
From MaRDI portal
Publication:6062237
Abstract: As the scale of problems and data used for experimental design, signal processing and data assimilation grow, the oft-occuring least squares subproblems are correspondingly growing in size. As the scale of these least squares problems creates prohibitive memory movement costs for the usual incremental QR and Krylov-based algorithms, randomized least squares problems are garnering more attention. However, these randomized least squares solvers are difficult to integrate application algorithms as their uncertainty limits practical tracking of algorithmic progress and reliable stopping. Accordingly, in this work, we develop theoretically-rigorous, practical tools for quantifying the uncertainty of an important class of iterative randomized least squares algorithms, which we then use to track algorithmic progress and create a stopping condition. We demonstrate the effectiveness of our algorithm by solving a 0.78 TB least squares subproblem from the inner loop of incremental 4D-Var using only 195 MB of memory.
Recommendations
- scientific article; zbMATH DE number 6402625
- Near optimal solutions to least-squares problems with stochastic uncertainty
- Near optimal solutions to least-squares problems with stochastic uncertainty
- Randomized iterative methods for linear systems
- Stochastic iterative projection methods for large linear systems
- Randomized extended Kaczmarz for solving least squares
- Splitting-based randomized iterative methods for solving indefinite least squares problem
- scientific article; zbMATH DE number 1058092
- A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
- On Discrete Least-Squares Projection in Unbounded Domain with Random Evaluations and its Application to Parametric Uncertainty Quantification
Cites work
- A Practical Method to Estimate Information Content in the Context of 4D-Var Data Assimilation
- A statistical perspective on randomized sketching for ordinary least-squares
- Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
- An elementary proof of a theorem of Johnson and Lindenstrauss
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Extensions of Lipschitz mappings into a Hilbert space
- GMRES methods for least squares problems
- High-dimensional statistics. A non-asymptotic viewpoint
- scientific article; zbMATH DE number 48363 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Linear Least Squares Approach for Accurate Received Signal Strength Based Source Localization
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- On variants of the Johnson–Lindenstrauss lemma
- Randomized Block Adaptive Linear System Solvers
- Randomized iterative methods for linear systems
- Regression-based sparse polynomial chaos for uncertainty quantification of subsurface flow models
- Sparse kernel regression modeling using combined locally regularized orthogonal least squares and d-optimality experimental design
- Stochastic reformulations of linear systems: algorithms and convergence theory
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
Cited in
(4)- Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides
- On Discrete Least-Squares Projection in Unbounded Domain with Random Evaluations and its Application to Parametric Uncertainty Quantification
- Solving, tracking and stopping streaming linear inverse problems
- Blind error estimation for CUR approximation
This page was built for publication: Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6062237)
