Scientific Computation and Applied & Industrial Mathematics Seminar: Maryam Fazel

We consider models or signals with simultaneous structure, for example a matrix that is simultaneously sparse and low-rank. Our goal is to find suitable convex penalties that allow us to reconstruct such signals given random measurements and noisy observations.

Often penalties that promote each individual structure are known and yield an order-wise optimal number of measurements (e.g., \ell 1 norm for sparsity, nuclear norm for matrix rank), so it is reasonable to minimize a combination of such norms. We show that, surprisingly, if we use multi-objective optimization with the individual norms, then we can do no better (order-wise) in terms of required measurements than an algorithm that exploits only one of the structures. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation, not one that is a function of convex relaxations used for each structures.