On the augmented system approach to sparse least-squares problems
From MaRDI portal
When the least-squares problem \(\| Ax-b\|_ 2\to \min !\) is to be solved, one may consider the augmented system \[ \left( \begin{matrix} I\\ A^ T\end{matrix} \begin{matrix} A\\ 0\end{matrix} \right)\left( \begin{matrix} r\\ x\end{matrix} \right)=\left( \begin{matrix} b\\ 0\end{matrix} \right) \] instead of the normal equations. In order to reduce the condition number of the augmented matrix, the identity matrix I may be replaced by \(\alpha\) I with \(\alpha\) being a suitable scaling factor. Iterative refinements and perturbation theoretic arguments are discussed in the framework of an error analysis. Ten tables with numerical results for several test matrices are given.
Recommendations
Cites work
- A new polynomial-time algorithm for linear programming
- A Survey of Condition Number Estimation for Triangular Matrices
- Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
- Condition Estimates
- scientific article; zbMATH DE number 3604265 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- scientific article; zbMATH DE number 3363343 (Why is no real title available?)
- Iterative Refinement Implies Numerical Stability for Gaussian Elimination
- Iterative refinement of linear least squares solutions I
- Jordan-Elimination und Ausgleichung nach kleinsten Quadraten
- On the Method of Weighting for Equality-Constrained Least-Squares Problems
- Scaling for Numerical Stability in Gaussian Elimination
- Solving Sparse Linear Systems with Sparse Backward Error
- Sparse matrix test problems
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
Cited in
(57)- Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution
- Iterative refinement enhances the stability of \(QR\) factorization methods for solving linear equations
- Selection of fictitious independent variables for the solution of sparse linear equations
- The augmented system variant of IPMs in two-stage stochastic linear programming computation
- Warm start of the primal-dual method applied in the cutting-plane scheme
- The role of the augmented system in interior point methods
- Solving symmetric indefinite systems in an interior-point method for linear programming
- Corrected sequential linear programming for sparse minimax optimization
- Solution of augmented linear systems using orthogonal factorizations
- Componentwise analysis of direct factorization of real symmetric and Hermitian matrices
- Perturbation bound of singular linear systems
- Generalized AOR method for solving a class of generalized saddle point problems
- Variants of the Uzawa method for three-order block saddle point problem
- Solution of sparse rectangular systems using LSQR and Craig
- Iterative refinement of linear least squares solutions
- A parameterized shift-splitting preconditioner for saddle point problems
- Improved componentwise verified error bounds for least squares problems and underdetermined linear systems
- Exploiting structure in parallel implementation of interior point methods for optimization
- A generalized shift-splitting preconditioner for saddle point problems
- Semi-convergence analysis of GMSSOR methods for singular saddle point problems
- A class of new extended shift-splitting preconditioners for saddle point problems
- Convergence of a generalized MSSOR method for augmented systems
- Symmetric-triangular decomposition and its applications. II: Preconditioners for indefinite systems
- Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill-posed problems.
- Imposing symmetry in augmented linear systems.
- Regularization and preconditioning of KKT systems arising in nonnegative least-squares problems
- scientific article; zbMATH DE number 5815888 (Why is no real title available?)
- scientific article; zbMATH DE number 992796 (Why is no real title available?)
- On mixed and componentwise condition numbers for Moore–Penrose inverse and linear least squares problems
- Preconditioning indefinite systems in interior point methods for large scale linear optimisation
- An augmented LSQR method
- Implementing cholesky factorization for interior point methods of linear programming
- scientific article; zbMATH DE number 554733 (Why is no real title available?)
- Interior point methods 25 years later
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
- A novel partitioning method for accelerating the block Cimmino algorithm
- A condition analysis of the weighted linear least squares problem using dual norms
- Perturbation analysis of saddle-point problems
- A class of modified GSS preconditioners for complex symmetric linear systems
- Efficient Preconditioners for Interior Point Methods via a New Schur Complement-Based Strategy
- On the GTSOR-like Method for the Augmented systems
- On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems
- On condition numbers for Moore-Penrose inverse and linear least squares problem involving Kronecker products
- A survey of direct methods for sparse linear systems
- Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement
- A modified symmetric successive overrelaxation method for augmented systems
- Sparse linear least-squares problems
- A new parameterized matrix splitting preconditioner for the saddle point problems
- A comparison of mixed precision iterative refinement approaches for least-squares problems
- The modified double shift-splitting preconditioner for nonsymmetric generalized saddle point problems from the time-harmonic Maxwell equations
- On the minimum convergence factor of a class of GSOR-like methods for augmented systems
- Component-wise perturbation analysis and error bounds for linear least squares solutions
- Symmetric SOR method for augmented systems
- Convergence of relaxation iterative methods for saddle point problem
- The solution of large-scale least-squares problems on supercomputers
- On generalized symmetric SOR method for augmented systems
- A class of Uzawa-SOR methods for saddle point problems
This page was built for publication: On the augmented system approach to sparse least-squares problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124275)
