Abstract
We provide theory for the computation of convex envelopes of non-convex functionals including an ℓ2-term and use these to suggest a method for regularizing a more general set of problems. The applications are particularly aimed at compressed sensing and low-rank recovery problems, but the theory relies on results which potentially could be useful also for other types of non-convex problems. For optimization problems where the ℓ2-term contains a singular matrix, we prove that the regularizations never move the global minima. This result in turn relies on a theorem concerning the structure of convex envelopes, which is interesting in its own right. It says that at any point where the convex envelope does not touch the non-convex functional, we necessarily have a direction in which the convex envelope is affine.
Original language | English |
---|---|
Pages (from-to) | 66-84 |
Journal | Journal of Optimization Theory and Applications |
Volume | 183 |
Issue number | 1 |
Early online date | 2019 May 29 |
DOIs | |
Publication status | Published - 2019 |
Subject classification (UKÄ)
- Mathematical Sciences
Free keywords
- Convex envelope
- Fenchel conjugate
- Non-convex/non-smooth optimization
- Proximal hull
- Regularization