×

Acceleration of sequential subspace optimization in Banach spaces by orthogonal search directions. (English) Zbl 1458.65062

Summary: A standard solution technique for linear operator equations of first kind is the Landweber scheme which is an iterative method that uses the negative gradient of the current residual as search direction, which is also called the Landweber direction. Though this method proves to be stable with respect to noisy data, it is known to be numerically slow for problems in Hilbert spaces and this behavior shows to be even worse in some Banach space settings. This is why the idea came up to use several search directions instead of the Landweber direction only which has led to the development of Sequential Subspace Optimization (SESOP) methods. This idea is related to the famous Conjugate Gradient (CG) techniques that are known to be amongst the most effective methods to solve linear equations in Hilbert spaces. Since CG methods decisively make use of the inner product structure, they have been inherently restricted to Hilbert spaces so far. SESOP methods in Banach spaces do not share the conjugacy property with CG methods. In this article we use the concept of generalized orthogonality in Banach spaces and apply metric projections to orthogonalize the current Landweber direction with respect to the search space of the last iteration. This leads to an accelerated SESOP method which is confirmed by various numerical experiments. Moreover, in Hilbert spaces our method coincides with the Conjugate Gradient Normal Error (CGNE) or Craig’s method applied to the normal equation. We prove weak convergence to the exact solution. Furthermore we perform a couple of numerical tests on a linear problem involving a random matrix and on the problem of 2D computerized tomography where we use different \(\ell_p\)-spaces. In all experiments the orthogonalization of the search space shows superior convergence properties compared to standard SESOP. This especially holds for \(p\) close to 1. Letting \(p \rightarrow 2\) the more we recover the conjugacy property for the search directions and the more the convergence behaves independently of the size of the search space.

MSC:

65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
65F10 Iterative numerical methods for linear systems
65K10 Numerical optimization and variational techniques

Software:

