×

On convex envelopes and regularization of non-convex functionals without moving global minima. (English) Zbl 1425.49013

Summary: We provide theory for the computation of convex envelopes of non-convex functionals including an \(\ell ^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 \(\ell ^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.

MSC:

49M20 Numerical methods of relaxation type
65K10 Numerical optimization and variational techniques
90C26 Nonconvex programming, global optimization

Software:

SCAT; PDCO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[2] Donoho, D.L.: For most large underdetermined systems of linear equations the minimal \[\ell^1\] ℓ1-norm solution is also the sparsest solution. Commun. Pure Appl. Math. 59(6), 797-829 (2006) · Zbl 1113.15004 · doi:10.1002/cpa.20132
[3] Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203-4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[4] Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Stanford University (2002)
[5] Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[6] Carlsson, M., Gerosa, D., Olsson, C.: A un-biased approach to compressed sensing. arXiv preprint arXiv:1806.05283 (2018) · Zbl 1458.94080
[7] Larsson, V., Olsson, C.: Convex low rank approximation. Int. J. Comput. Vis. 120, 194-214 (2016) · Zbl 1398.68586 · doi:10.1007/s11263-016-0904-7
[8] Soubies, E., Blanc-Féraud, L., Aubert, G.: A continuous exact \[\ell_0\] ℓ0 penalty (CEL0) for least squares regularized problem. SIAM J. Imaging Sci. 8(3), 1607-1639 (2015) · Zbl 1325.65086 · doi:10.1137/151003714
[9] Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Program. 125(2), 263-295 (2010) · Zbl 1207.65084 · doi:10.1007/s10107-010-0394-2
[10] Andersson, F., Carlsson, M., Olsson, C.: Convex envelopes for fixed rank approximation. Optim. Lett. 11(8), 1783-1795 (2017) · Zbl 1409.90145 · doi:10.1007/s11590-017-1146-5
[11] Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[12] Carlsson, M.: On convexification/optimization of functionals including an L2-misfit term. arXiv preprint arXiv:1609.09378 (2016)
[13] Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[14] Lucet, Y.: The Legendre-Fenchel transform and the convex Hull of a function: fast computational algorithms. Second-order smoothness and analysis, Ph.D. thesis (1997)
[15] Brøndsted, A.: Milman’s theorem for convex functions. Math. Scand. 19, 5-10 (1966) · Zbl 0162.44201 · doi:10.7146/math.scand.a-10790
[16] Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward – backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137(1-2), 91-129 (2013) · Zbl 1260.49048 · doi:10.1007/s10107-011-0484-9
[17] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, vol. 317. Springer, Berlin (2009) · Zbl 0888.49001
[18] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7
[19] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)
[20] Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry, vol. 36. Springer, Berlin (2013) · Zbl 0633.14016
[21] Moreau, J.J.: Inf-convolutions, sous-additivé, convexité des fonctions numériques. J. Math. Pures Appl. 49, 109-154 (1970) · Zbl 0195.49502
[22] Weiss, E.A.: Konjugierte funktionen. Archiv Math. 20(5), 538-545 (1969) · Zbl 0191.48702 · doi:10.1007/BF01899461
[23] Poliquin, R.: Subgradient monotonicity and convex functions. Nonlinear Anal. Theory Methods Appl. 14(4), 305-317 (1990) · Zbl 0742.49013 · doi:10.1016/0362-546X(90)90167-F
[24] Lucet, Y.: What shape is your conjugate? A survey of computational convex analysis and its applications. SIAM Rev. 52(3), 505-542 (2010) · Zbl 1197.65072 · doi:10.1137/100788458
[25] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I convex underestimating problems. Math. Program. 10(1), 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[26] Borwein, J.M., Hamilton, C.H.: Symbolic Fenchel conjugation. Math. Program. 116(1-2), 17-35 (2009) · Zbl 1158.90007 · doi:10.1007/s10107-007-0134-4
[27] Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math. Program. 103(2), 207-224 (2005) · Zbl 1099.90045 · doi:10.1007/s10107-005-0580-9
[28] Brighi, B., Chipot, M.: Approximated convex envelope of a function. SIAM J. Numer. Anal. 31(1), 128-148 (1994) · Zbl 0796.65009 · doi:10.1137/0731007
[29] Hare, W., Sagastizábal, C.: Computing proximal points of nonconvex functions. Math. Program. 116(1-2), 221-258 (2009) · Zbl 1168.90010 · doi:10.1007/s10107-007-0124-6
[30] Attouch, H., Azé, D.: Approximation and regularization of arbitrary functions in Hilbert spaces by the Lasry-Lions method. Ann. l’IHP Anal. Non linéaire 10, 289-312 (1993) · Zbl 0780.41021 · doi:10.1016/S0294-1449(16)30214-1
[31] Strömberg, T.: On regularization in Banach spaces. Ark. Mat. 34(2), 383-406 (1996) · Zbl 0873.49028 · doi:10.1007/BF02559552
[32] Lasry, J.M., Lions, P.L.: A remark on regularization in Hilbert spaces. Isr. J. Math. 55(3), 257-266 (1986) · Zbl 0631.49018 · doi:10.1007/BF02765025
[33] Bauschke, H.H., Goebel, R., Lucet, Y., Wang, X.: The proximal average: basic theory. SIAM J. Optim. 19(2), 766-785 (2008) · Zbl 1172.26003 · doi:10.1137/070687542
[34] Hare, W.L.: A proximal average for nonconvex functions: a proximal stability perspective. SIAM J. Optim. 20(2), 650-666 (2009) · Zbl 1206.26019 · doi:10.1137/07070913X
[35] Goebel, R.: Self-dual smoothing of convex and saddle functions. J. Convex Anal. 15(1), 179 (2008) · Zbl 1142.26010
[36] Olsson, C., Carlsson, M., Andersson, F., Larsson, V.: Non-convex rank/sparsity regularization and local minima. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 332-340 (2017)
[37] Caprani, J., Carlsson, M.: Quadratic envelope regularization for structured low rank approximation. In: ICASSP Proceedings (2019)
[38] Andersson, F., Carlsson, M., Wendt, H.: On a fixed-point algorithm for structured low-rank approximation and estimation of half-life parameters. In: 2016 24th European Signal Processing Conference (EUSIPCO), pp. 326-330. IEEE (2016)
[39] Andersson, F., Carlsson, M.: Fixed-point algorithms for frequency estimation and structured low rank approximation. Appl. Comput. Harmon. Anal. 46, 40-65 (2017) · Zbl 1475.65043 · doi:10.1016/j.acha.2017.03.004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.