Exact RelaxatiOns for Sparse and low-rank optImizatiON – EROSION

Numerous problems in signal/image processing, statistics, and machine learning rely on the resolution of optimization problems with sparse or low-rank priors. These problems are very challenging to solve due to their combinatorial nature and can be considered as open to a large extent. Within this context, the promise of EROSION is to push the frontiers of sparse and low-rank optimization by combining the strengths of exact relaxations and local optimization. To that end, EROSION will focus on two high-level research objectives: 1) deriving exact relaxations of the targeted problem with the same global minimizers, less local minimizers and wider basin of attraction, and 2) developing initialization strategies that are guaranteed to lie within a basin of attraction of a global solution of the exact relaxation. Finally, these methodological developments will be applied to several signal processing and machine learning problems.