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.