Enhancement of the Kaczmarz algorithm with projection adjustment

Numerical Algorithms - Projection adjustment is a technique that improves the rate of convergence, as measured by the number of iterations needed to achieve a given level of performance, of the...     

Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms

The randomized extended Kaczmarz and Gauss–Seidel algorithms have attracted much attention because of their ability to treat all types of linear systems (consistent or inconsistent, full rank or rank deficient). In this paper, we present tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms. Numerical experiments are given to illustrate the theoretical results.     

Characterization of the solutions set of inconsistent least-squares problems by an extended Kaczmarz algorithm

We give a new characterization of the solutions set of the general (inconsistent) linear least-squares problem using the set of limit-points of an extended version of the classical Kaczmarz’s projections method. We also obtain a “ step error reduction formula” which, in some cases, can give us apriori information about the convergence properties of the algorithm. Some numerical experiments with our algorithm and comparisons between it and others existent in the literature, are made in the last section of the paper.     

Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

Normal projection: deterministic and probabilistic algorithms

We consider the following problem： for a collection of points in an n-dimensional space, find a linear projection mapping the points to the ground field such that different points are mapped to different values. Such projections are called normal and are useful for making algebraic varieties into normal positions. The points may be given explicitly or implicitly and the coefficients of the projection come from a subset S of the ground field. If the subset S is small, this problem may be hard. This paper deals with relatively large S, a deterministic algorithm is given when the points are given explicitly, and a lower bound for success probability is given for a probabilistic algorithm from in the literature.     

Inertial projection and contraction algorithms for variational inequalities

In this article, we introduce an inertial projection and contraction algorithm by combining inertial type algorithms with the projection and contraction algorithm for solving a variational inequality in a Hilbert space H. In addition, we propose a modified version of our algorithm to find a common element of the set of solutions of a variational inequality and the set of fixed points of a nonexpansive mapping in H. We establish weak convergence theorems for both proposed algorithms. Finally, we give the numerical experiments to show the efficiency and advantage of the inertial projection and contraction algorithm.     

Dual extragradient algorithms extended to equilibrium problems

In this paper we propose two iterative schemes for solving equilibrium problems which are called dual extragradient algorithms. In contrast with the primal extragradient methods in Quoc et al. (Optimization 57(6):749–776, 2008) which require to solve two general strongly convex programs at each iteration, the dual extragradient algorithms proposed in this paper only need to solve, at each iteration, one general strongly convex program, one projection problem and one subgradient calculation. Moreover, we provide the worst case complexity bounds of these algorithms, which have not been done in the primal extragradient methods yet. An application to Nash-Cournot equilibrium models of electricity markets is presented and implemented to examine the performance of the proposed algorithms.     

Selectable Set Randomized Kaczmarz

The Randomized Kaczmarz method (RK) is a stochastic iterative method for solving linear systems that has recently grown in popularity due to its speed and low memory requirement. Selectable Set Randomized Kaczmarz is a variant of RK that leverages existing information about the Kaczmarz iterate to identify an adaptive “selectable set” and thus yields an improved convergence guarantee. In this article, we propose a general perspective for selectable set approaches and prove a convergence result for that framework. In addition, we define two specific selectable set sampling strategies that have competitive convergence guarantees to those of other variants of RK. One selectable set sampling strategy leverages information about the previous iterate, while the other leverages the orthogonality structure of the problem via the Gramian matrix. We complement our theoretical results with numerical experiments that compare our proposed rules with those existing in the literature.     

The Dual Kaczmarz Algorithm

The Kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector \(x\) in a (separable) Hilbert space from the inner-products \(\{\langle x, \phi _{n} \rangle \}\). The Kaczmarz algorithm defines a sequence of approximations from the sequence \(\{\langle x, \phi _{n} \rangle \}\); these approximations only converge to \(x\) when \(\{\phi _{n}\}\) is effective. We dualize the Kaczmarz algorithm so that \(x\) can be obtained from \(\{\langle x, \phi _{n} \rangle \}\) by using a second sequence \(\{\psi _{n}\}\) in the reconstruction. This allows for the recovery of \(x\) even when the sequence \(\{\phi _{n}\}\) is not effective; in particular, our dualization yields a reconstruction when the sequence \(\{\phi _{n}\}\) is almost effective. We also obtain some partial results characterizing when the sequence of approximations from \(\{\langle x, \phi _{n} \rangle \}\) using \(\{\psi _{n}\}\) converges to \(x\), in which case \(\{(\phi _{n}, \psi _{n})\}\) is called an effective pair.

     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

Some properties of the recursive projection and interpolation algorithms

The recursive projection algorithm (rpa), derived from the vectorSylvester identity, has a connection with the recursive interpolationalgorithm (ria). These algorithms have many applications andconnections with some other methods used in various areas ofnumerical analysis. The aim of this paper is to study some propertiesof these algorithms. We use properties of projectors, a matriximplementation and the Schur complement extended to the vectorcase, to give a result about their finite termination.     

Imperfect conjugate gradient algorithms for extended quadratic functions

Summary Generalized conjugate gradient algorithms which are invariant to a nonlinear scaling of a strictly convex quadratic function are described. The algorithms when applied to scaled quadratic functionsfR _n R ₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹(R ₁) an arbitrary strictly monotone functionh generate the same direction vectors as for the functionF without perfect steps.     

A class of superlinearly convergent projection algorithms with relaxed stepsizes

A quasi-Newton extension of the Goldstein-Levitin-Polyak (GLP) projected gradient algorithm for constrained optimization is considered. Essentially, this extension projects an unconstrained descent step on to the feasible region. The determination of the stepsize is divided into two stages. The first is a stepsize sequence, chosen from the range [1,2], converging to unity. This determines the size of the unconstrained step. The second is a stepsize chosen from the range [0,1] according to a stepsize strategy and determines the length of the projected step. Two such strategies are considered. The first bounds the objective function decrease by a conventional linear functional, whereas the second uses a quadratic functional as a bound.The introduction of the unconstrained step provides the option of taking steps that are larger than unity. It is shown that unit steplengths and subsequently superlinear convergence rates are attained if the projection of the quasi-Newton Hessian approximation approaches the projection of the Hessian at the solution. Thus, the requirement in the GLP algorithm for a positive definite Hessian at the solution is relaxed. This allows the use of strictly positive definite Hessian approximations, thereby simplifying the quadratic subproblem involved, even if the Hessian at the solution is not strictly positive definite.This research was funded by a Science and Engineering Research Council Advanced Fellowship. The author is also grateful to an anonymous referee for numerous constructive criticisms and comments.     

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.     

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.