報告題目：A Linearly Convergent Double Stochastic Gauss-Seidel Algorithm for Linear Systems

報告人：羅智泉 教授 （香港中文大學深圳）

報告時間：2018年5月2日下午14:40-15:40

地點：X2511

歡迎光臨！

信息與計算科學系

報告摘要：

In this talk, we propose a double stochastic Gauss-Seidel (G-S) type algorithm for solving a linear system of equations Ax = b. Although it is generally known that the G-S scheme and many of its variants diverge when A is neither diagonal dominant nor symmetric positive definite, we show a positive result: with a random choice of equations and variables, the (over relaxed) G-S algorithm converges globally linearly (in expectation) for any feasible linear systems of equations. The key in the algorithm

design is to introduce a nonuniform and double randomization rule for picking the equations and the variables in each update step. Our analysis also generalizes to certain iterative alternating projection algorithms for solving the linear inequality system Ax \le b with an arbitrary A. Our result demonstrates that properly introducing randomization can ensure global linear convergence of an (otherwise divergent) G-S type algorithm for arbitrary A.

This is a joint work with Mingyi Hong, Meisam Razaviyayn, Navid Reyhanian.

個人簡介：

ZHI-QUAN TOM LUO (F) received his B.Sc, Applied Mathematics, from Peking University in 1984 and PhD in Operations Research from MIT in 1989. He was with the McMaster University, Canada, from 1989 to 2003, where he served as the Head of the ECE Department and held a Canada Research Chair in Information Processing. He has been with the ECE Department at the University of Minnesota (Twin Cities), since 2003-present (on leave). He is Vice President (Academic) and Professor of School of Science and Engineering, the Chinese University of Hong Kong (Shenzhen) (2014-present). He is also concurrently serving as the founding director of the Shenzhen Research Institute of Big Data. His research interests lie in optimization algorithms for signal processing, data analytics and digital communication.

Dr. Luo is a recipient of the 2004, 2009 and 2011 IEEE SPS Best Paper Award, the 2015 IEEE SPS Best Magazine Paper Award, the 2011 EURASIP Best Paper Award and the 2011 ICC Best Paper Award. He was awarded the 2010 Farkas Prize from the INFORMS Optimization Society.

Prof. Luo is a Fellow of IEEE and SIAM. His professional activities include: Editor-in-Chief, IEEE Transactions on Signal Processing (2012-2014); Editorial Board Member, IEEE Signal Processing Magazine (2009-2012) and IEEE Journal of Selected Topics of Signal Processing (2013-Present); Associate Editor, Mathematics of Operations Research, INFORMS, (2007-Present) and Management Sciences (2009-Present); Member/Vice Chair/Chair/Past Chair, SPS Signal Processing for Communications and Networking Technical Committee (2005-2013) and Member, SPS Publications Board (2012-present); Associate Editor, IEEE Transactions on Signal Processing (2000-2004) and SIAM Journal on Optimization (1998-2005); Member, SPS Signal Processing Theory and Methods Technical Committee (2006-2009); Member, SPS Technical Directions Board (2010-2012); 2004 ICASSP tutorial lecturer, 2009 ICASSP area overview speaker; Plenary speaker, 2013 IEEE SPAWC Workshop and 2014 IEEE Comm. Theory Workshop; Semi-plenary speaker, 2011 IEEE Conference on Decision and Control.

He is elected to the Royal Society of Canada (highest distinction for a Canadian scientist) for influential contributions to optimization algorithms and their applications in signal processing, communications. He also received the 2010 Farkas Prize from the INFORMS Optimization Society for outstanding contributions to the field of ptimization. He is elected to SIAM Fellow in 2011 for the development of novel applied mathematics ideas and methods for signal processing and digital communication.