Accelerating the convergence of the method of alternating projections

The powerful von Neumann-Halperin method of alternating projections (MAP) is an algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces. It achieves this by reducing the problem to an iterative scheme which involves only computing best approximations from the individual subspaces which make up the intersection. The main practical drawback of this algorithm, at least for some applications, is that the method is slowly convergent. In this paper, we consider a general class of iterative methods which includes the MAP as a special case. For such methods, we study an ``accelerated' version of this algorithm that was considered earlier by Gubin, Polyak, and Raik (1967) and by Gearhart and Koshy (1989). We show that the accelerated algorithm converges faster than the MAP in the case of two subspaces, but is, in general, not faster than the MAP for more than two subspaces! However, for a ``symmetric' version of the MAP, the accelerated algorithm always converges faster for any number of subspaces. Our proof seems to require the use of the Spectral Theorem for selfadjoint mappings.

     

A note on the finite convergence of alternating projections

We establish sufficient conditions for finite convergence of the alternating projections method for two non-intersecting and potentially nonconvex sets. Our results are based on a generalization of the concept of intrinsic transversality, which until now has been restricted to sets with nonempty intersection. In the special case of a polyhedron and closed half space, our sufficient conditions define the minimum distance between the two sets that is required for alternating projections to converge in a single iteration.     

An alternating projections method for certain linear problems in a Hilbert space

Recent extensions of von Neumann's alternating projection methodpermit the computation of proximity projections onto certainconvex sets. This paper exploits this fact in constructing aglobally convergent method for minimizing linear functions overa convex set in a Hilbert space. In particular, we solve theeducational testing problem and an inverse eigenvalue problem,two difficult problems involving positive semidefiniteness constraints.     

Paley-Wiener subspace of vectors in a Hilbert space with applications to integral transforms

The goal of this article is to introduce an analogue of the Paley-Wiener space of bandlimited functions, PWω, in Hilbert spaces and then apply the general result to more specific examples. Guided by the role that the differentiation operator plays in some of the characterizations of the Paley-Wiener space, we construct a space of vectors using a self-adjoint operator D in a Hilbert space H, and denote this space by PWω(D). The article can be virtually divided into two parts. In the first part we show that the space PWω(D) has similar properties to those of the space PWω, including an analogue of the Bernstein inequality and the Riesz interpolation formula. We also develop a new characterization of the abstract Paley-Wiener space in terms of solutions of Cauchy problems associated with abstract Schrödinger equations. Finally, we prove two sampling theorems for vectors in PWω(D), one of which uses the notion of Hilbert frames and the other is based on the notion of variational splines in H. In the second part of the paper we apply our abstract results to integral transforms associated with singular Sturm-Liouville problems. In particular we obtain two new sampling formulas related to one-dimensional Schrödinger operators with bounded potential.     

A note on the star order in Hilbert spaces

We study the star order on the algebra L(?) of bounded operators on a Hilbert space ?. We present a new interpretation of this order which allows to generalize to this setting many known results for matrices: functional calculus, semi-lattice properties, shorted operators and orthogonal decompositions. We also show several properties for general Hilbert spaces regarding the star order and its relationship with the functional calculus and the polar decomposition, which were unknown even in the finite-dimensional setting. We also study the existence of strong limits of star-monotone sequences and nets.     

Convergence of minimum norm elements of projections and intersections of nested affine spaces in Hilbert space

We consider a Hilbert space, an orthogonal projection onto a closed subspace and a sequence of downwardly directed affine spaces. We give sufficient conditions for the projection of the intersection of the affine spaces into the closed subspace to be equal to the intersection of their projections. Under a closure assumption, one such (necessary and) sufficient condition is that summation and intersection commute between the orthogonal complement of the closed subspace, and the subspaces corresponding to the affine spaces. Another sufficient condition is that the cosines of the angles between the orthogonal complement of the closed subspace, and the subspaces corresponding to the affine spaces, be bounded away from one. Our results are then applied to a general infinite horizon, positive semi-definite, linear quadratic mathematical programming problem. Specifically, under suitable conditions, we show that optimal solutions exist and, modulo those feasible solutions with zero objective value, they are limits of optimal solutions to finite-dimensional truncations of the original problem.     

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm.     

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.     

