Column-oriented algebraic iterative methods for nonnegative constrained least squares problems

Numerical Algorithms - This paper considers different versions of block-column iterative (BCI) methods for solving nonnegative constrained linear least squares problems. We present the convergence...     

A new step size rule for the superiorization method and its application in computerized tomography

Numerical Algorithms - In this paper, we consider a regularized least squares problem subject to convex constraints. Our algorithm is based on the superiorization technique, equipped with a new...     

Convergence analysis for column-action methods in image reconstruction

Column-oriented versions of algebraic iterative methods are interesting alternatives to their row-version counterparts: they converge to a least squares solution, and they provide a basis for saving computational work by skipping small updates. In this paper we consider the case of noise-free data. We present a convergence analysis of the column algorithms, we discuss two techniques (loping and flagging) for reducing the work, and we establish some convergence results for methods that utilize these techniques. The performance of the algorithms is illustrated with numerical examples from computed tomography.     

On the convergence of nonstationary column-oriented version of algebraic iterative methods

Recently, Elfving, Hansen, and Nikazad introduced a successful nonstationary block-column iterative method for solving linear system of equations based on flagging idea (called BCI-F). Their numerical tests show that the column-action method provides a basis for saving computational work using flagging technique in BCI algorithm. However, they did not present a general convergence analysis. In this paper, we give a convergence analysis of BCI-F. Furthermore, we consider a fully flexible version of block-column iterative method (FBCI), in which the relaxation parameters and weight matrices can be updated in each iteration and the column partitioning of coefficient matrix is allowed to update in each cycle. We also provide the convergence analysis of algorithm FBCI under mild conditions.     

Controlling noise error in block iterative methods

This paper describes a new \(O(N^{\frac {3}{2}}\log (N))\) solver for the symmetric positive definite Toeplitz system T_Nx_N = b_N. The method is based on the block QR decomposition of T_N accompanied with Levinson algorithm and its generalized version for solving Schur complements S_m of size m. In our algorithm we use a formula for displacement rank representation of the S_m in terms of generating vectors of the matrix T_N, and we assume that N = lm with \(l, m\in \mathbb {N}\). The new algorithm is faster than the classical O(N²)-algorithm for N > 2⁹. Numerical experiments confirm the good computational properties of the new method.