About the Selection of the Relaxation and Ordering of the Projections in Kaczmarz method with Emphasis on Highly Parallel Implementations and Applications in Tomographic Reconstruction

• Grant number: 12/11207-2
• Support Opportunities: Scholarships in Brazil - Master
• Start date: September 01, 2012
• End date: December 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Elias Salomão Helou Neto
• Grantee: Leonardo Bravo Estácio
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Recently, works have been published where averaged convergence rates for the Kaczmarz method were obtained when the ordering of the hyperplanes over which the iteration is projected is chosen in a random way, under a appropriate probabilistic distribution. Using such results, other researchers where able to speed up the convergence of the algorithm through a dimensionality reduction strategy based on Johnson-Lindenstrauss lemma. This latter adptation passes a essentially parallel nature, where several projections are computed (in a reduced dimension space), but only the one which advances the most in the direction of the desired solution is used. Furthermore, in both of the mentioned works, the step size is such that the projection over each hyperplane is exact, but it has been recognized that other values for this parameter lead to a faster convergence to the solution.The intention of the present project is to study parallel implementation of Eldar and Needel's method, and to search for theoretical and empirical solutions for the problem of choosing the relaxation parameter which provides the highest possible convergence speed for the Kaczmarz.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

ESTÁCIO, Leonardo Bravo. On the choice of relaxation and ordering of projections in Kaczmarz method with emphasis on highly prallel implementations and applications in tomographic reconstruction. 2014. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.