5
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Approximation Accuracy of the Krylov Subspaces for Linear Discrete Ill-Posed Problems

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          For the large-scale linear discrete ill-posed problem \(\min\|Ax-b\|\) or \(Ax=b\) with \(b\) contaminated by white noise, the Lanczos bidiagonalization based Krylov solver LSQR and its mathematically equivalent CGLS, the Conjugate Gradient (CG) method implicitly applied to \(A^TAx=A^Tb\), are most commonly used, and CGME, the CG method applied to \(\min\|AA^Ty-b\|\) or \(AA^Ty=b\) with \(x=A^Ty\), and LSMR, which is equivalent to the minimal residual (MINRES) method applied to \(A^TAx=A^Tb\), have also been choices. These methods have intrinsic regularizing effects, where the iteration number \(k\) plays the role of the regularization parameter. However, there has been no definitive answer to the long-standing fundamental question: {\em can LSQR and CGLS can find best possible regularized solutions}? The same question is for CGME and LSMR too. At iteration \(k\), these four methods compute iterates from the same \(k\) dimensional Krylov subspace when starting vectors are chosen properly. A first and fundamental step towards to answering the above question is to accurately estimate the accuracy of the underlying \(k\) dimensional Krylov subspace approximating the \(k\) dimensional dominant right singular subspace of \(A\). Assuming that the singular values of \(A\) are simple, we present a general \(\sin\Theta\) theorem for the 2-norm distances between the two subspaces, derive accurate estimates on them for severely, moderately and mildly ill-posed problems, and establish some relationships between the smallest Ritz values and these distances. Numerical experiments justify our estimates and theory.

          Related collections

          Most cited references 26

          • Record: found
          • Abstract: not found
          • Article: not found

          Methods of conjugate gradients for solving linear systems

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Solution of Sparse Indefinite Systems of Linear Equations

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter

                Bookmark

                Author and article information

                Journal
                24 May 2018
                Article
                1805.10132

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                65F22, 15A18, 65F10, 65F20, 65R32, 65J20, 65R30
                30 pages, 22 figures. arXiv admin note: substantial text overlap with arXiv:1701.05708, arXiv:1608.05907
                math.NA

                Numerical & Computational mathematics

                Comments

                Comment on this article