A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates

Reconstructing bandlimited functions from random sampling is an important problem in signal processing. Strohmer and Vershynin obtained good results for this problem by using a randomized version of the Kaczmarz algorithm (RK) and assigning to every equation a probability weight proportional to the average distance of the sample from its two nearest neighbors. However, their results are valid only for moderate to high sampling rates; in practice, it may not always be possible to obtain many samples. Experiments show that the number of projections required by RK and other Kaczmarz variants rises seemingly exponentially when the equations/variables ratio (EVR) falls below 5. CGMN, which is a CG acceleration of Kaczmarz, provides very good results for low values of EVR and it is much better than CGNR and CGNE. A derandomization method, based on an extension of the bit-reversal permutation, is combined with the weights and shown to improve the performance of CGMN and the regular (cyclic) Kaczmarz, which even outperforms RK. A byproduct of our results is the finding that signals composed mainly of high-frequency components are easier to recover.     

Two-Subspace Projection Method for Coherent Overdetermined Systems

We present a Projection onto Convex Sets (POCS) type algorithm for solving systems of linear equations. POCS methods have found many applications ranging from computer tomography to digital signal and image processing. The Kaczmarz method is one of the most popular solvers for overdetermined systems of linear equations due to its speed and simplicity. Here we introduce and analyze an extension of the Kaczmarz method that iteratively projects the estimate onto a solution space given by two randomly selected rows. We show that this projection algorithm provides exponential convergence to the solution in expectation. The convergence rate improves upon that of the standard randomized Kaczmarz method when the system has correlated rows. Experimental results confirm that in this case our method significantly outperforms the randomized Kaczmarz method.     

A proximal augmented Lagrangian method for equilibrium problems

Considering a recently proposed proximal point method for equilibrium problems, we construct an augmented Lagrangian method for solving the same problem in reflexive Banach spaces with cone constraints generating a strongly convergent sequence to a certain solution of the problem. This is an inexact hybrid method meaning that at a certain iterate, a solution of an unconstrained equilibrium problem is found, allowing a proper error bound, followed by a Bregman projection of the initial iterate onto the intersection of two appropriate halfspaces. Assuming a set of reasonable hypotheses, we provide a full convergence analysis.     

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.     

A generalized cyclic iterative method for solving variational inequalities over the solution set of a split common fixed point problem

For solving the large-scale linear least-squares problem, we propose a block version of the randomized extended Kaczmarz method, called the two-subspace randomized extended Kaczmarz method, which does not require any row or column paving. Theoretical analysis and numerical results show that the two-subspace randomized extended Kaczmarz method is much more efficient than the randomized extended Kaczmarz method. When the coefficient matrix is of full column rank, the two-subspace randomized extended Kaczmarz method can also outperform the randomized coordinate descent method. If the linear system is consistent, we remove one of the iteration sequences in the two-subspace randomized extended Kaczmarz method, which approximates the projection of the right-hand side vector onto the orthogonal complement space of the range space of the coefficient matrix, and obtain the generalized two-subspace randomized Kaczmarz method, which is actually a generalization of the two-subspace randomized Kaczmarz method without the assumptions of unit row norms and full column rank on the coefficient matrix. We give the upper bound for the convergence rate of the generalized two-subspace randomized Kaczmarz method which also leads to a better upper bound for the convergence rate of the two-subspace randomized Kaczmarz method.

     

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.     

On the Acceleration of Kaczmarz Projection Algorithm

In the paper [1], a direct version of the classical Kaczmarz algorithm was proposed, which gives us in only one iteration a solution of an arbitrary consistent system of linear equations. Unfortunately, as any direct method applied to large sparse matrices, this algorithm is based on some modifications of the system matrix sparsity structure such that a big fill-in appears. In order to overcome this difficulty, in the present paper we propose a modified version of this direct Kaczmarz algorithm in which the transformations applied to the system matrix try to conserve the initial sparsity structure. This transformations are done via clustering using Jaccard and Hamming distances. The modified Kaczmarz algorithm is no more a direct method, but we obtain an acceleration of convergence with respect to the classical Kaczmarz algorithm. Numerical experiments which ilustrate the efficiency of our algorithm are also presented. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A half-space projection method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method.     

Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma

The Kaczmarz method is an algorithm for finding the solution to an overdetermined consistent system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson–Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.     

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.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

A Conic Trust-Region Method for Nonlinearly Constrained Optimization

Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions.     

Single projection Kaczmarz extended algorithms

In order to find the least squares solution of a very large and inconsistent system of equations, one can employ the extended Kaczmarz algorithm. This method simultaneously removes the error term, so that a consistent system is asymptotically obtained, and applies Kaczmarz iterations for the current approximation of this system. It has been shown that for random corrections of the right hand side and Kaczmarz updates selected at random, the algorithm converges to the least squares solution. In this work we consider deterministic strategies like the maximal-residual and the almost-cyclic control, and show convergence to a least squares solution.     

