×

zbMATH — the first resource for mathematics

A continuous relaxation of the constrained \(\ell_2-\ell_0\) problem. (English) Zbl 07363956
Summary: We focus on the minimization of the least square loss function under a \(k\)-sparse constraint encoded by a \(\ell_0\) pseudo-norm. This is a non-convex, non-continuous and NP-hard problem. Recently, for the penalized form (sum of the least square loss function and a \(\ell_0\) penalty term), a relaxation has been introduced which has strong results in terms of minimizers. This relaxation is continuous and does not change the global minimizers, among other favorable properties. The question that has driven this paper is the following: can a continuous relaxation of the \(k\)-sparse constraint problem be developed following the same idea and same steps as for the \(penalized \ell_2-\ell_0\) problem? We calculate the convex envelope of the constrained problem when the observation matrix is orthogonal and propose a continuous non-smooth, non-convex relaxation of the \(k\)-sparse constraint functional. We give some equivalence of minimizers between the original and the relaxed problems. The subgradient is calculated as well as the proximal operator of the new regularization term, and we propose an algorithm that ensures convergence to a critical point of the \(k\)-sparse constraint problem. We apply the algorithm to the problem of single-molecule localization microscopy and compare the results with well-known sparse minimization schemes. The results of the proposed algorithm are as good as the state-of-the-art results for the penalized form, while fixing the constraint constant is usually more intuitive than fixing the penalty parameter.
MSC:
68-XX Computer science
94-XX Information and communication theory, circuits
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, F.; Carlsson, M.; Olsson, C., Convex envelopes for fixed rank approximation, Optim. Lett., 11, 8, 1783-1795 (2017) · Zbl 1409.90145
[2] Bechensteen, A.; Blanc-Féraud, L.; Aubert, G., New \(l_2- l_0\) algorithm for single-molecule localization microscopy, Biomed. Opt. Express, 11, 2, 1153-1174 (2020)
[3] Beck, A.; Eldar, YC, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim., 23, 3, 1480-1509 (2013) · Zbl 1295.90051
[4] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[5] Betzig, E.; Patterson, GH; Sougrat, R.; Lindwasser, OW; Olenych, S.; Bonifacino, JS; Davidson, MW; Lippincott-Schwartz, J.; Hess, HF, Imaging intracellular fluorescent proteins at nanometer resolution, Science, 313, 5793, 1642-1645 (2006)
[6] Bi, S.; Liu, X.; Pan, S., Exact penalty decomposition method for zero-norm minimization based on mpec formulation, SIAM J. Sci. Comput., 36, 4, A1451-A1477 (2014) · Zbl 1306.65211
[7] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1, 459-494 (2014) · Zbl 1297.90125
[8] Bourguignon, S.; Ninin, J.; Carfantan, H.; Mongeau, M., Exact sparse approximation problems via mixed-integer programming: formulations and computational performance, IEEE Trans. Signal Process., 64, 6, 1405-1419 (2016) · Zbl 1412.94020
[9] Breiman, L., Better subset regression using the nonnegative garrote, Technometrics, 37, 4, 373-384 (1995) · Zbl 0862.62059
[10] Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., Simões, L.E.: Gradient sampling methods for nonsmooth optimization. arXiv preprint arXiv:1804.11003 (2018)
[11] Candes, EJ; 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
[12] Candes, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 5-6, 877-905 (2008) · Zbl 1176.94014
[13] Carlsson, M.: On convexification/optimization of functionals including an l2-misfit term. arXiv:1609.09378 [math] (2016)
[14] Carlsson, M., On convex envelopes and regularization of non-convex functionals without moving global minima, J. Optim. Theory Appl., 183, 1, 66-84 (2019) · Zbl 1425.49013
[15] Chahid, M.: Echantillonnage compressif appliqué à la microscopie de fluorescence et à la microscopie de super résolution. Ph.D. thesis, Bordeaux (2014)
[16] Clarke, FH, Optimization and Nonsmooth Analysis (1990), Philadelphia: SIAM, Philadelphia
[17] Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[18] Gazagnes, S., Soubies, E., Blanc-Féraud, L.: High density molecule localization for super-resolution microscopy using CEL0 based sparse approximation. In: 2017 IEEE 14th International Symposium on Biomedical Imaging (ISBI 2017), pp. 28-31. IEEE (2017)
[19] Hess, ST; Girirajan, TPK; Mason, MD, Ultra-high resolution imaging by fluorescence photoactivation localization microscopy, Biophys. J., 91, 11, 4258-4272 (2006)
[20] Larsson, V.; Olsson, C., Convex low rank approximation, Int. J. Comput. Vis., 120, 2, 194-214 (2016) · Zbl 1398.68586
[21] Li, H., Lin, Z.: Accelerated proximal gradient methods for nonconvex programming. In: Advances in Neural Information Processing Systems, pp. 379-387 (2015)
[22] Lu, Z.; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 4, 2448-2478 (2013) · Zbl 1295.90056
[23] Mallat, SG; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 12, 3397-3415 (1993) · Zbl 0842.94004
[24] Mordukhovich, BS; Nam, NM, An easy path to convex analysis and applications, Synth. Lect. Math. Stat., 6, 2, 1-218 (2013)
[25] Nikolova, M., Relationship between the optimal solutions of least squares regularized with \(\ell_0\)-norm and constrained by k-sparsity, Appl. Comput. Harmonic Anal., 41, 1, 237-265 (2016) · Zbl 1338.90323
[26] Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, Vol. 1, pp. 40-44 (1993). doi:10.1109/ACSSC.1993.342465
[27] Peleg, D.; Meir, R., A bilinear formulation for vector sparsity optimization, Signal Process., 88, 2, 375-389 (2008) · Zbl 1186.94273
[28] Pilanci, M.; Wainwright, MJ; El Ghaoui, L., Sparse learning via Boolean relaxations, Math. Program., 151, 1, 63-87 (2015) · Zbl 1328.90106
[29] Rockafellar, RT; Wets, RJB, Variational Analysis (2009), Berlin: Springer, Berlin · Zbl 0888.49001
[30] Rust, MJ; Bates, M.; Zhuang, X., Sub-diffraction-limit imaging by stochastic optical reconstruction microscopy (STORM), Nat. Methods, 3, 10, 793-796 (2006)
[31] Sage, D.; Kirshner, H.; Pengo, T.; Stuurman, N.; Min, J.; Manley, S.; Unser, M., Quantitative evaluation of software packages for single-molecule localization microscopy, Nat. Methods, 12, 8, 717 (2015)
[32] Sage, D.; Pham, TA; Babcock, H.; Lukes, T.; Pengo, T.; Chao, J.; Velmurugan, R.; Herbert, A.; Agrawal, A.; Colabrese, S., Super-resolution fight club: assessment of 2d and 3d single-molecule localization microscopy software, Nat. Methods, 16, 5, 387-395 (2019)
[33] Selesnick, I., Sparse regularization via convex analysis, IEEE Trans. Signal Process., 65, 17, 4481-4494 (2017) · Zbl 1414.94545
[34] Simon, B.: Trace Ideals and Their Applications, Vol. 120. American Mathematical Society, Philadelphia (2005) · Zbl 1074.47001
[35] Soubies, E.; Blanc-Féraud, L.; Aubert, G., A continuous exact \(\ell_0\) penalty (CEL0) for least squares regularized problem, SIAM J. Imaging Sci., 8, 3, 1607-1639 (2015) · Zbl 1325.65086
[36] Soubies, E.; Blanc-Féraud, L.; Aubert, G., A unified view of exact continuous penalties for \(\backslash\) ell_\(2- \backslash\) ell_0 minimization, SIAM J. Optim., 27, 3, 2034-2060 (2017) · Zbl 1375.65086
[37] Soussen, C.; Idier, J.; Brie, D.; Duan, J., From Bernoulli-Gaussian deconvolution to sparse signal restoration, IEEE Trans. Signal Process., 59, 10, 4572-4584 (2011) · Zbl 1392.94466
[38] Tono, K., Takeda, A., Gotoh, J.: Efficient dc algorithm for constrained sparse optimization. arXiv preprint arXiv:1701.08498 (2017) · Zbl 06869181
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.