A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation

Jackie Lok, Elizaveta Rebrova

Research output: Contribution to journalArticlepeer-review


We study a version of the randomized Kaczmarz algorithm for solving systems of linear equations where the iterates are confined to the solution space of a selected subsystem. We show that the subspace constraint leads to an accelerated convergence rate, especially when the system has approximately low-rank structure. On Gaussian-like random data, we show that it results in a form of dimension reduction that effectively increases the aspect ratio of the system. Furthermore, this method serves as a building block for a second, quantile-based algorithm for solving linear systems with arbitrary sparse corruptions, which is able to efficiently utilize external knowledge about corruption-free equations and achieve convergence in difficult settings. Numerical experiments on synthetic and realistic data support our theoretical results and demonstrate the validity of the proposed methods for even more general data models than guaranteed by the theory.

Original languageEnglish (US)
Pages (from-to)220-260
Number of pages41
JournalLinear Algebra and Its Applications
StatePublished - Oct 1 2024

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • Corrupted linear systems
  • Kaczmarz algorithm
  • Quantile methods
  • Stochastic iterative methods


Dive into the research topics of 'A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation'. Together they form a unique fingerprint.

Cite this