CSL Decision and Control Group

Back to Listing

DCL Lecture Series: Randomized Kaczmarz Algorithm

Event Type
Seminar/Symposium
Sponsor
Decision and Control Laboratory, Coordinated Science Laboratory
Location
141 CSL
Date
Sep 30, 2013   2:00 - 3:00 pm  
Speaker
Dr. Nikolaos Freris, EPFL
Contact
Jana Lenz
E-Mail
janalenz@illinois.edu
Phone
217-244-1654
Views
813

Decision and Control Lecture Series

Decision and Control Laboratory, Coordinated Science Laboratory

 

Randomized Kaczmarz algorithm

 

Nikolaos Freris

 

Senior Research Scientist, Audiovisual Communications Lab (LCAV) Ecole Polytecnique Federale de Lausanne (EPFL)

 

 Monday, September 30, 2013

2:00 p.m. to 3:00 p.m.

141 CSL

________________________________________________________________________________________________________________________________________________________________________

Abstract

We propose and analyze a randomized iterative variant of the popular Kaczmarz algorithm for solving large-scale linear systems. The scheme features exponential convergence in the m.s to the minimum-norm least-squares solution of a given linear system of equations. The expected number of arithmetic operations is proportional to the squared condition number of the system multiplied by the number of non-zero entries of the input matrix. We experimentally test the performance against the vastly mature literature of state-of-art linear solvers and showcase improvements.

 

In sensor networks, we study the problem of estimation from noisy relative measure-ments, i.e., differences of nodal values across edges. We use Randomized Kaczmarz to design and analyze a new class of distributed asynchronous consensus algorithms, and analyze the convergence rate depending solely on properties of the network topology. Inspired by the analytical insights, we propose Randomized Kaczmarz Over-smoothing (RKO), which has demonstrated, in both theory and simulations, improvement over existing protocols in terms of both convergence speed-up and energy savings.

 

(This is joint work with A. Zouzias)

 

Biography

Nikolaos M. Freris received the Diploma in Electrical and Computer Engineering from the National Technical University of Athens, Greece in 2005 and the M.S. degree in Electrical and Computer Engineering, the M.S. degree in Mathematics, and the Ph.D. degree in Electrical and Computer Engineering all from the University of Illinois at Urbana-Champaign in 2007, 2008, and 2010, respectively. He is currently a senior research scientist at the Audiovisual Communications Laboratory (LCAV) in Ecole Polytecnique Federale de Lausanne (EPFL). From 2010-2012, he was a postdoctorate researcher in IBM Research - Zurich, Switzerland. His research interests span the areas of control, wireless and sensor networks, signal processing and data mining with provable guarantees. Dr. Freris is a member of IEEE, SIAM and the Technical Chamber of Greece.

link for robots only