Loading Events

« All Events

  • This event has passed.

CESG Fishbowl Seminar: Randomized Kaczmarz algorithm

October 7, 2013 @ 4:00 pm - 5:00 pm

Room 333 (fishbowl)

Nikolaos M. Freris
Senior Researcher in École Polytecnique Fédérale de Lausanne (EPFL)

Abstract:
We propose and analyze a randomized iterative variant of 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 linear solvers and showcase improvements.

In sensor networks, we study the problem of estimation from noisy relative measurements, 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 leading protocols in terms of both convergence speed-up and energy savings.

Keywords: Randomized algorithms, Distributed algorithms, Consensus, Wireless Sensor Networks.

Bio
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 researcher in École Polytecnique Fédérale 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. He was a recipient of IBM invention achievement award, in 2011, and the Gerondelis and Vodafone fellowships for graduate studies. Dr. Freris is a member of IEEE, SIAM and the Technical Chamber of Greece.

Host: Dr. Kumar

Details

Date:
October 7, 2013
Time:
4:00 pm - 5:00 pm