Sharp convergence rates for averaged nonexpansive maps

We establish sharp estimates for the convergence rate of the Kranosel’ski?–Mann fixed point iteration in general normed spaces, and we use them to show that the optimal constant of asymptotic regularity is exactly \(1/\sqrt \pi \). To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. We show that these bounds are tight by building a nonexpansive map T: [0, 1]^N → [0, 1]^N that attains them with equality, settling a conjecture by Baillon and Bruck. The recursive bounds are in turn reinterpreted as absorption probabilities for an underlying Markov chain which is used to establish the tightness of the constant \(1/\sqrt \pi \).     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

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.

     

On improving the convergence rates of extrapolated alternating direction implicit schemes

This paper describes how a further improvement on the convergence rates of Extrapolated Alternating Direction Implicit schemes is possible. In the case of the first boundary value problem for Laplace's equation over the unit square an analysis is presented which can be extended to cover more general problems. In addition numerical examples which prove the validity of the analysis are given.     

Optimal rates of convergence for estimating Toeplitz covariance matrices

Toeplitz covariance matrices are used in the analysis of stationary stochastic processes and a wide range of applications including radar imaging, target detection, speech recognition, and communications systems. In this paper, we consider optimal estimation of large Toeplitz covariance matrices and establish the minimax rate of convergence for two commonly used parameter spaces under the spectral norm. The properties of the tapering and banding estimators are studied in detail and are used to obtain the minimax upper bound. The results also reveal a fundamental difference between the tapering and banding estimators over certain parameter spaces. The minimax lower bound is derived through a novel construction of a more informative experiment for which the minimax lower bound is obtained through an equivalent Gaussian scale model and through a careful selection of a finite collection of least favorable parameters. In addition, optimal rate of convergence for estimating the inverse of a Toeplitz covariance matrix is also established.     

On the convergence of von Neumann''s alternating projection algorithm for two sets

We give several unifying results, interpretations, and examples regarding the convergence of the von Neumann alternating projection algorithm for two arbitrary closed convex nonempty subsets of a Hilbert space. Our research is formulated within the framework of Fejér monotonicity, convex and set-valued analysis. We also discuss the case of finitely many sets.     

On the convergence of von Neumann's alternating projection algorithm for two sets

We give several unifying results, interpretations, and examples regarding the convergence of the von Neumann alternating projection algorithm for two arbitrary closed convex nonempty subsets of a Hilbert space. Our research is formulated within the framework of Fejér monotonicity, convex and set-valued analysis. We also discuss the case of finitely many sets.     

Degree of convergence of modified averaged iterations for fixed points problems and operator equations

Let H be a real Hilbert space. We propose a modification for averaged mappings to approximate the unique fixed point of a mapping T:H→H such that T is boundedly Lipschitzian and −T is monotone. We not only prove strong convergence theorems, but also determine the degree of convergence. Using this result, an iteration process is given for finding the unique solution of the equation Ax=f, where A:H→H is strongly monotone and boundedly Lipschitzian.     

Optimal global rates of convergence ofM-estimates for multivariate nonparametric regression

Consider the nonparametric regression modelY=go(T)+u, whereY is real-valued,u is a random error,T is a randomd-vector of explanatory variables ranging over a nondegenerated-dimensional compact setC, andgo(·) is the unknown smooth regression function, which ism (0) times continuously differentiable and itsmth partial derivatives satisfy the Hölder condition with exponent(0,1], wherei ₁, ...,i _d are nonnegative integers satisfying _k ^=1/d i _k =m. The piecewise polynomial estimator ofgo based onM-estimates is considered. It is proved that the rate of convergence of the underlying estimator is under certain regular conditions, which is the optimal global rate of convergence of least square estimates for nonparametric regression studied in [10–11].This work is partly supported by the National Natural Science Foundation of China.     

A method for the improvement of the convergence rates of stationary iterative schemes for the solution of complex linear systems

In this paper a number of theorems and lemmas are stated and proved, which can be used as criteria for the evaluation of some unknown eigenvalues of the coefficient matrix of a complex linear system in connection with a consistent with the linear system stationary iterative scheme. The aforementioned eigenvalues can be used together with or without the iterative approximations to improve the convergence rates of the iterative scheme. Numerical examples show the validity of the theory developed.     

On convergence rates for the Iteratively regularized Gauss-Newton method

Received on 3 February 1995. Revised on 20 April 1996. In this paper we prove that the iteratively regularized Gauss-Newtonmethod is a locally convergent method for solving nonlinearill-posed problems, provided the nonlinear operator satisfiesa certain smoothness condition. For perturbed data we proposea priori and a posteriori stopping niles that guarantee convergenceof the iterates, if the noise level goes to zero. Under appropriatecloseness and smoothness conditions on the exact solution weobtain the same convergence rates as for linear ill-posed problems.     

