Sparse Optimization Algorithms and Applications

In many applications of optimization, an exact solution is less useful than a simple, well structured approximate solution. An example is found in compressed sensing, where we prefer a sparse signal (e.g. containing few frequencies) that matches the observations well to a more complex signal that matches the observations even more closely. The need for simple, approximate solutions has a profound effect on the way that optimization problems are formulated and solved. Regularization terms can be introduced into the formulation to induce the desired structure, but such terms are often non-smooth and thus may complicate the algorithms. On the other hand, an algorithm that is too slow for finding exact solutions may become competitive and even superior when we need only an approximate solution. In this talk we outline the range of applications of sparse optimization, then sketch some techniques for formulating and solving such problems, with a particular focus on applications such as compressed sensing and data analysis.