A Note On Convergence Rate of Randomized Kaczmarz Method
- PDF / 1,088,385 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 165 Views
A Note On Convergence Rate of Randomized Kaczmarz Method Ying‑Jun Guan1 · Wei‑Guo Li1 · Li‑Li Xing1 · Tian‑Tian Qiao1 Received: 27 May 2020 / Revised: 20 July 2020 / Accepted: 27 July 2020 © Istituto di Informatica e Telematica (IIT) 2020
Abstract In this paper, we propose an alternative version of the randomized Kaczmarz method, which chooses each row of the coefficient matrix A with probability proportional to the square of the Euclidean norm of the residual of each corresponding equation. We prove that it converges with expected linear rate and the convergence rate of this method is better than the Strohmer and Vershynin’s RK method. Numerical experiments also show this method is more efficient than the RK method. Keywords Linear system · Residual · Randomized Kaczmarz method · Expected linear rate Mathematics Subject Classifification 15A06 · 65F10 · 65F20
1 Introduction Consider to solve a consistent linear system of equations
Ax = b,
(1.1)
where matrix A ∈ ℝm×n , b ∈ ℝm , and x( ∈ ℝn is the) unknown vector. Denote the T rows of A by aT1 , aT2 , ..., aTm and let b = b1 , b2 , ..., bm . The Kaczmarz method [9] (or the algebraic reconstruction technique (ART) [6]) is one of the most popular solvers. At each iteration, the Kaczmarz method uses the cyclic rule to choose a row of the matrix and projects the current iteration onto the corresponding hyperplane. In 2009, Strohmer and Vershynin [14] proved firstly that the randomized Kaczmarz (RK) method converges with linear rate. In addition, many authors have This research is supported by National Key Research and Development program of China (2017YFC1405600), the Fundamental Research Funds for the Central Universities (19CX05003A-2) and Fundamental Research Funds for the Central Universities (18CX02041A). * Wei‑Guo Li [email protected] 1
College of Science, China University of Petroleum, Qingdao 266580, People’s Republic of China
13
Vol.:(0123456789)
26
Page 2 of 11
Y.-J. Guan et al.
explored the convergence rate of random methods for other linear problems with the same row or column choosing rule as the RK; see, e.g., [8, 10, 11, 15]. If we consider the greedy selection rules, there are at least two methods: the maximum residual (MR) rule and the maximum distance (MD) rule respectively:
ik = arg max �⟨ai , x⟩ − bi � (MR); i
ik = arg max �⟨ai , x⟩ − bi �∕‖ai ‖2 (MD) i
(1.2) where ik is the row index that should be selected at the kth iteration; see, e.g., [1, 12, 13]. However, the row selection rule used in the RK is not necessarily optimal in general [5]. In particular, if they scaled their equations so that ‖ai ‖2 = 1 ( i = 1, 2, … , m ) after scaling, then the difference between the behaviors of simple randomized Kaczmarz and of the RK would have disappeared [5]. Bai and Wu [2] introduced an effective probability criterion for selecting the working rows from the coefficient matrix and constructed the greedy randomized Kaczmarz (GRK) method. It is proved that this method converges to the unique least-norm solution of the linear system when
Data Loading...