On rates of convergence in functional linear regression

This paper investigates the rate of convergence of estimating the regression weight function in a functional linear regression model. It is assumed that the predictor as well as the weight function are smooth and periodic in the sense that the derivatives are equal at the boundary points. Assuming that the functional data are observed at discrete points with measurement error, the complex Fourier basis is adopted in estimating the true data and the regression weight function based on the penalized least-squares criterion. The rate of convergence is then derived for both estimators. A simulation study is also provided to illustrate the numerical performance of our approach, and to make a comparison with the principal component regression approach.     

Optimal convergence rates for the combined methods of different finite element methods

Coupling techniques are essential to combining different numerical methods together for the purpose of solving an elliptic boundary value problem. By means of nonconforming constraints, the combinations of various Lagrange finite element methods often cause reduced rates of convergence. In this article, we present a method using penalty plus hybrid technique to match different finite element methods such that the optimal convergence rates in the ‖ · ‖_h and zero norms of errors of the solution can always be achieved. Also, such a coupling technique will lead to an optimal asymptotic condition number for the associated coefficient matrix. Moreover, this study can easily be extended for combining the finite difference method with the finite element method to also yield the optimal rate of convergence.     

On the convergence condition for the Schwarz alternating method for the two-dimensional Laplace equation

The Schwarz alternating method makes it possible to construct a solution of the Dirichlet problem for the two-dimensional Laplace equation in a finite union of overlapping domains, provided that this problem has a solution in each domain. The existing proof of the method convergence and estimation of the convergence rate use the condition that the normals to the boundaries of the domains at the intersection points are different. In the paper, it is proved that this constraint can be removed for domains with Hölder continuous normals. Removing the constraint does not affect the rate of convergence.

     

On the linear convergence of the circumcentered-reflection method

In order to accelerate the Douglas–Rachford method we recently developed the circumcentered-reflection method, which provides the closest iterate to the solution among all points relying on successive reflections, for the best approximation problem related to two affine subspaces. We now prove that this is still the case when considering a family of finitely many affine subspaces. This property yields linear convergence and incites embedding of circumcenters within classical reflection and projection based methods for more general feasibility problems.     

On the convergence of the modified overrelaxation method

The modified overrelaxation (MSOR) method is applied to a linear system Ax=b, where A has property A. We get bounds for the spectral radius of the iteration matrix of this method, and we achieve convergence conditions for the MSOR method when A is strictly diagonally dominant. We extend our conclusions to another kind of matrices—H,L,M or Stieltjes. In the last section we use the vectorial norms, getting convergence conditions for the MSOR method, when A is a block-H matrix. We also generalize a theorem of Robert's for this kind of matrices.     

A modified alternating direction method for convex minimization problems

The alternating direction method is an attractive approach for large problems. The convergence proof of the method is based on the exact solutions of the subproblems. Computing the solution of the subproblems exactly can be expensive if the number of unknowns is large. In this paper, for convex quadratic minimization problems, we propose a modified alternating direction method which can overcome the above mentioned disadvantage.     

Optimal convergence for the finite element method in Campanato spaces

We prove a priori estimates and optimal error estimates for linear finite element approximations of elliptic systems in divergence form with continuous coefficients in Campanato spaces. The proofs rely on discrete analogues of the Campanato inequalities for the solution of the system, which locally measure the decay of the energy. As an application of our results we derive -estimates and give a new proof of the well-known -results of Rannacher and Scott.

     

MGM Optimal convergence for certain (multilevel) structured linear systems

We present a multigrid algorithm to solve linear systems whose coefficient metrices belongs to circulant, Hartley or τ multilevel algebras and are generated by a nonnegative multivariate polynomial f. It is known that these matrices are banded (with respect to their multilevel structure) and their eigenvalues are obtained by sampling f on uniform meshes, so they are ill‐conditioned (or singular, and need some corrections) whenever f takes the zero value. We prove the proposed metod to be optimal even in presence of ill‐conditioning: if the multilevel coefficient matrix has dimension ni at level i, i = 1, … , d, then only ni operations are required on each iteration, but the convergence rate keeps constant with respect to N(n) as it depends only on f. The algorithm can be extended to multilevel Toeplitz matrices too.     

A different convergence proof of the projective method for linear programming

We give a different proof of convergence of the polynomial-time algorithm for linear programming based on projective transformations.