Where Have All the Kaczmarz Iterates Gone?

• URL: http://arxiv.org/abs/2510.08563v1
• Date: Thu, 09 Oct 2025 17:59:36 GMT
• Title: Where Have All the Kaczmarz Iterates Gone?
• Abstract summary: The randomized Kaczmarz (RK) algorithm is one of the most computationally and memory-efficient iterative algorithms for solving large-scale linear systems.<n>This paper investigates the behavior of RK when solving noisy and inconsistent systems, addressing the locations of their limit points.
• Score: 10.915273070034127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The randomized Kaczmarz (RK) algorithm is one of the most computationally and memory-efficient iterative algorithms for solving large-scale linear systems. However, practical applications often involve noisy and potentially inconsistent systems. While the convergence of RK is well understood for consistent systems, the study of RK on noisy, inconsistent linear systems is limited. This paper investigates the asymptotic behavior of RK iterates in expectation when solving noisy and inconsistent systems, addressing the locations of their limit points. We explore the roles of singular vectors of the (noisy) coefficient matrix and derive bounds on the convergence horizon, which depend on the noise levels and system characteristics. Finally, we provide extensive numerical experiments that validate our theoretical findings, offering practical insights into the algorithm's performance under realistic conditions. These results establish a deeper understanding of the RK algorithm's limitations and robustness in noisy environments, paving the way for optimized applications in real-world scientific and engineering problems.

Related papers

• A joint optimization approach to identifying sparse dynamics using least squares kernel collocation [70.13783231186183]
  We develop an all-at-once modeling framework for learning systems of ordinary differential equations (ODE) from scarce, partial, and noisy observations of the states.<n>The proposed methodology amounts to a combination of sparse recovery strategies for the ODE over a function library combined with techniques from reproducing kernel Hilbert space (RKHS) theory for estimating the state and discretizing the ODE.
  arXiv  Detail & Related papers  (2025-11-23T18:04:15Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Limits and Powers of Koopman Learning [0.0]
  Dynamical systems provide a comprehensive way to study complex and changing behaviors across various sciences. Koopman operators have emerged as a dominant approach because they allow the study of nonlinear dynamics using linear techniques. This paper addresses a fundamental open question: textitWhen can we robustly learn the spectral properties of Koopman operators from trajectory data of dynamical systems, and when can we not?
  arXiv  Detail & Related papers  (2024-07-08T18:24:48Z)
• A Note on Randomized Kaczmarz Algorithm for Solving Doubly-Noisy Linear Systems [6.334599472563052]
  Large-scale linear systems, $Ax=b$, frequently arise in practice and demand effective iterative solvers. In this paper, we analyze the convergence of the randomized Kaczmarz algorithm for noisy systems.
  arXiv  Detail & Related papers  (2023-08-31T17:59:00Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning. This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
  arXiv  Detail & Related papers  (2023-04-24T02:19:39Z)
• Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees [39.287388288477096]
  We consider the task of estimating a structural model of dynamic decisions by a human agent based upon the observable history of implemented actions and visited states. This problem has an inherent nested structure: in the inner problem, an optimal policy for a given reward function is identified while in the outer problem, a measure of fit is maximized. We propose a single-loop estimation algorithm with finite time guarantees that is equipped to deal with high-dimensional state spaces.
  arXiv  Detail & Related papers  (2022-10-04T00:11:38Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• A Priori Denoising Strategies for Sparse Identification of Nonlinear Dynamical Systems: A Comparative Study [68.8204255655161]
  We investigate and compare the performance of several local and global smoothing techniques to a priori denoise the state measurements. We show that, in general, global methods, which use the entire measurement data set, outperform local methods, which employ a neighboring data subset around a local point.
  arXiv  Detail & Related papers  (2022-01-29T23:31:25Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
  We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. We propose a likelihood matching algorithm that is resilient to catastrophic forgetting and is completely online.
  arXiv  Detail & Related papers  (2021-02-07T14:19:07Z)
• A Machine Learning Framework for Computing the Most Probable Paths of Stochastic Dynamical Systems [5.028470487310566]
  We develop a machine learning framework to compute the most probable paths in the sense of Onsager-Machlup action functional theory. Specifically, we reformulate the boundary value problem of Hamiltonian system and design a prototypical neural network to remedy the shortcomings of shooting method.
  arXiv  Detail & Related papers  (2020-10-01T20:01:37Z)
• Active Learning for Identification of Linear Dynamical Systems [12.056495277232118]
  We show a finite time bound estimation rate our algorithm attains. We analyze several examples where our algorithm provably improves over rates obtained by playing noise.
  arXiv  Detail & Related papers  (2020-02-02T21:30:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.