A Randomized Kaczmarz Algorithm with Exponential Convergence

Thomas Strohmer, Roman Vershynin

Type: Article

Publication Date: 2008-04-24

Citations: 833

DOI: https://doi.org/10.1007/s00041-008-9030-4

View Publication

Download PDF

Locations

Journal of Fourier Analysis and Applications - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	A randomized Kaczmarz algorithm with exponential convergence	2007	Thomas Strohmer Roman Vershynin
+	A Randomized Solver for Linear Systems with Exponential Convergence	2006	Thomas Strohmer Roman Vershynin
+ PDF Chat	Randomized Kaczmarz algorithms: Exact MSE analysis and optimal sampling probabilities	2014	Ameya Agaskar Chuang Wang Yue M. Lu
+	A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear systems	2013	Hassan Mansour Özgür Yılmaz
+	A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear systems	2013	Hassan Mansour Özgür Yılmaz
+ PDF Chat	Randomized Kaczmarz algorithm for inconsistent linear systems: An exact MSE analysis	2015	Chuang Wang Ameya Agaskar Yue M. Lu
+	Randomized Kaczmarz Algorithm for Inconsistent Linear Systems: An Exact MSE Analysis	2015	Chuang Wang Ameya Agaskar Yue M. Lu
+ PDF Chat	Randomized Kaczmarz solver for noisy linear systems	2010	Deanna Needell
+	Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma	2010	Yonina C. Eldar Deanna Needell
+	Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma	2010	Yonina C. Eldar Deanna Needell
+ PDF Chat	Preasymptotic convergence of randomized Kaczmarz method	2017	Yuling Jiao Bangti Jin Xiliang Lu
+ PDF Chat	Two-Subspace Projection Method for Coherent Overdetermined Systems	2012	Deanna Needell Rachel Ward
+	Two-subspace Projection Method for Coherent Overdetermined Systems	2012	Deanna Needell Rachel Ward
+	Convergence of the randomized Kaczmarz method for phase retrieval	2017	Halyun Jeong C. Sınan Güntürk
+	Randomized Block Kaczmarz Method with Projection for Solving Least Squares	2014	Deanna Needell Ran Zhao Anastasios Zouzias
+	Randomized Block Kaczmarz Method with Projection for Solving Least Squares	2014	Deanna Needell Ran Zhao Anastasios Zouzias
+	Randomized block Kaczmarz method with projection for solving least squares	2015	Deanna Needell Ran Zhao Anastasios Zouzias
+	Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints	2023	Halyun Jeong Deanna Needell
+	Two-subspace Projection Method for Coherent Overdetermined Systems	2012	Deanna Needell Rachel Ward
+	A Count Sketch Kaczmarz Method For Solving Large Overdetermined Linear Systems	2020	Yanjun Zhang Hanyu Li

Works That Cite This (574)

Action	Title	Year	Authors
+	Effects of conditioning on the convergence of randomized optimization algorithms	2009	Adrian S. Lewis D. Leventhal
+	Kaczmarz's anomaly: A surprising feature of Kaczmarz's method	2023	Achiya Dax
+	Stochastic Gradient Descent Variants for Corrupted Systems of Linear Equations	2020	Jamie Haddock Deanna Needell Elizaveta Rebrova William Swartworth
+ PDF Chat	Rejoinder: “Nonparametric regression using deep neural networks with ReLU activation function”	2020	Johannes Schmidt-Hieber
+ PDF Chat	Fast iterative regularization by reusing data	2023	Cristian Vega Cesare Molinari Lorenzo Rosasco Silvia Villa
+ PDF Chat	On Adaptive Stochastic Heavy Ball Momentum for Solving Linear Systems	2024	Yun Zeng Deren Han Yansheng Su Jiaxin Xie
+ PDF Chat	Nonparametric regression using deep neural networks with ReLU activation function	2020	Johannes Schmidt-Hieber
+ PDF Chat	Randomized Kaczmarz solver for noisy linear systems	2010	Deanna Needell
+	On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems	2018	Zhong‐Zhi Bai Wen-Ting Wu
+	On the Polyak momentum variants of the greedy deterministic single and multiple row-action methods	2022	Nian‐Ci Wu Qian Zuo Yatian Wang

Works Cited by This (29)

Action	Title	Year	Authors
+	Conjugate Gradient Type Methods for Ill-Posed Problems	2017	Martin Hanke
+	Rate of Convergence of the Method of Alternating Projections	1984	Frank Deutsch
+ PDF Chat	Eigenvalues and Condition Numbers of Random Matrices	1988	Alan Edelman
+	Iterative and one-step reconstruction from nonuniform samples by convex projections	1990	Shu-Jen Yeh Henry Stark
+	Spectral Analysis of Networks with Random Topologies	1977	Ulf Grenander Jack W. Silverstein
+	Fast monte-carlo algorithms for finding low-rank approximations	2004	Alan Frieze Ravi Kannan Santosh Vempala
+ PDF Chat	Inverse Littlewood–Offord theorems and the condition number of random discrete matrices	2009	Terence Tao Van H. Vu
+	<title>New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling</title>	1992	Hans G. Feichtinger C. Cenker Monika Mayer H. Steier Thomas Strohmer
+	Random Sampling of Multivariate Trigonometric Polynomials	2004	Richard F. Bass Karlheinz Gröchenig
+ PDF Chat	Relaxation methods for image reconstruction	1978	Gábor T. Herman Arnold Lent Peter H. Lutz