Abstract
Many problems in applied mathematics can be abstracted into finding a common point of a finite collection of sets. If all the sets are closed and convex in a Hilbert space, the method of successive projections (MOSP) has been shown to converge to a solution point, i.e., a point in the intersection of the sets. These assumptions are however not suitable for a broad class of problems. In this paper, we generalize the MOSP to collections of approximately compact sets in metric spaces. We first define a sequence of successive projections (SOSP) in such a context and then proceed to establish conditions for the convergence of a SOSP to a solution point. Finally, we demonstrate an application of the method to digital signal restoration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Kaczmarz, S.,Angenäherte Auflösung von Systemen Linearer Gleichungen, Bulletin de l'Académie des Sciences de Pologne, Série A, Vol. 35, pp. 355–357, 1937.
Levitin, E. S., andPolyak, B. T.,Constrained Minimization Methods, USSR Computational Mathematics and Mathematical Physics, Vol. 6, pp. 1–50, 1966.
Lent, A., andTuy, H.,An Iterative Method for the Extrapolation of Band-Limited Functions, Journal of Mathematical Analysis and Applications, Vol. 83, pp. 554–565, 1981.
Glover, J. D., andSchweppe, F. C.,Control of Linear Dynamic Systems with Set-Constrained Disturbances, IEEE Transactions on Automatic Control, Vol. AC-16, pp. 411–423, 1971.
Youla, D. C., andWebb, H.,Image Restoration by the Method of Convex Projections, Part 1: Theory, IEEE Transactions on Medical Imaging, Vol. MI-1, pp. 81–94, 1982.
Trussell, H. J., andCivanlar, M. R.,The Feasible Solution in Signal Restoration, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-32, pp. 201–212, 1984.
Combettes, P. L., andTrussell, H. J.,Methods for Digital Restoration of Signals Degraded by a Stochastic Impulse Response, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-37, pp. 393–401, 1989.
Sezan, M. I., andStark, H.,Tomographic Image Reconstruction from Incomplete View Data by Convex Projections and Direct Fourier Inversion, IEEE Transactions on Medical Imaging, Vol. MI-3, pp. 91–98, 1984.
Carazo, J. M., andCarrascosa, J. L.,Information Recovery in Missing Angular Data Cases: An Approach by the Convex Projections Method in Three Dimensions, Journal of Microscopy, Vol. 145, pp. 23–43, 1987.
Gubin, L. G., Polyak, B. T., andRaik, E. V.,The Method of Projections for Finding the Common Point of Convex Sets, USSR Computational Mathematics and Mathematical Physics, Vol. 7, pp. 1–24, 1967.
Ottavy, N.,Strong Convergence of Projection-Like Methods in Hilbert Spaces, Journal of Optimization Theory and Applications, Vol. 56, pp. 433–461, 1988.
Kuratowski, K.,Topology, Vols. 1 and 2, Academic Press, New York, New York, 1966 and 1968.
Berge, C.,Espaces Topologiques, Fonctions Multivoques, 2nd Edition, Dunod, Paris, France, 1966.
Bourbaki, N.,Eléments de Mathématique—Topologie Générale, Hermann, Paris, France, 1974.
Efimov, N. V., andStechkin, S. B.,Approximative Compactness and Chebyshev Sets, Soviet Mathematics—Doklady, Vol. 2, pp. 1226–1228, 1961.
Singer, I.,Some Remarks on Approximative Compactness, Revue Roumaine de Mathématiques Pures et Appliquées, Vol. 9, pp. 167–177, 1964.
Bourbaki, N.,Eléments de Mathématique—Espaces Vectoriels Topologiques, Masson, Paris, France, 1981.
Brègman, L. M.,The Method of Successive Projection for Finding a Common Point of Convex Sets, Soviet Mathematics—Doklady, Vol. 6, pp. 688–692, 1965.
Stiles, W. J.,Closest Point Maps and Their Product, II, Nieuw Archief voor Wiskunde, Vol. 13, pp. 212–225, 1965.
Halperin, I.,The Product of Projection Operators, Acta Scientiarum Mathematicarum (Szeged), Vol. 23, pp. 96–99, 1962.
Von-Neumann, J.,On Rings of Operators. Reduction Theory, Annals of Mathematics, Vol. 50, pp. 401–485, 1949.
Jessen, B.,Two Theorems on Convex Point Sets, Matematisk Tidsskrift B, pp. 66–70, 1940 (in Danish).
Erdös, P.,Some Remarks on the Measurability of Certain Sets, Bulletin of the American Mathematical Society, Vol. 48, pp. 728–731, 1945.
Ostrowski, A. M.,Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York, New York, 1973.
Dieudonné, J. A.,Foundations of Modern Analysis, 2nd Edition, Academic Press, New York, New York, 1969.
Arioli, M., Laratta, A., andMenchi, O.,A Big-M Type Method for the Computation of Projections onto Polyhedrons, Journal of Optimization Theory and Applications, Vol. 47, pp. 17–34, 1985.
Wolfe, P.,Finding the Nearest Point in a Polytope, Mathematical Programming, Vol. 11, pp. 128–149, 1976.
Barr, R. O.,An Efficient Computational Procedure for a Generalized Quadratic Programming Problems, SIAM Journal on Control, Vol. 7, pp. 415–429, 1969.
Archetti, F., andSchoen, F.,A Survey on the Global Optimization Problem: General Theory and Computational Approaches, Annals of Operations Research, Vol. 1, pp. 87–110, 1984.
Rinnooy Kan, A. H., andTimmer, G. T.,Stochastic Global Optimization Methods, Part 1: Clustering Methods andPart 2: Multi Level Methods, Mathematical Programming, Vol. 39, pp. 27–56, 1987 and Vol. 39, pp. 57–78, 1987.
Andrews, H. C., andHunt, B. R.,Digital Image Restoration. Prentice-Hall, Englewood Cliffs, New Jersey, 1977.
Author information
Authors and Affiliations
Additional information
Communicated by E. Polak
Rights and permissions
About this article
Cite this article
Combettes, P.L., Trussell, H.J. Method of successive projections for finding a common point of sets in metric spaces. J Optim Theory Appl 67, 487–507 (1990). https://doi.org/10.1007/BF00939646
Issue Date:
DOI: https://doi.org/10.1007/BF00939646