The method of alternating projections and the method of subspace corrections in Hilbert space

A new identity is given in this paper for estimating the norm of the product of nonexpansive operators in Hilbert space. This identity can be applied for the design and analysis of the method of alternating projections and the method of subspace corrections. The method of alternating projections is an iterative algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces by alternatively computing the best approximations from the individual subspaces which make up the intersection. The method of subspace corrections is an iterative algorithm for finding the solution of a linear equation in a Hilbert space by approximately solving equations restricted on a number of closed subspaces which make up the entire space. The new identity given in the paper provides a sharpest possible estimate for the rate of convergence of these algorithms. It is also proved in the paper that the method of alternating projections is essentially equivalent to the method of subspace corrections. Some simple examples of multigrid and domain decomposition methods are given to illustrate the application of the new identity.

     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

Randomized Kaczmarz solver for noisy linear systems

The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system Ax≈b+r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.     

On the convergence of Han's method for convex programming with quadratic objective

We present an iterative method for minimizing strictly convex quadratic functions over the intersection of a finite number of convex sets. The method consists in computing projections onto the individual sets simultaneously and the new iterate is a convex combination of those projections. We give convergence proofs even for the inconsistent case, i.e. when the intersection of the sets is empty.Work of this author was partially supported by CNPq under grant No. 301280/86-MA.     

Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization

Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the Expectation Maximization Maximum Likelihood (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.     

Optimal Non-Linear Models for Sparsity and Sampling

Given a set of vectors (the data) in a Hilbert space ?, we prove the existence of an optimal collection of subspaces minimizing the sum of the square of the distances between each vector and its closest subspace in the collection. This collection of subspaces gives the best sparse representation for the given data, in a sense defined in the paper, and provides an optimal model for sampling in union of subspaces. The results are proved in a general setting and then applied to the case of low dimensional subspaces of ? ^N and to infinite dimensional shift-invariant spaces in L ²(? ^d ). We also present an iterative search algorithm for finding the solution subspaces. These results are tightly connected to the new emergent theories of compressed sensing and dictionary design, signal models for signals with finite rate of innovation, and the subspace segmentation problem.     

A Randomized Kaczmarz Algorithm with Exponential Convergence

The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling. T. Strohmer was supported by NSF DMS grant 0511461. R. Vershynin was supported by the Alfred P. Sloan Foundation and by NSF DMS grant 0401032.     

Local Linear Convergence for Alternating and Averaged Nonconvex Projections

The idea of a finite collection of closed sets having “linearly regular intersection” at a point is crucial in variational analysis. This central theoretical condition also has striking algorithmic consequences: in the case of two sets, one of which satisfies a further regularity condition (convexity or smoothness, for example), we prove that von Neumann’s method of “alternating projections” converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having linearly regular intersection at some point, the method of “averaged projections” converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly. Research of A.S. Lewis supported in part by National Science Foundation Grant DMS-0504032. Research of D.R. Luke supported in part by National Science Foundation Grant DMS-0712796.     

Strong Convergence Theorems for Quasi-Nonexpansive Mappings and Uniformly L-Lipschitzian Asymptotically Pseudo-Contractive Mappings in Banach Spaces

A new 𝒮-generated Ishikawa iteration with errors is proposed for a pair of quasi-nonexpansive mapping and uniformly L-Lipschitzian asymptotically pseudo-contractive mapping in real Banach spaces. We show that the proposed iterative scheme converges strongly to a common solution of quasi-nonexpansive mapping and uniformly L-Lipschitzian asymptotically pseudo-contractive mapping in real Banach spaces. A comparison table is prepared using a numeric example which shows that the proposed iterative algorithm is faster than some known iterative algorithms.     

Two-sided Grassmann–Rayleigh quotient iteration

The two-sided Rayleigh quotient iteration proposed by Ostrowski computes a pair of corresponding left–right eigenvectors of a matrix C. We propose a Grassmannian version of this iteration, i.e., its iterates are pairs of p-dimensional subspaces instead of one-dimensional subspaces in the classical case. The new iteration generically converges locally cubically to the pairs of left–right p-dimensional invariant subspaces of C. Moreover, Grassmannian versions of the Rayleigh quotient iteration are given for the generalized Hermitian eigenproblem, the Hamiltonian eigenproblem and the skew-Hamiltonian eigenproblem.     

Hybrid Methods for Approximating Hankel Matrix

Hybrid methods for minimizing least distance functions with Hankel positive semi-definite matrix constraints are considered. Our approach is based on (i) a projection algorithm which converges globally but slowly; and (ii) the Newton method which is faster. Hybrid methods that attempt to combine the best features of both methods are then considered. Comparative numerical results are reported.     

A new iterative method for solving split feasibility problem

In this paper, we construct a new iterative algorithm and show that the newly introduced iterative algorithm converges faster than a number of existing iterative algorithms for contractive-like mappings. We present a numerical example followed by graphs to validate our claim. We prove strong and weak convergence results for approximating fixed points of generalized $\alpha$-nonexpansive mappings. Again we reconfirm our results by an example and table. Further, we utilize our proposed algorithm to solve split feasibility problem.     

Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994     

Comparison of the EM algorithm and alternatives

The Expectation-Maximization (EM) algorithm is widely used also in industry for parameter estimation within a Maximum Likelihood (ML) framework in case of missing data. It is well-known that EM shows good convergence in several cases of practical interest. To the best of our knowledge, results showing under which conditions EM converges fast are only available for specific cases. In this paper, we analyze the connection of the EM algorithm to other ascent methods as well as the convergence rates of the EM algorithm in general including also nonlinear models and apply this to the PMHT model. We compare the EM with other known iterative schemes such as gradient and Newton-type methods. It is shown that EM reaches Newton-convergence in case of well-separated objects and a Newton-EM combination turns out to be robust and efficient even in cases of closely-spaced targets.     

MM Algorithms for Variance Components Models

Variance components estimation and mixed model analysis are central themes in statistics with applications in numerous scientific disciplines. Despite the best efforts of generations of statisticians and numerical analysts, maximum likelihood estimation (MLE) and restricted MLE of variance component models remain numerically challenging. Building on the minorization–maximization (MM) principle, this article presents a novel iterative algorithm for variance components estimation. Our MM algorithm is trivial to implement and competitive on large data problems. The algorithm readily extends to more complicated problems such as linear mixed models, multivariate response models possibly with missing data, maximum a posteriori estimation, and penalized estimation. We establish the global convergence of the MM algorithm to a Karush–Kuhn–Tucker point and demonstrate, both numerically and theoretically, that it converges faster than the classical EM algorithm when the number of variance components is greater than two and all covariance matrices are positive definite. Supplementary materials for this article are available online.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.     

An O(n) Algorithm for Projecting a Vector on the Intersection of a Hyperplane and a Box in Rn

We consider the problem of projecting a vector on the intersection of a hyperplane and a box in Rⁿ. This paper extends a previous result of Maculan, Minoux, and Plateau (Ref. 1) concerning the projection of a vector on the intersection of a hyperplane and Rⁿ ₊. We present an O(n) time algorithm based on the linear-time median-finding algorithm. This algorithm determines the median of the components of the vector to be projected. Computational results are also presented in order to evaluate the algorithm and its time complexity. We consider two sets of instances which are randomly generated for any given n. The algorithm was successful in solving all the instances in a reasonable time.     

Gearhart–Koshy acceleration for affine subspaces

The method of cyclic projections finds nearest points in the intersection of finitely many affine subspaces. To accelerate convergence, Gearhart & Koshy proposed a modification which, in each iteration, performs an exact line search based on minimising the distance to the solution. When the subspaces are linear, the procedure can be made explicit using feasibility of the zero vector. This work studies an alternative approach which does not rely on this fact, thus providing an efficient implementation in the affine setting.     

加权再生核空间中信号的平均采样与重构

主要讨论L_v~p的加权再生核子空间中信号的平均采样与重构.首先,针对两种平均采样泛函建立了采样稳定性;其次,基于概率测度给出一个一般的迭代算法,将迭代逼近投影算法和迭代标架算法统一起来;最后,针对被白噪声污染的平均样本给出了信号重构的渐进点态误差估计.     

Restricted Normal Cones and the Method of Alternating Projections: Applications

The method of alternating projections (MAP) is a common method for solving feasibility problems. While employed traditionally to subspaces or to convex sets, little was known about the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick derived local linear convergence results provided that a condition involving normal cones holds and at least one of the sets is superregular (a property less restrictive than convexity). However, their results failed to capture very simple classical convex instances such as two lines in a three-dimensional space. In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only any two linear subspaces but also any two closed convex sets whose relative interiors meet are covered. We also allow for sets that are more structured such as unions of convex sets. The key tool required is the restricted normal cone, which is a generalization of the classical Mordukhovich normal cone. Numerous examples are provided to illustrate the theory.