The Joint Bidiagonalization of a Matrix Pair with Inaccurate Inner Iterations

DOI10.1137/22M1541083MaRDI QIDQ6180360zbMATH OpenOpenAlexWikidataFDO

Authors Haibo Li

Publication date 19 January 2024

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.06943

zbMATH Keywords

convergence and accuracyGSVDinner iterationjoint bidiagonalizationLanczos bidiagonalizationstopping tolerance

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Orthogonalization in numerical linear algebra (65F25) Error analysis and interval analysis (65G99)

Abstract: The joint bidiagonalization (JBD) process iteratively reduces a matrix pair $A,B$ to two bidiagonal forms simultaneously, which can be used for computing a partial generalized singular value decomposition (GSVD) of $A,B$. The process has a nested inner-outer iteration structure, where the inner iteration usually can not be computed exactly. In this paper, we study the inaccurately computed inner iterations of JBD by first investigating influence of computational error of the inner iteration on the outer iteration, and then proposing a reorthogonalized JBD (rJBD) process to keep orthogonality of a part of Lanczos vectors. An error analysis of the rJBD is carried out to build up connections with Lanczos bidiabonalizations. The results are then used to investigate convergence and accuracy of the rJBD based GSVD computation. It is shown that the accuracy of computed GSVD components depend on the computing accuracy of inner iterations and condition number of $(A^T,B^T{)}^T$ while the convergence rate is not affected very much. For practical JBD based GSVD computations, our results can provide a guideline for choosing a proper computing accuracy of inner iterations in order to obtain approximate GSVD components with a desired accuracy. Numerical experiments are made to confirm our theoretical results.

Recommendations

• The joint bidiagonalization process with partial reorthogonalization
• The joint bidiagonalization method for large GSVD computations in finite precision
• Thick-restarted joint Lanczos bidiagonalization for the GSVD
• On inner iterations of Jacobi-Davidson type methods for large SVD computations

Cites work

• A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations
• A Jacobi--Davidson Iteration Method for Linear Eigenvalue Problems
• A Jacobi--Davidson Method for Solving Complex Symmetric Eigenvalue Problems
• A joint bidiagonalization based iterative algorithm for large scale general-form Tikhonov regularization
• A Note on a Result of Sun Ji-Guang: Sensitivity of the CS and GSV Decompositions
• A Projection‐Based Approach to General‐Form Tikhonov Regularization
• A useful form of unitary matrix obtained from any sequence of unit 2-norm n-vectors
• Accuracy and Stability of Numerical Algorithms
• Bounds on Perturbations of Generalized Singular Values and of Associated Subspaces
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• Computational Variants of the Lanczos Method for the Eigenproblem
• Computing the generalized singular values/vectors of large sparse or structured matrix pairs
• Controlling inner iterations in the Jacobi-Davidson method
• Discrete inverse problems. Insight and algorithms.
• Generalizing the Singular Value Decomposition
• scientific article; zbMATH DE number 3884316 (Why is no real title available?)
• scientific article; zbMATH DE number 3978275 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Partial least-squares vs. Lanczos bidiagonalization. I: Analysis of a projection method for multiple regression
• Perturbation Analysis for the Generalized Singular Value Problem
• Perturbation bounds in connection with singular value decomposition
• Rank-Deficient and Discrete Ill-Posed Problems
• Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction
• The QR Algorithm Revisited
• The Joint Bidiagonalization Method for Large GSVD Computations in Finite Precision
• The joint bidiagonalization process with partial reorthogonalization
• The University of Florida sparse matrix collection
• Towards a Generalized Singular Value Decomposition
• Uniform accuracy of eigenpairs from a shift‐invert Lanczos method

Cited in

(3)

• A preconditioned Krylov subspace method for linear inverse problems with general-form Tikhonov regularization
• Projected Newton method for large-scale Bayesian linear inverse problems
• Characterizing GSVD by singular value expansion of linear operators and its computation

This page was built for publication: The Joint Bidiagonalization of a Matrix Pair with Inaccurate Inner Iterations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180360)