More Like this

1. A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations

   https://doi.org/10.1007/978-3-030-69637-5_20  

   Hegde, Chinmay; Keinert, Fritz; Weber, Eric S. (February 2021, Applied and numerical harmonic analysis)

   The Kaczmarz algorithm is an iterative method for solving systems of linear equations. We introduce a modified Kaczmarz algorithm for solving systems of linear equations in a distributed environment, i.e., the equations within the system are distributed over multiple nodes within a network. The modification we introduce is designed for a network with a tree structure that allows for passage of solution estimates between the nodes in the network. We prove that the modified algorithm converges under no additional assumptions on the equations. We demonstrate that the algorithm converges to the solution, or the solution of minimal norm, when the system is consistent. We also demonstrate that in the case of an inconsistent system of equations, the modified relaxed Kaczmarz algorithm converges to a weighted least squares solution as the relaxation parameter approaches 0. 

   more » « less
2. Block Matrix and Tensor Randomized Kaczmarz Methods for Linear Feasibility Problems

   https://doi.org/10.1007/s44007-025-00163-z  

   Zhang, Minxin; Haddock, Jamie; Needell, Deanna (May 2025, La Matematica)

   Abstract The randomized Kaczmarz methods are a popular and effective family of iterative methods for solving large-scale linear systems of equations, which have also been applied to linear feasibility problems. In this work, we propose a new block variant of the randomized Kaczmarz method, B-MRK, for solving linear feasibility problems defined by matrices. We show that B-MRK converges linearly in expectation to the feasible region. Furthermore, we extend the method to solve tensor linear feasibility problems defined under the tensor t-product. A tensor randomized Kaczmarz (TRK) method, TRK-L, is proposed for solving linear feasibility problems that involve mixed equality and inequality constraints. Additionally, we introduce another TRK method, TRK-LB, specifically tailored for cases where the feasible region is defined by linear equality constraints coupled with bound constraints on the variables. We show that both of the TRK methods converge linearly in expectation to the feasible region. Moreover, the effectiveness of our methods is demonstrated through numerical experiments on various Gaussian random data and applications in image deblurring. 

   more » « less
3. The Dual Kaczmarz Algorithm

   https://doi.org/10.1007/s10440-019-00244-6  

   Aboud, Anna; Curl, Emelie; Harding, Steven N.; Vaughan, Mary; Weber, Eric S. (October 2019, Acta Applicandae Mathematicae)

   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 \emph{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 \emph{almost effective}. We also obtain some partial results characterizing when the sequence of approximations from $$\{\langle \vec{x}, \phi_{n} \rangle\}$$ converges to $$x$$, in which case $$\{ (\phi_{n}, \psi_{n}) \}$$ is called an effective pair. 

   more » « less
4. Selectable Set Randomized Kaczmarz

   https://doi.org/10.1002/nla.2458  

   Yaniv, Yotam; Moorman, Jacob D.; Swartworth, William; Tu, Thomas; Landis, Daji; Needell, Deanna (June 2022, Numerical Linear Algebra with Applications)

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

   more » « less
5. Decentralized computation of effective resistances and acceleration of consensus algorithms

   https://doi.org/10.1109/GlobalSIP.2017.8308701  

   Aybat, Necdet Serhat; Gurbuzbalaban, Mert (November 2017, IEEE Global Conference on Signal and Information Processing (GlobalSIP))

   The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure. 

   more » « less