Two-Subspace Projection Method for Coherent Overdetermined Systems
- PDF / 585,068 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 176 Views
Two-Subspace Projection Method for Coherent Overdetermined Systems Deanna Needell · Rachel Ward
Received: 1 April 2012 / Revised: 2 October 2012 / Published online: 9 November 2012 © Springer Science+Business Media New York 2012
Abstract We present a Projection onto Convex Sets (POCS) type algorithm for solving systems of linear equations. POCS methods have found many applications ranging from computer tomography to digital signal and image processing. The Kaczmarz method is one of the most popular solvers for overdetermined systems of linear equations due to its speed and simplicity. Here we introduce and analyze an extension of the Kaczmarz method that iteratively projects the estimate onto a solution space given by two randomly selected rows. We show that this projection algorithm provides exponential convergence to the solution in expectation. The convergence rate improves upon that of the standard randomized Kaczmarz method when the system has correlated rows. Experimental results confirm that in this case our method significantly outperforms the randomized Kaczmarz method. Keywords Kaczmarz method · Randomized Kaczmarz method · Computer tomography · Signal processing Mathematics Subject Classification 65J20 · 47J06 1 Introduction We consider a consistent system of linear equations of the form Ax = b, Communicated by Roman Vershynin. D. Needell () Claremont, CA, USA e-mail: [email protected] R. Ward Austin, TX, USA
J Fourier Anal Appl (2013) 19:256–269
257
Input: Standardized matrix A, vector b Output: An estimation x k of the unique solution x to Ax = b Set x 0 . k←0
{Trivial initial approximation}
repeat k←k+1 Select r ∈ {1, 2, . . . , n} Set x k ← x k−1 + (br − a r , x k−1 )a r
{Randomly select a row of A} {Perform projection}
Algorithm 1: Randomized Kaczmarz where b ∈ Cm and A ∈ Cm×n is a full-rank m × n matrix that is overdetermined, having more rows than columns (m ≥ n). When the number of rows of A is large, it is far too costly to invert the matrix to solve for x, so one may utilize an iterative solver such as the Projection onto Convex Sets (POCS) method, used in many applications of signal and image processing [1, 18]. The Kaczmarz method is often preferred, iteratively cycling through the rows of A and orthogonally projecting the estimate onto the solution space given by each row [10]. Precisely, let us denote by a 1 , a 2 , . . . , a m the rows of A and b1 , b2 , . . . , bm the coordinates of b. We assume each pair of rows is linear independent, and for simplicity, we will assume throughout that the matrix A is standardized, meaning that each of its rows has unit Euclidean norm; generalizations from this case will be straightforward. Given some trivial initial estimate x 0 , the Kaczmarz method cycles through the rows of A and in the kth iteration projects the previous estimate x k onto the solution hyperplane of a i , x = bi where i = k mod m, x k+1 = x k + bi − a i , x k a i . Theoretical results about the rate of convergence of the Kaczmarz method have been difficult to obtain
Data Loading...
