On convexification/optimization of functionals including an l2-misfit term

We provide theory for computing the lower semi-continuous convex envelope of functionals of the type f(x) plus an l2 misfit, and discuss applications to various non-convex optimization problems. The latter term is a data fit term whereas f provides structural constraints on x. By minimizing the above expression, possibly with additional constraints, we thus find a tradeoff between matching the measured data and enforcing a particular structure on x, such as sparsity or low rank. For these particular cases, the theory provides alternatives to convex relaxation techniques such as l1 -minimization (for vectors) and nuclear norm-minimization (for matrices). For functionals where the l2 misfit includes a singular matrix and where the convex envelope usually is not explicitly computable, we provide theory for how minimizers of (explicitly computable) approximations of the convex envelope relate to minimizers of the original functional. In particular, we give explicit conditions on when the two coincide.