Sparsity-Aware Adaptive Learning: A Set Theoretic Estimation Approach
Learning sparse models has been a topic at the forefront of research for the last ten years or so. Considerable effort has been invested in developing efficient schemes for the recovery of sparse signal/parameter vectors. However, most of these efforts have focused on batch processing, via the compressed sensing or sampling (CS) framework. It is only very recently that online/time-adaptive algorithms have been developed, where the training data are processed sequentially, and the sparse signal/system to be recovered has the freedom to be time-varying. Besides time variation, online schemes are becoming very popular in the context of Big Data applications, where processing as well as memory requirements for batch processing may become excessively large. Our stage of discussion will be that of set theoretic estimation. Instead of a single optimal point, we are searching for a set of solutions that are in agreement with the available information, which comprises a set of training points and a set of constraints. Each training point is associated with a convex set, built around concepts borrowed by the robust statistics loss functions family.
In its more "standard" formulation, the sparsity constraint is imposed via convex sets such as l_1 or weighted l_1 balls. The solution is searched in the intersection of all the previously mentioned sets, via the use of a sequence of projections on the respective convex sets. Both of the previous constraint sets are equivalent to a soft thresholding operation rule. Moreover, the interesting characteristic of the weighted l_1 ball approach is that it corresponds to an optimizing task with time varying constraints. Convergence proofs are established via the rich fixed point theory. The respective algorithms are of linear complexity with respect to the number of unknowns.
Beyond convex constraints, more recent methods are also discussed, where sparsity is imposed via mappings; these are inspired by generalized thresholding rules, which are associated with non-convex penalty functions. To this end, the existing theory had to be extended with a new concept, that of partially quasi-non-expansive mappings, whose fixed point is a union of subspaces; an object that lies at the heart of sparse model learning. This new family of sparsity promoting algorithms scales, also, linearly with the number of unknowns.
The presentation will be based on geometric arguments by-passing a mathematical formulation path. Comparative results will be discussed with respect to other sparsity promoting algorithms, which build upon arguments based on regularization in the context of the LMS and RLS-type schemes. Moreover, versions of our novel algorithms for distributed learning will be presented and their relative merits will be discussed.
Joint work with Prof. K. Slavakis, Dr Y. Kopsinis, Dr S. Chouvardas
Sergios Theodoridis is currently Professor of Signal Processing and Communications in the Department of Informatics and Telecommunications of the University of Athens. His research interests lie in the areas of Adaptive Algorithms and Communications, Machine Learning and
Pattern Recognition, Signal Processing for Audio Processing and Retrieval. He is the co-editor of the book "Efficient Algorithms for Signal Processing and System Identification", Prentice Hall 1993, the co-author of the best selling book "Pattern Recognition", Academic Press, 4th ed. 2008, the co-author of the book "Introduction to Pattern Recognition: A MATLAB Approach", Academic Press, 2009, and the co-author of three books in Greek, two of them for the Greek Open University. He is Editor-in-Chief for the Signal Processing Book Series, Academic Press and for the E-Reference Signal Processing, Elsevier. He is the co-author of six papers that have received best paper awards including the 2009 IEEE Computational Intelligence Society Transactions on Neural Networks Outstanding paper Award. He has served as an IEEE Signal Processing Society Distinguished Lecturer. He was Otto Monstead Guest Professor, Technical University of Denmark, 2012, and holder of the Excellence Chair, Dept. of Signal Processing and Communications, University Carlos III, Madrid, Spain, 2011.
He was the general chairman of EUSIPCO-98, the Technical Program co-chair for ISCAS-2006 and ISCAS-2013, and co-chairman and co-founder of CIP-2008 and co-chairman of CIP-2010. He has served as President of the European Association for Signal Processing (EURASIP) and as member of the Board of Governors for the IEEE CAS Society. He currently serves as member of the Board of Governors (Member-at-Large) of the IEEE SP Society. He has served as a member of the Greek National Council for Research and Technology and he was Chairman of the SP advisory committee for the Edinburgh Research Partnership (ERP). He has served as vice chairman of the Greek Pedagogical Institute and he was for four years member of the Board of Directors of COSMOTE (the Greek mobile phone operating company). He is Fellow of IET, a Corresponding Fellow of the Royal Society of Edinburgh (RSE), a Fellow of EURASIP and a Fellow of IEEE.