A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS

In this paper, we propose a feasible QP-free method for solving nonlinear inequality constrained optimization problems. A new working set is proposed to estimate the active set. Specially, to determine the working set, the new method makes use of the multiplier information from the previous iteration, eliminating the need to compute a multiplier function. At each iteration, two or three reduced symmetric systems of linear equations with a common coefficient matrix involving only constraints in the working set are solved, and when the iterate is sufficiently close to a KKT point, only two of them are involved. Moreover, the new algorithm is proved to be globally convergent to a KKT point under mild conditions. Without assuming the strict complementarity, the convergence rate is superlinear under a condition weaker than the strong second-order sufficiency condition. Numerical experiments illustrate the efficiency of the algorithm.     

一种新的记忆梯度法及其收敛性

本文提出一种新的无约束优化记忆梯度算法,算法在每步迭代时利用了前面迭代点的信息,增加了参数选择的自由度,适于求解大规模无约束优化问题.分析了算法的全局收敛性.数值试验表明算法是有效的.     

Strong Convergence of an Inexact Proximal Point Algorithm for Equilibrium Problems in Banach Spaces

We develop an inexact proximal point algorithm for solving equilibrium problems in Banach spaces which consists of two principal steps and admits an interesting geometric interpretation. At a certain iterate, first we solve an inexact regularized equilibrium problem with a flexible error criterion to obtain an axillary point. Using this axillary point and the inexact solution of the previous iterate, we construct two appropriate hyperplanes which separate the current iterate from the solution set of the given problem. Then the next iterate is defined as the Bregman projection of the initial point onto the intersection of two halfspaces obtained from the two constructed hyperplanes containing the solution set of the original problem. Assuming standard hypotheses, we present a convergence analysis for our algorithm, establishing that the generated sequence strongly and globally converges to a solution of the problem which is the closest one to the starting point of the algorithm.     

Constraining by a family of strictly nonexpansive idempotent functions with applications in image reconstruction

When solving an image reconstruction problem a previous knowledge concerning the original image may lead to various constraining strategies. A convergence result has been previously proved for a constrained version of the Kaczmarz projection algorithm with a single strictly nonexpansive idempotent function with a closed image. In this paper we consider a more general projection based iterative method and a family of such constraining functions with some additional hypotheses in order to better use the a priori information for every approximation calculated. We present a particular family of box-constraining functions which satisfies our assumptions and we design an adaptive algorithm that uses an iteration-dependent family of constraining functions for some numerical experiments of image reconstruction on Tomographic Particle Image Velocimetry.     

有限元模型修正问题的不精确最速下降迭代解

在结构动力分析中,往往需利用结构振动测试所得的实际测量数据(如振动频率和振型),对结构分析模型进行最优修正,使之更能合理反映结构的实际性能,其实质即为计算数学中的特征值反问题.本文考虑有阻尼结构振动中的-类反问题,用一组不完备的模态测量数据修正系统质量矩阵、刚度矩阵和阻尼矩阵,通过等价正交投影思想将原问题转化成-个闭凸锥上的正交投影问题,构造-个不精确最速下降迭代法求解,并讨论了收敛性.算例表明算法是有效的.     

A superlinearly convergent projection method for constrained systems of nonlinear equations

In this paper, a new projection method for solving a system of nonlinear equations with convex constraints is presented. Compared with the existing projection method for solving the problem, the projection region in this new algorithm is modified which makes an optimal stepsize available at each iteration and hence guarantees that the next iterate is more closer to the solution set. Under mild conditions, we show that the method is globally convergent, and if an error bound assumption holds in addition, it is shown to be superlinearly convergent. Preliminary numerical experiments also show that this method is more efficient and promising than the existing projection method. This work was done when Yiju Wang visited Chongqing Normal University.     

Projection methods for the numerical solution of non-self-adjoint elliptic partial differential equations

We compare the relative performances of two iterative schemes based on projection techniques for the solution of large sparse nonsymmetric systems of linear equations, encountered in the numerical solution of partial differential equations. The Block–Symmetric Successive Over-Relaxation (Block-SSOR) method and the Symmetric–Kaczmarz method are derived from the simplest of projection methods, that is, the Kaczmarz method. These methods are then accelerated using the conjugate gradient method, in order to improve their convergence. We study their behavior on various test problems and comment on the conditions under which one method would be better than the other. We show that while the conjugate-gradient-accelerated Block-SSOR method is more amenable to implementation on vector and parallel computers, the conjugate-gradient accelerated Symmetric–Kaczmarz method provides a viable alternative for use on a scalar machine.