Convex and Non-convex Approaches for Low-dimensional Models

Volkan Cevher, EPFL, Switzerland, and Mário A. T. Figueiredo, University of Lisbon and Instituto de Telecomunicações, Portugal
Sun, Dec 15, 2013, 9:00 am - 12:00 pm

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.

Monitoring and Optimization for Smarter Power Grids

Georgios B. Giannakis, Dept. of Electrical and Computer Engr., Endowed Chair Prof. of Wireless Telecommunications, and Director of Digital Technology Center, University of Minnesota, USA
Sun, Dec 15, 2013, 1:30 pm - 4:30 pm

Abstract: The pressing need to modernize the aging power grid has culminated into the smart grid vision, which entails the widespread use of state-of-the-art sensing, control, and communication technologies. The deployment of these smart technologies calls for novel grid monitoring and optimization techniques. This tutorial focuses on how current research challenges in power grid monitoring and optimization can be addressed through signal processing, communications, and networking toolboxes. After an overview of fundamental power engineering concepts, a wide range of modern research topics will be presented, including power system state estimation, phasor measurement units, line outage identification, price and load forecasting, economic operation of power systems, demand response, electric vehicles, and renewable energy management.