Decision and Control Lecture Series
Decision and Control Laboratory, Coordinated Science Laboratory
Randomized Kaczmarz algorithm
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.
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)
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.