Alternating Projection Methods Fundamentals of Algorithms Editor-in-Chief: Nicholas J. Higham, University of Manchester The SIAM series on Fundamentals of Algorithms is a collection of short user-oriented books on state-of- the-art numerical methods. Written by experts, the books provide readers with sufficient knowledge to choose an appropriate method for an application and to understand the method’s strengths and limita- tions. The books cover a range of topics drawn from numerical analysis and scientific computing. The intended audiences are researchers and practitioners using the methods and upper level undergraduates in mathematics, engineering, and computational science. Books in this series not only provide the mathematical background for a method or class of methods used in solving a specific problem but also explain how the method can be developed into an algorithm and translated into software. The books describe the range of applicability of a method and give guidance on troubleshooting solvers and interpreting results. The theory is presented at a level accessible to the practitioner. MATLAB® software is the preferred language for codes presented since it can be used across a wide variety of platforms and is an excellent environment for prototyping, testing, and problem solving. The series is intended to provide guides to numerical algorithms that are readily accessible, contain practical advice not easily found elsewhere, and include understandable codes that implement the algorithms. Editorial Board Uri M. Ascher Randall J. LeVeque University of British Columbia University of Washington Howard Elman Beatrice Meini University of Maryland University of Pisa Mark Embree Danny Sorensen Rice University Rice University C. T. Kelley Jared Tanner North Carolina State University University of Edinburgh Series Volumes Escalante, R. and Raydan, M., Alternating Projection Methods Hansen, P. C., Discrete Inverse Problems: Insight and Algorithms Modersitzki, J., FAIR: Flexible Algorithms for Image Registration Chan, R. H.-F. and Jin, X.-Q., An Introduction to Iterative Toeplitz Solvers Eldén, L., Matrix Methods in Data Mining and Pattern Recognition Hansen, P. C., Nagy, J. G., and O’Leary, D. P., Deblurring Images: Matrices, Spectra, and Filtering Davis, T. A., Direct Methods for Sparse Linear Systems Kelley, C. T., Solving Nonlinear Equations with Newton’s Method René Escalante Marcos Raydan Universidad Simón Bolívar Caracas, Venezuela Alternating Projection Methods Society for Industrial and Applied Mathematics Philadelphia Copyright © 2011 by the Society for Industrial and Applied Mathematics. 10 9 8 7 6 5 4 3 2 1 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 Market Street, 6th Floor, Philadelphia, PA 19104-2688 USA. Trademarked names may be used in this book without the inclusion of a trademark symbol. These names are used in an editorial context only; no infringement of trademark is intended. MATLAB is a registered trademark of The MathWorks, Inc. For MATLAB product information, please contact The MathWorks, Inc., 3 Apple Hill Drive, Natick, MA 01760-2098 USA, 508-647-7000, Fax: 508-647-7001, [email protected], www.mathworks.com. Library of Congress Cataloging-in-Publication Data Escalante, René. Alternating projection methods / René Escalante, Marcos Raydan. p. cm. -- (Fundamentals of algorithms) Includes bibliographical references and indexes. ISBN 978-1-611971-93-4 (pbk.) 1. Projection. 2. Algorithms. 3. Convex sets. I. Raydan, Marcos. II. Society for Industrial and Applied Mathematics. III. Title. QA521.E83 2011 516’.08--dc23 2011021076 is a registered trademark. Contents Preface vii 1 Introduction 1 1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Overview on Spaces 5 2.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Convex Sets and Cones . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Normed Linear Spaces . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Inner Product and Hilbert Spaces . . . . . . . . . . . . . . . . . 10 2.6 Comments and Additional References . . . . . . . . . . . . . . . 16 2.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 The MAP on Subspaces 19 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 The von Neumann Theorem . . . . . . . . . . . . . . . . . . . . 20 3.3 The Extension of Halperin . . . . . . . . . . . . . . . . . . . . . 24 3.4 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.1 Angle between Subspaces . . . . . . . . . . . . . . . 27 3.4.2 Rate of Convergence of MAP . . . . . . . . . . . . . 29 3.5 Acceleration Techniques . . . . . . . . . . . . . . . . . . . . . . 33 3.6 Comments and Additional References . . . . . . . . . . . . . . . 34 3.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 Row-Action Methods 39 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Some Row-Action Methods . . . . . . . . . . . . . . . . . . . . . 40 4.2.1 The Method of Kaczmarz . . . . . . . . . . . . . . . 40 4.2.2 The Relaxation Method of Agmon, Motzkin, and Schoenberg (MAMS) . . . . . . . . . . . . . . . . . . 41 4.2.3 Hildreth’s Method . . . . . . . . . . . . . . . . . . . 42 4.2.4 Successive Orthogonal Projections . . . . . . . . . . 44 4.2.5 Cimmino’s Method . . . . . . . . . . . . . . . . . . . 44 v vi Contents 4.2.6 Bregman’s Generalization of the Method of Successive Projections . . . . . . . . . . . . . . . . . 45 4.3 Acceleration Schemes . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 Convex Feasibility Problems . . . . . . . . . . . . . . . . . . . . 47 4.5 Comments and Additional References . . . . . . . . . . . . . . . 51 4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 Projecting onto Convex Sets 55 5.1 Dykstra’s Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . 55 5.2 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.3 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . 68 5.4 Comments and Additional References . . . . . . . . . . . . . . . 72 5.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6 Applications of MAP for Matrix Problems 75 6.1 Solving Constrained Least-Squares Matrix Problems . . . . . . . 75 6.1.1 Description of the General Problem . . . . . . . . . 75 6.1.2 The Feasible Region . . . . . . . . . . . . . . . . . . 76 6.1.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . 77 6.1.4 An Improved Version of the Algorithm . . . . . . . . 80 6.1.5 Numerical Experiments . . . . . . . . . . . . . . . . 83 6.1.6 Constrained Least-Squares Rectangular Matrix Problems . . . . . . . . . . . . . . . . . . . . . . . . 86 6.1.7 Improved Implementation of the Projection Algorithm onto the εpd Set . . . . . . . . . . . . . . 89 6.2 Solving Matrix Model Updating Problems . . . . . . . . . . . . 92 6.2.1 Description of the Problem . . . . . . . . . . . . . . 93 6.2.2 Alternating Projection Approach for MMUP . . . . 94 6.2.3 Numerical Experiments . . . . . . . . . . . . . . . . 98 6.3 Comments and Additional References . . . . . . . . . . . . . . . 100 6.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Bibliography 103 Author Index 121 Subject Index 125 Preface Due to their utility and broad applicability in many areas of applied mathematics and physical science (e.g., computerized tomography, Navier–Stokesequations, pat- tern recognition, and image restoration, among others) the Method of Alternating Projection (MAP) continues to receive significant attention. The main purpose of this book is to describe and analyze all available algorithms in the MAP family for solving the general problem of finding a point in the intersection of several given sets that belong to a Hilbert space. Different types of algorithms and different ap- plications are studied for the following types of sets: subspaces, linear varieties, and general convex sets. The second goal of this book is to unify all these algorithms into a common framework. In recent decades, many papers have appeared dealing with the MAP family and especially its wide applicability. Four important books have also appeared that dedicate one or more chapters to the topic of MAP: The book by Censor and Zenios [65], Parallel Optimization, which is mainly concerned with “row-action” methods that are suitable for parallel architectures; the book by Deutsch [95], Best Approx- imation in Inner Product Spaces, that dedicates one chapter to this topic, paying significant attention to Dykstra’s algorithm for finite-dimensional inner product spaces; and the book by Stark and Yang [233] Vector Space Projections: A Numeri- cal Approach to Signal and Image Processing, Neural Nets, and Optics and the book by Byrne [49] Applied Iterative Methods, both which describe important problems in various areas of science and engineering that can be solved using MAP. Nevertheless, much of the inspiration that motivated us to write this book comes from a fifth publication on a related topic, the classical book by Luenberger [190], Optimization by Vector Space Methods, which, according to its author has as a primary objective “to demonstrate that a rather large segment of the field of optimization can be effectively unified by a few geometric principles of linear vector space theory.” We share this thought. For this reason, the support pillar of the approach taken in this book is the geometry associated with Hilbert spaces. This book grew up from our personal notes while teaching the topic of MAP in several graduate courses, and also advanced undergraduate courses, in different universities: Universidad Central de Venezuela (Caracas, Venezuela) and Universi- dad Simo´n Bol´ıvar (Caracas, Venezuela) for the last 12 years, and at Universidad Nacional del Sur (Bah´ıa Blanca, Argentina) once in 1999. Therefore, it evolved as a textbook for advanced undergraduate or first year graduate students. However, since the book is comprehensive, it can also be used as a tutorial or a reference by vii viii Preface those researchers who need to solve alternating projection problems in their work. The required background is some familiarity with matrix algebra and numerical analysis. Throughout the book we have used a standard notation as similar as possible to that found in the previous books mentioned above. In Chapter 1 we present a list of some applications of MAP to problems of practical interest in science and engineering. In Chapter 2 we present a review of the vector spaces used in the rest of the book, including a list of basic concepts and results in functional analysis. From that point on, the chapters are introduced following a chronological order. Chapter 3 introduces MAP on subspaces. Here we follow the classic approach on this topic, beginning with a theoretical framework as it was originally developed by von Neumann [209] and Halperin [148], and followed by a treatment on the rate of convergence of MAP, and some acceleration techniques. In Chapter 4 we study the row-action methods, which are specially designed for linear varieties. We in- troduce also a recent scheme of acceleration, and we close with a discussion on the more general convex feasibility problem. In Chapter 5 we show the very important Dykstra’s theorem, which is a skillful extension of MAP to the convex case, and we discuss its rate of convergence in the polyhedral case and also the delicate issue of stopping the convergence process for Dykstra’s method. In Chapter 6 we de- scribe two distinct applications of MAP whose variables are matrices. The first is related to a least-squares approach for solving some special problems in statistics and mathematical economy. The second is related to the model updating problem that appears in the design of vibration structural dynamic systems. We wanted to keep the book as short as possible without sacrificing the clarity of the exposition. Thus, at the end of every chapter, we have included some information under the heading Comments and Additional References to include the historical perspective and to list in a condensed form the more advanced topics and the ongoing lines of research. At the end of each chapter we also offer a variety of problems to be solved. Some of them are closely related to the theoretical development of the alternating projection field, and others are related to the practical aspects of the described algorithms. Acknowledgments Many people have contributed to this book, both indirectly through discussions and directly through comments on earlier versions of the manuscript. In particular we would like to thank the following colleagues: Ernesto Birgin, Jonathan Borwein, Claude Brezinski, Yair Censor, Debora Cores, Biswa Datta, JohnDennis, Lucio Dos Santos, Bernardo Feijoo, Ubaldo Garc´ıa-Palomares, Mar´ıa Gonz´alez-Lima, Tom Hayden, Nick Higham, Alfredo Iusem, William La Cruz, Cristina Maciel, Mario Mart´ınez, Hugo Scolnik, Richard Tapia, and Pablo Tarazaga. We are also very thankful to the many students whose comments andquestions ledto correctionsand clarifications. Maricarmen Andrade, Reinaldo Astudillo, Lenys Bello, Flavia Buffo, Carlos Contreras, Braulio De Abreu, Gabriela Eberle, Robert Espitia, Luis M. Hern´andez-Ramos, Mar´ıa Mendoza, Marlliny Monsalve, Joali Moreno, Susana Orofino, Ram´on Porras, Adriana Verdiell, Marta Vidal, and Melina Wijaya were Preface ix particularly helpful in this respect. We also express our gratitude to the CESMa Center and the Scientific Computing and Statistics Department at Universidad Sim´on Bol´ıvar and the CCCT Center at Universidad Central de Venezuela for their strong support to our research efforts over the years. Finally, we wish to thank the SIAM publications staff, in particular Lisa Briggeman, Elizabeth Greenspan, and Gina Rinelli. Ren´e Escalante (USB) and Marcos Raydan (USB, UCV) Caracas, 2011 Chapter 1 Introduction An important problem that appears quite frequently in applied mathematics and scientific computing is the following: Find a point in the intersection of a finite H collection of closed and convex sets, contained in a given Hilbert space . Another interesting and related problem is to find the point in the intersection of a finite collection of closed and convex sets which is the closest to a given point in the H space . H Depending on the characteristics of the space , and also on the character- istics of the involved sets, different algorithms need to be used. Several of these possibilities will be considered in this book. For example, if the sets are subspaces of the given space, then the algorithms that are capable of solving those problems are variants of the Method of Alternating Projections (MAP), which are simpler than the algorithms, variants of the so-called Dykstra’s algorithm, developed for solving the problems in which the sets are closed and convex but not necessarily subspaces. In both cases, there are variants that take advantage of the intrinsic structure of the problem, or variants that take advantage of the possible computer architecture to be used. In this setting, specialized algorithms have also been de- signed for solving specific problems with special features. We will also discuss some of these special problems. 1.1 Applications We present a list of important problems in various areas of mathematics and also a list of real applications for which alternating projection methods have proved to be useful, and we mention some of the many authors who have contributed in different ways with the development of this topic. Several MAP algorithms have been useful for solving important problems that appear in the following areas of mathematics and the physical sciences: • Solving systems of linear equations, Kaczmarz [180], Cimmino [70], Tanabe [235], McCormick [198], Bramley and Sameh [34], Eggermont, Herman, and Lent [109], Herman, Hurwitz, and Lent [156], Herman, Lent, and Lutz [157], 1