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.

     

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.     

Almost Sure Convergence of the Kaczmarz Algorithm with Random Measurements

The Kaczmarz algorithm is an iterative method for reconstructing a signal x??? ^d from an overcomplete collection of linear measurements y _n =??x,?? _n ??, n??1. We prove quantitative bounds on the rate of almost sure exponential convergence in the Kaczmarz algorithm for suitable classes of random measurement vectors $\{\varphi_{n}\}_{n=1}^{\infty} \subset {\mathbb {R}}^{d}$ . Refined convergence results are given for the special case when each ?? _n has i.i.d. Gaussian entries and, more generally, when each ?? _n /???? _n ?? is uniformly distributed on $\mathbb{S}^{d-1}$ . This work on almost sure convergence complements the mean squared error analysis of Strohmer and Vershynin for randomized versions of the Kaczmarz algorithm.     

On block Gaussian sketching for the Kaczmarz method

Numerical Algorithms - The Kaczmarz algorithm is one of the most popular methods for solving large-scale over-determined linear systems due to its simplicity and computational efficiency. This...     

On the Kaczmarz iterative method and its generalizations

Under study is the family of iterative projection methods that stems from the work of Kaczmarz in 1937. We propose some alternating block algorithms of Kaczmarz type in Krylov subspaces with a relaxation parameter and acceleration in Krylov spaces. The results are presented and discussed of numerical experiments for some model problems.     

On a General Projection Algorithm for Variational Inequalities

Let H be a real Hilbert space with norm and inner product denoted by and . Let K be a nonempty closed convex set of H, and let f be a linear continuous functional on H. Let A, T, g be nonlinear operators from H into itself, and let be a point-to-set mapping. We deal with the problem of finding uK such that g(u)K(u) and the following relation is satisfied: , where >0 is a constant, which is called a general strong quasi-variational inequality. We give a general and unified iterative algorithm for finding the approximate solution to this problem by exploiting the projection method, and prove the existence of the solution to this problem and the convergence of the iterative sequence generated by this algorithm.     

Unconstrained Optimization Techniques for the Acceleration of Alternating Projection Methods

Alternating projection methods have been extensively used to find the closest point, to a given point, in the intersection of several given sets that belong to a Hilbert space. One of the characteristics of these schemes is the slow convergence that can be observed in practical applications. To overcome this difficulty, several techniques, based on different ideas, have been developed to accelerate their convergence. Recently, a successful acceleration scheme was developed specially for Cimmino's method when applied to the solution of large-scale saddle point problems. This specialized acceleration scheme is based on the use of the well-known conjugate gradient method for minimizing a related convex quadratic map. In this work, we extend and further analyze this optimization approach for several alternating projection methods on different scenarios. In particular, we include a specialized analysis and treatment for the acceleration of von Neumann-Halperin's method and Cimmino's method on subspaces, and Kaczmarz method on linear varieties. For some specific applications we illustrate the advantages of our acceleration schemes with encouraging numerical experiments.     

A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin

In a recent paper by Strohmer and Vershynin (J. Fourier Anal. Appl. 15:262–278, 2009) a “randomized Kaczmarz algorithm” is proposed for solving consistent systems of linear equations {〈a ⁱ ,x〉=b _i } _i=1 ^m . In that algorithm the next equation to be used in an iterative Kaczmarz process is selected with a probability proportional to ‖a ⁱ ‖². The paper illustrates the superiority of this selection method for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values. In this note we point out that the reported success of the algorithm of Strohmer and Vershynin in their numerical simulation depends on the specific choices that are made in translating the underlying problem, whose geometrical nature is “find a common point of a set of hyperplanes”, into a system of algebraic equations. If this translation is carefully done, as in the numerical simulation provided by Strohmer and Vershynin for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values, then indeed good performance may result. However, there will always be legitimate algebraic representations of the underlying problem (so that the set of solutions of the system of algebraic equations is exactly the set of points in the intersection of the hyperplanes), for which the selection method of Strohmer and Vershynin will perform in an inferior manner.     