Global and uniform convergence of subspace correction methods for some convex optimization problems

This paper gives some global and uniform convergence estimates for a class of subspace correction (based on space decomposition) iterative methods applied to some unconstrained convex optimization problems. Some multigrid and domain decomposition methods are also discussed as special examples for solving some nonlinear elliptic boundary value problems.

     

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

     

The alternating algorithm in a uniformly convex and uniformly smooth Banach space

Let X   be a uniformly convex and uniformly smooth Banach space. Assume that the _Mi$M_i$, i=1,…,r$i=1,\dots ,r$, are closed linear subspaces of X  , _PMi$P_{M_i}$ is the best approximation operator to the linear subspace _Mi$M_i$, and M:=_M1+?+_Mr$M:=M_1+?+M_r$. We prove that if M is closed, then the alternating algorithm given by repeated iterations of

(I−_PMr)(I−_PMr−1)?(I−_PM1)$(I-P_{M_r})(I-P_{M_{r-1}})?(I-P_{M_1})$

applied to any x∈X$x\in X$ converges to x−_PMx$x-P_{M}x$, where _PM$P_M$ is the best approximation operator to the linear subspace M  . This result, in the case r=2$r=2$, was proven in Deutsch [4].     

The many proofs of an identity on the norm of oblique projections

Given an oblique projector P on a Hilbert space, i.e., an operator satisfying P ²=P, which is neither null nor the identity, it holds that ||P|| = ||I –P||. This useful equality, while not widely-known, has been proven repeatedly in the literature. Many published proofs are reviewed, and simpler ones are presented.     

Reflection symmetry and symmetrizability of Hilbert space operators

A general factorization theorem for symmetrizable operators relating their spectra to spectra of selfadjoint operators induced by minimal factorizations is established. Its modified version essentially improves and completes a theorem of Jorgensen, which concerns diagonalizing operators with reflection symmetry.

     

Bicircular projections and characterization of Hilbert spaces

We prove that every JB* triple with rank one bicircular projection is a direct sum of two ideals, one of which is isometrically isomorphic to a Hilbert space.

     

The play operator on the rectifiable curves in a Hilbert space

The vector play operator is the solution operator of a class of evolution variational inequalities arising in continuum mechanics. For regular data, the existence of solutions is easily obtained from general results on maximal monotone operators. If the datum is a continuous function of bounded variation, then the existence of a weak solution is usually proved by means of a time discretization procedure. In this paper we give a short proof of the existence of the play operator on rectifiable curves making use of basic facts of measure theory. We also drop the separability assumptions usually made by other authors. Copyright © 2007 John Wiley & Sons, Ltd.     

The method of cyclic projections for closed convex sets in a Hilbert space under the presence of computational errors

Numerical Algorithms - In this paper, we study the method of cyclic projections for inconsistent convex feasibility problems in a Hilbert space under the presence of computational errors. We show...     

Applications of a space decomposition method to linear and nonlinear elliptic problems

This work presents some space decomposition algorithms for a convex minimization problem. The algorithms has linear rate of convergence and the rate of convergence depends only on four constants. The space decomposition could be a multigrid or domain decomposition method. We explain the detailed procedure to implement our algorithms for a two-level overlapping domain decomposition method and estimate the needed constants. Numerical tests are reported for linear as well as nonlinear elliptic problems. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 717–737, 1998     

Conformal mapping by the method of alternating projections

Summary The functional analytic principle of alternating projections is used to construct an iterative method for numerical conformal mapping of the unit disc onto regions with smooth boundaries. The result is a simple method which requires in each iterative step only two complex Fourier transforms. Local convergence can be proved using a theorem of Ostrowski. Convergence is linear. The asymptotic convergence factor is equal to the spectral radius of a certain operator. A version with overrelaxation as well as a discretized version are discussed along the same lines. For regions which are close to the unit disc convergence is fast. For some familiar regions the convergence factors can be calculated explicitly. Finally, the method is compared with Theodorsen's.Dedicated to the memory of Peter Henrici