A trick for creating convex envelopes

The convex envelope of a function is its best convex approximation. Convex envelopes are important because they permit to approximate hard nonconvex optimization problems by easy convex ones. However, creating convex envelopes is more of an art than a science. In this talk, I reveal a trick for creating convex envelopes and illustrate with examples in signal reconstruction with sparse, gaussian, and markov priors. Those examples have been obtained by different researchers with different approaches, but I will use the trick to rederive them in a unified manner, thus exposing the method behind the magic.

João Xavier

João Xavier is a researcher at the Instituto de Sistemas e Robótica (ISR), Lisbon, and a professor of Electrical and Computer Engineering at the Instituto Superior Técnico (IST). His current research interests focus on distributed signal processing for networks of cooperative agents. Using tools from optimization, dynamical systems and probability, he aims to: (1) understand the fundamental performance limits on detection and estimation, imposed by network topology and communication protocols; (2) investigate how network deterministic behaviors emerge from random local interactions; and (3) design resource-efficient algorithms to serve key decentralized applications as network localization, cognitive radio, and large-scale collaborative learning.ISR