On the rate of convergence of the alternating projection method in finite dimensional spaces. (English) Zbl 1074.65059
Summary: Using the results of K. Smith, D. Solomon, and S. Wagner [Bull. Amer. Math. Soc. 83, 1227–1270 (1977; Zbl 0521.65090)] and S. Nelson and M. Neumann [Numer. Math. 51, 123–141 (1987; Zbl 0628.65024)] we derive new estimates for the speed of the alternating projection method and its relaxed version in \(\mathbb R^m\). These estimates can be computed in at most \(O(m^3)\) arithmetic operations unlike the estimates in papers mentioned above that require spectral information. The new and old estimates are equivalent in many practical cases. In cases when the new estimates are weaker, the numerical testing indicates that they approximate the original bounds in papers mentioned above quite well.
MSC:
| 65J10 | Numerical solutions to equations with linear operators |
| 65Fxx | Numerical linear algebra |
| 41A25 | Rate of convergence, degree of approximation |
References:
| [1] | Achieser, N.; Glasmann, I., Theorie der Linearen Operatoren im Hilbert Raum (1954), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0056.11101 |
| [2] | Aronszajn, N., Theory of reproducing kernels, Trans. Amer. Math. Soc., 68, 337-404 (1950) · Zbl 0037.20701 |
| [3] | Bauschke, H.; Borwein, J., On projection algorithms for solving convex feasibility problems, SIAM Rev., 38, 367-426 (1996) · Zbl 0865.47039 |
| [4] | Ben-Israel, A., On the geometry of subspaces in Euclidean \(n\)-spaces, SIAM J. Appl. Math., 15, 1184-1198 (1967) · Zbl 0178.03201 |
| [5] | Björck, A.; Golub, G., Numerical methods for computing angles between linear subspaces, Math. Comput., 27, 579-594 (1973) · Zbl 0282.65031 |
| [6] | Davis, P., Interpolation and Approximation (1975), Dover: Dover New York · Zbl 0329.41010 |
| [7] | Dax, A., The convergence of linear stationary iterative processes for solving singular unstructured systems of linear equations, SIAM Rev., 32, 611-635 (1990) · Zbl 0718.65021 |
| [8] | Deutsch, F., Rate of convergence of the method of alternating projections, (Internat. Ser. Numer. Math., vol. 72 (1984), Birkhäuser: Birkhäuser Basel), 96-107 · Zbl 0575.65049 |
| [9] | Deutsch, F., The method of alternating orthogonal projections, (Singh, S. P., Approximation Theory, Spline Functions and Applications (1992)), 105-121 · Zbl 0751.41031 |
| [10] | Deutsch, F., The angle between subspaces of a Hilbert space, (Singh, S., Approximation Theory, Wavelets and Applications (1995)), 107-130 · Zbl 0848.46010 |
| [11] | Deutsch, F.; Hundal, H., The rate of convergence for the method of alternating projections. II, J. Math. Anal. Appl., 205, 381-405 (1997) · Zbl 0890.65053 |
| [12] | Franchetti, C.; Light, W., On the von Neumann alternating algorithm in Hilbert space, J. Math. Anal. Appl., 114, 305-314 (1986) · Zbl 0617.65049 |
| [13] | Galántai, A., Projectors and Projection Methods (2004), Kluwer Academic · Zbl 1055.65043 |
| [14] | Halperin, I., The product of projection operators, Acta Sci. Math., 23, 96-99 (1962) · Zbl 0143.16102 |
| [15] | Hamaker, C.; Solmon, D., The angles between the null spaces of X rays, J. Math. Anal. Appl., 62, 1-23 (1978) · Zbl 0437.45025 |
| [16] | Householder, A., The Theory of Matrices in Numerical Analysis (1964), Blaisdell · Zbl 0161.12101 |
| [17] | Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, (Bulletin International de l’Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A. Sciences Mathématiques (1937)), 355-357 · Zbl 0017.31703 |
| [18] | Kayalar, S.; Weinert, H., Error bounds for the method of alternating projections, Math. Control Signals Systems, 1, 43-59 (1988) · Zbl 0673.65036 |
| [19] | Meany, R., A matrix inequality, SIAM J. Numer. Anal., 6, 104-107 (1969) · Zbl 0177.05201 |
| [20] | Metcalf, F., A Bessel-Schwarz inequality for Gramians and related bounds for determinants, Ann. Mat. Pura Appl., 68, 201-232 (1965) · Zbl 0168.27901 |
| [21] | Nelson, S.; Neumann, M., Generalizations of the projection method with application to SOR theory for Hermitian positive semidefinite linear systems, Numer. Math., 51, 123-141 (1987) · Zbl 0628.65024 |
| [22] | von Neumann, J., On rings of operators, reduction theory, Ann. of Math., 50, 401-485 (1950) · Zbl 0034.06102 |
| [23] | Pan, V.; Yu, Y.; Stewart, C., Algebraic and numerical techniques for the computation of matrix determinants, Comput. Math. Appl., 34, 43-70 (1997) · Zbl 0885.65052 |
| [24] | Smith, K.; Solmon, D.; Wagner, S., Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. Amer. Math. Soc., 83, 1227-1270 (1977) · Zbl 0521.65090 |
| [25] | Vasil’chenko, G.; Svetlanov, A., Proektsionnyj algoritm resheniya sistem linejnykh algebraicheskikh uravnenij bol’shoj razmernosti, Zh. Vychisl. Mat. Mat. Fiz., 20, 3-10 (1980), (in Russian) · Zbl 0446.65012 |
| [26] | Zassenhaus, H., Angles of inclination in correlation theory, Amer. Math. Monthly, 71, 218-219 (1964) |
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.
