Tutorial 11: Convex and non-convex approaches for low-dimensional models
Presented by
Volkan Cevher, Mário Figueiredo
Abstract
Many natural and man-made signals can be well modeled as having a few degrees of freedom relative to their "size"/"dimension", due to natural parameterizations or constraints; examples range from the classical band-limited signals that have been studied for many decades, to collections of video and acoustic signals observed from multiple viewpoints and locations in a network-of-sensors and to internet "signals" generated with limited network connectivity. The inherent low-dimensional structure of such signals may be mathematically modeled via combinatorial and/or geometric concepts, such as sparsity, unions-of-subspaces, manifolds, or mixtures of factor analyzers, and are revolutionizing the way we address inverse problems (e.g., signal recovery, parameter estimation, or structure learning) from dimensionality-reduced or incomplete data.
Addressing inverse problems by using a low dimensional model (LDM) to arbitrate the solution among infinitely many possible candidates for the unknown signal (i.e., as a prior, in Bayesian terms) typically leads to optimization problems with exponential complexity. Surprisingly, convex relaxations of specific LDM (priors) produce solutions that are provably close to (or even exactly the same as) an exhaustive search result, at the cost of a slight penalty in the number of required observations. For example, theoretically, using the 1-norm or the nuclear-norm is analogous to seeking the sparsest solution in compressive sensing (CS) or finding the minimum rank solution in matrix completion (MC), respectively, both known to be NP-hard problems. Unfortunately, many other interesting LDMs are intrinsically combinatorial and cannot be "convexified" (or can only be approximated up to constant factors). Such problems require explicitly combinatorial approximation algorithms that can go beyond simple LDM selection heuristics towards provable solution quality as well as runtime/space bounds.
Speaker Biography
Volkan Cevher received the B.Sc. degree (valedictorian) in electrical engineering from Bilkent University, Ankara, Turkey, in 1999, and the Ph.D. degree in electrical and computer engineering from the Georgia Institute of Technology, Atlanta, in 2005. He held research scientist positions at the University of Maryland, College Park, during 2006-2007 and at Rice University, Houston, TX, during 2008-2009. Currently, he is an Assistant Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include signal processing theory, machine learning, graphical models, and information theory. Dr. Cevher received a Best Paper Award at SPARS in 2009 and an ERC StG in 2011.
Mário Figueiredo received EE, MSc, PhD, and "Agregado" degrees in electrical and computer engineering, from Instituto Superior Técnico (IST), Technical University of Lisbon (TULisbon), Portugal, in 1985, 1990, 1994, and 2004, respectively. Since 1994, he has been with the faculty of the Department of Electrical and Computer Engineering, IST, where he is now a Full Professor, as well as area coordinator at Instituto de Telecomunicações. M. Figueiredo is a Fellow of the IEEE and of the IAPR and was (2005-2010) a member of the Image, Video, and Multidimensional Signal Processing Technical Committee of the IEEE Signal Processing Society. His current scientific interests include signal/image processing, statistical learning, information theory, and optimization. He is/was associate editor of several journals: IEEE Transactions on Image Processing, IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transactions on Mobile Computing, Pattern Recognition Letters, Signal Processing, and Statistics and Computing. He was guest co-editor of special issues of several IEEEjournals, co-chair of several workshops, and member of program or technical committees of many international conferences.