Projection Greedy Algorithm

Mathematical Notes - We introduce and study a new type of greedy algorithm, namely, projection greedy algorithms with respect to a given dictionary in a Hilbert space. We prove that these...     

On the Cesaro Summability with Respect to the Walsh–Kaczmarz System

The Walsh system will be considered in the Kaczmarz rearrangement. We show that the maximal operator σ* of the (C,1)-means of the Walsh–Kaczmarz–Fourier series is bounded from the dyadic Hardy space H^p into L^p for every 1/2<p1. From this it follows by standard arguments that σ* is of weak type (1, 1) and bounded from L^q into L^q if 1<q∞.     

Monte Carlo EM加速算法

EM算法是近年来常用的求后验众数的估计的一种数据增广算法, 但由于求出其E步中积分的显示表达式有时很困难, 甚至不可能, 限制了其应用的广泛性. 而Monte Carlo EM算法很好地解决了这个问题, 将EM算法中E步的积分用Monte Carlo模拟来有效实现, 使其适用性大大增强. 但无论是EM算法, 还是Monte Carlo EM算法, 其收敛速度都是线性的, 被缺损信息的倒数所控制, 当缺损数据的比例很高时, 收敛速度就非常缓慢. 而Newton-Raphson算法在后验众数的附近具有二次收敛速率. 本文提出Monte Carlo EM加速算法, 将Monte Carlo EM算法与Newton-Raphson算法结合, 既使得EM算法中的E步用Monte Carlo模拟得以实现, 又证明了该算法在后验众数附近具有二次收敛速度. 从而使其保留了Monte Carlo EM算法的优点, 并改进了Monte Carlo EM算法的收敛速度. 本文通过数值例子, 将Monte Carlo EM加速算法的结果与EM算法、Monte Carlo EM算法的结果进行比较, 进一步说明了Monte Carlo EM加速算法的优良性.     

On the two-dimensional Marcinkiewicz means with respect to Walsh–Kaczmarz system

In this paper we prove that the maximal operator of the Marcinkiewicz means of two-dimensional integrable functions with respect to the Walsh–Kaczmarz system is of weak type (1,1). Moreover, the Marcinkiewicz means converge to f almost everywhere, for any integrable function f.     

关于q-Bernstein多项式的加速问题

In this paper,we investigate not only the acceleration problem of the q-Bernstein polynomials Bn(f,q;x)to B∞(f,q;x)but also the convergence of their iterated Boolean sum.Using the methods of exact estimate and theories of modulus of smoothness,we get the respective estimates of the convergence rate,which suggest that q-Bernstein polynomials have the similar answer with the classical Bernstein polynomials to these two problems.     

An Acceleration Scheme for Solving Convex Feasibility Problems Using Incomplete Projection Algorithms

The Projected Aggregation Methods (PAM) for solving linear systems of equalities and/or inequalities, generate a new iterate x ^k+1 by projecting the current point x ^k onto a separating hyperplane generated by a given linear combination of the original hyperplanes or halfspaces. In [12] we introduced acceleration schemes for solving systems of linear equations by applying optimization techniques to the problem of finding the optimal combination of the hyperplanes within a PAM like framework. In this paper we generalize those results, introducing a new accelerated iterative method for solving systems of linear inequalities, together with the corresponding theoretical convergence results. In order to test its efficiency, numerical results obtained applying the new acceleration scheme to two algorithms introduced by García-Palomares and González-Castaño [6] are given.     

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...     

On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems

For solving large sparse systems of linear equations by iteration methods, we further generalize the greedy randomized Kaczmarz method by introducing a relaxation parameter in the involved probability criterion, obtaining a class of relaxed greedy randomized Kaczmarz methods. We prove the convergence of these methods when the linear system is consistent, and show that these methods can be more efficient than the greedy randomized Kaczmarz method if the relaxation parameter is chosen appropriately.