More Like this

1. A Randomized Distributed Kaczmarz Algorithm and Anomaly Detection

   https://doi.org/10.3390/axioms11030106  

   Keinert, Fritz; Weber, Eric S. (March 2022, Axioms)

   The Kaczmarz algorithm is an iterative method for solving systems of linear equations. We introduce a randomized 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 demonstrate that the algorithm converges to the solution, or the solution of minimal norm, when the system is consistent. We also prove convergence rates of the randomized algorithm that depend on the spectral data of the coefficient matrix and the random control probability distribution. In addition, we demonstrate that the randomized algorithm can be used to identify anomalies in the system of equations when the measurements are perturbed by large, sparse noise. 

   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. Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

   https://doi.org/10.1609/aaai.v36i9.21174  

   Qiu, Zirou; Chen, Chen; Marathe, Madhav; Ravi, S.S.; Rosenkrantz, Daniel J.; Stearns, Richard; Vullikanti, Anil (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data areavailable at: https://github.com/bridgelessqiu/NMIN-FPE 

   more » « less
5. Cooling Improves Cosmic Microwave Background Map-making when Low-frequency Noise is Large

   https://doi.org/10.3847/1538-4357/ac31ab  

   Chiang 强, Bai-Chiang 百强; Huffenberger, Kevin M. (November 2021, The Astrophysical Journal)

   Abstract In the context of cosmic microwave background data analysis, we study the solution to the equation that transforms scanning data into a map. As originally suggested in “messenger” methods for solving linear systems, we split the noise covariance into uniform and nonuniform parts and adjust their relative weights during the iterative solution. With simulations, we study mock instrumental data with different noise properties, and find that this “cooling” or perturbative approach is particularly effective when there is significant low-frequency noise in the timestream. In such cases, a conjugate gradient algorithm applied to this modified system converges faster and to a higher fidelity solution than the standard conjugate gradient approach. We give an analytic estimate for the parameter that controls how gradually the linear system should change during the course of the solution. 

   more » « less