×

An iterative method for Tikhonov regularization with a general linear regularization operator. (English) Zbl 1210.65092

To solve a large scale ill-posed linear least squares problem \(Ax=b\) with \(A\in {\mathbb C}^{m\times n}\), a general regularization is proposed in which one has to minimize \(\|Ax-b\|^2+\mu\|Lx\|^2\) with regularization parameter \(\mu>0\) and regularization operator \(L\). It is assumed that \(Ax=\hat{b}\) is consistent and that an upper bound \(\delta\) is known for the perturbation \(b-\hat{b}\). The proposed iterative method is based on a Golub-Kahan bidiagonalization of \(A\). This projects the problem on a \(k\)-dimensional subspace so that one has to solve a \(\mu\)-dependent least squares problem of size \((2k+1)\times k\) with a simple right-hand side that has only one nonzero element.
The main idea of the paper is to use a value for \(\mu=\mu(\delta)\) such that with the corresponding solution \(x^{(\mu)}\) one has \(\|Ax^{(\mu)}-b\|=\eta\delta\) with \(\eta>1\) a user-specified constant. This identifies \(\nu=1/\mu\) as a Lagrange multiplier for \(\min \|Lx\|\) with constraint \(\|Ax-b\|=\eta\delta\). This \(\nu\) satisfies in general an equation with a unique solution. The numerical applications given include discretization of integral equations and image processing. In the printed version, the blue graphs for the examples are missing. These are visible in the on-line version.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65R30 Numerical methods for ill-posed problems for integral equations
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
45B05 Fredholm integral equations
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M.L. Baart, The use of auto-correlation for pseudo-rank determination in noisy ill-conditioned least-squares problems , IMA J. Numer. Anal. 2 (1982), 241-247. · Zbl 0484.65021
[2] J. Baglama and L. Reichel, Decomposition methods for large linear discrete ill-posed problems , J. Comput. Appl. Math. 198 (2007), 332-342. · Zbl 1106.65035
[3] Å. Björck, Numerical methods for least squares problems , SIAM, Philadelphia, 1996. · Zbl 0847.65023
[4] A. Bunse-Gerstner, V. Guerra-Ones and H. Madrid de La Vega, An improved preconditioned LSQR for discrete ill-posed problems , Math. Comput. Simul. 73 (2006), 65-75. · Zbl 1104.65034
[5] D. Calvetti, P.C. Hansen and L. Reichel, L -curve curvature bounds via Lanczos bidiagonalization, Electron. Trans. Numer. Anal. 14 (2002), 20-35. · Zbl 1029.65041
[6] D. Calvetti and L. Reichel, Tikhonov regularization of large linear problems , BIT 43 (2003), 263-283. · Zbl 1038.65048
[7] D. Calvetti, L. Reichel and A. Shuibi, Invertible smoothing preconditioners for linear discrete ill-posed problems , Appl. Numer. Math. 54 (2005), 135-149. · Zbl 1072.65057
[8] J.W. Daniel, W.B. Gragg, L. Kaufman and G.W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp. 30 (1976), 772-795. · Zbl 0345.65021
[9] L. Eldén, A weighted pseudoinverse, generalized singular values, and constrained least squares problems , BIT 22 (1982), 487-501. · Zbl 0509.65019
[10] H.W. Engl, M. Hanke and A. Neubauer, Regularization of inverse problems , Kluwer, Dordrecht, 1996. · Zbl 0859.65054
[11] G.H. Golub and C.F. Van Loan, Matrix computations , 3rd ed., Johns Hopkins University Press, Baltimore, 1996. · Zbl 0865.65009
[12] C.W. Groetsch, The theory of Tikhonov regularization for Fredholm equations of the first kind , Pitman, Boston, 1984. · Zbl 0545.65034
[13] P.C. Hansen, Rank-deficient and discrete ill-posed problems , SIAM, Philadelphia, 1998. · Zbl 0890.65037
[14] ——–, Regularization tools version 4.0 for Matlab 7.3, Numer. Algorithms 46 (2007), 189-194. · Zbl 1128.65029
[15] M. Jacobsen, P.C. Hansen and M.A. Saunders, Subspace preconditioned LSQR for discrete ill-posed problems, BIT 43 (2003), 975-989. · Zbl 1046.65030
[16] M.E. Kilmer, P.C. Hansen and M.I. Español, A projection-based approach to general-form Tikhonov regularization , SIAM J. Sci. Comput. 29 (2007), 315-330. · Zbl 1140.65030
[17] S. Morigi, L. Reichel and F. Sgallari, A truncated projected SVD method for linear discrete ill-posed problems, Numer. Algorithms 43 (2006), 197-213. · Zbl 1114.65039
[18] ——–, Orthogonal projection regularization operators , Numer. Algorithms 44 (2007), 99-114. · Zbl 1124.65043
[19] F. Natterer, Regularisierung schlecht gestellter Probleme durch Projektionsverfahren , Numer. Math. 28 (1977), 329-341. · Zbl 0364.65042
[20] L. Reichel, F. Sgallari and Q. Ye, Tikhonov regularization based on generalized Krylov subspace methods , submitted. · Zbl 1246.65068
[21] L. Reichel and Q. Ye, Simple square smoothing regularization operators , Electron. Trans. Numer. Anal. 33 (2009), 63-83. · Zbl 1171.65033
[22] G. Wahba, Spline models for observational data , SIAM, Philadelphia, 1990. · Zbl 0813.62001
[23] H. Zha, Computing the generalized singular values/vectors of large sparse or structured matrix pairs , Numer. Math. 72 (1996), 391-417. · Zbl 0856.65041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.