Eigen
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Schöpfer, F.; Louis, A. K.; Schuster, T., Nonlinear iterative methods for linear ill-posed problems in Banach spaces, Inverse Problems, 22, 1, 311-329, (2006) · Zbl 1088.65052
[2] Hanke, M.; Neubauer, A.; Scherzer, O., A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72, 1, 21-37, (1995) · Zbl 0840.65049
[3] Kirsch, A., An introduction to the mathematical theory of inverse problems, 1-314, (2011), Springer Science+Business Media New York Dordrecht Heidelberg London Library
[4] Schöpfer, F.; Schuster, T.; Louis, A. K., Metric and Bregman projections onto affine subspaces and their computation via sequential subspace optimization methods, J. Inverse Ill-Posed Probl., 16, 5, 1-29, (2008) · Zbl 1160.46048
[5] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 6, 409-436, (1952) · Zbl 0048.09901
[6] Nocedal, J.; Wright, S. J., Numerical optimization, 1-636, (1999), Springer-Verlag New York · Zbl 0930.65067
[7] G. Narkiss, M. Zibulevsky, Sequential subspace optimization method for large-scale unconstrained problems, 2005.; G. Narkiss, M. Zibulevsky, Sequential subspace optimization method for large-scale unconstrained problems, 2005.
[8] Schöpfer, F.; Schuster, T., Fast regularizing sequential subspace optimization in Banach spaces, Inverse Problems, 25, 1, 1-22, (2009) · Zbl 1165.47010
[9] Wald, A.; Schuster, T., Sequential subspace optimization for nonlinear inverse problems, J. Inverse Ill-Posed Probl., 25, 4, (2016)
[10] Schöpfer, F., Iterative regularization methods for the solution of the split feasibility problem in Banach spaces, 1-108, (2007), Universität des Saarlandes, (Doctoral thesis)
[11] Craig, E. J., The N -step iteration procedures, J. Math. Phys., 34, 1-4, 64-73, (1955) · Zbl 0065.10901
[12] Alber, Y. I., James orthogonality and orthogonal decompositions of Banach spaces, J. Math. Anal. Appl., 312, 1, 330-342, (2005) · Zbl 1095.46007
[13] Cioranescu, I., Geometry of Banach spaces, duality mappings and nonlinear problems, 1-260, (1990), Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0712.47043
[14] Schuster, T.; Kaltenbacher, B.; Hofmann, B.; Kazimierski, K. S., Regularization methods in Banach spaces, (2012), De Gruyter · Zbl 1259.65087
[15] Lindenstrauss, J., On the modulus of smoothness and divergent series in Banach spaces., Michigan Math. J., (1963) · Zbl 0115.10001
[16] Clarkson, J. A., Uniformly convex spaces, Trans. Amer. Math. Soc., 40, 3, 396, (1936) · JFM 62.0460.04
[17] Day, M. M., Uniform convexity in factor and conjugate spaces, Ann. Mat., 45, 2, 375, (1944) · Zbl 0063.01058
[18] Lindenstrauss, J.; Tzafriri, L., Classical Banach spaces II - function spaces, 1-243, (1979), Springer-Verlag Berlin Heidelberg New York
[19] Schechter, M., Principles of functional analysis, 1-383, (1971), Academic Press, Inc. New York · Zbl 0211.14501
[20] Xu, Z.-b.; Roach, G. F., Characteristic inequalities of uniformly convex and uniformly smooth Banach spaces, J. Math. Anal. Appl., 157, 1, 189-210, (1991) · Zbl 0757.46034
[21] Chidume, C., (Geometric Properties of Banach Spaces and Nonlinear Iterations, Lecture Notes in Mathematics, vol. 1965, (2009), Springer London London) · Zbl 1167.47002
[22] Censor, Y.; Zenios, A., Parallel optimization - theory, algorithms, and applications, (1997), Oxford University Press New York, Oxford · Zbl 0945.90064
[23] Roberts, B. D., On the geometry of abstract vector spaces, Tohoku Math. J., First Ser., 39, 1927, 42-59, (1934) · JFM 60.1074.02
[24] Birkhoff, G., Orthogonality in linear metric spaces, Duke Math. J., 1, 169-172, (1935) · Zbl 0012.30604
[25] James, R. C., Orthogonality in normed linear spaces, Duke Math. J., 12, 2, 291-302, (1945) · Zbl 0060.26202
[26] Muscat, J., Functional analysis, 1-420, (2014), Springer International Publishing Cham
[27] Yuan, Y.-X.; Stoer, J., A subspace study on conjugate gradient algorithms, ZAMM - J. Appl. Math. Mech., 75, 11, 69-77, (1995) · Zbl 0823.65061
[28] Dunford, N.; Schwartz, J. T., Linear operators - part I - general theory, 1-858, (1957), Interscience Publishers, Inc. New York
[29] Zeidler, E., Nonlinear functional analysis and its applications. 1. fixed-point theorems, 1-897, (1986), Springer-Verlag Berlin Heidelberg New York Berlin Heidelberg New York
[30] Ashby, S. F.; Manteuffel, T. A.; Saylor, P. E., A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal., 27, 6, 1542-1568, (1990) · Zbl 0723.65018
[31] Saad, Y., Iterative methods for sparse linear systems, 1-528, (2003), Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1031.65046
[32] Chronopoulos, A.; Zlatev, Z., Iterative methods for nonlinear operator equations, Appl. Math. Comput., 51, 2-3, 167-180, (1992) · Zbl 0760.65055
[33] Golub, G. H.; O’Leary, D. P., Some history of the conjugate gradient and Lanczos methods, SIAM Rev., 31, 1, 50-102, (1989) · Zbl 0673.65017
[34] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Natl. Bur. Stand. B, 49, 1, 33-53, (1952)
[35] Golub, G. H.; van Loan, C. F., Matrix computations, (1996), The Johns Hopkins University Press London · Zbl 0865.65009
[36] G. Guennebaud, B. Jacob, et al., Eigen v3, 2010, URL http://eigen.tuxfamily.org; G. Guennebaud, B. Jacob, et al., Eigen v3, 2010, URL http://eigen.tuxfamily.org
[37] Loris, I., On the performance of algorithms for the minimization of l1 -penalized functionals, Inverse Problems, 25, 3, (2009)
[38] Natterer, F., The mathematics of computerized tomography, (1986), Wiley Chichester · Zbl 0617.92001
[39] Natterer, F.; Wübbeling, F., Mathematical methods in image reconstruction, (2001), SIAM Philadelphia · Zbl 0974.92016
[40] Hansen, P. C., Discrete inverse problems - insight and algorithms, 1-213, (2010), SIAM · Zbl 1197.65054
[41] Andrei, N., Another nonlinear conjugate gradient algorithm for unconstrained optimization, Optim. Methods Softw., 24, 1, 89-104, (2009) · Zbl 1154.90586
[42] Nemirovskii, A., The regularizing properties of the adjoint gradient method in ill-posed problems, USSR Comput. Math. Math. Phys., 26, 2, 7-16, (1986) · Zbl 0615.65056
[43] Hanke, M., (Conjugate Gradient type Methods for ill-posed Problems, Pitman Research Notes in Mathematics Series, vol. 327, (1995), Longman Scientific & Technical Burnt Mill, Harlow, England) · Zbl 0830.65043
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.