Capra-Convexity, Convex Factorization and Variational Formulations for the ℓ0 Pseudonorm
Tóm tắt
The so-called ℓ0 pseudonorm, or cardinality function, counts the number of nonzero components of a vector. In this paper, we analyze the ℓ0 pseudonorm by means of so-called Capra (constant along primal rays) conjugacies, for which the underlying source norm and its dual norm are both orthant-strictly monotonic (a notion that we formally introduce and that encompasses the ℓp-norms, but for the extreme ones). We obtain three main results. First, we show that the ℓ0 pseudonorm is equal to its Capra-biconjugate, that is, is a Capra-convex function. Second, we deduce an unexpected consequence, that we call convex factorization: the ℓ0 pseudonorm coincides, on the unit sphere of the source norm, with a proper convex lower semicontinuous function. Third, we establish a variational formulation for the ℓ0 pseudonorm by means of generalized top-k dual norms and k-support dual norms (that we formally introduce).
Tài liệu tham khảo
Akian, M., Gaubert, S., Kolokoltsov, V.: Invertibility of functional Galois connections. Comptes Rendus Mathematique 335(11), 883–888 (2002)
Argyriou, A., Foygel, R., Srebro, N.: Sparse Prediction with the K-Support Norm. In: Proceedings of the 25th International Conference on Neural Information Processing Systems - vol. 1, NIPS’12, pp 1457–1465. Curran Associates Inc, USA (2012)
Bhatia, R.: Matrix Analysis. Springer, New York (1997)
Chancelier, J.-P., De Lara, M.: Constant along primal rays conjugacies and the ℓ0 pseudonorm. Optimization 0(0), 1–32 (2020)
Chancelier, J.-P., De, M.: Lara. Hidden convexity in the ℓ0 pseudonorm. J. Convex Anal. 28(1), 203–236 (2021)
Fan, Z., Jeong, H., Sun, Y., Friedlander, M.P.: Atomic decomposition via polar alignment. Foundations and Trends\(^{{\circledR }},\) in Optimization 3(4), 280–366 (2020)
Gries, D.: Characterization of certain classes of norms. Numer. Math. 10, 30–41 (1967)
Gries, D., Stoer, J.: Some results on fields of values of a matrix. SIAM J. Numer. Anal. 4(2), 283–300 (1967)
Hiriart-Urruty, J.-B., Le, H.: A variational approach of the rank function. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research 21(2), 207–240 (2013)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vol. I. Springer, Berlin (1993)
Marques de Sà, E., Sodupe, M.-J.: Characterizations of *orthant-monotonic norms. Linear Algebra Appl. 193, 1–9 (1993)
Martínez-Legaz, J.E.: Generalized convex duality and its economic applications. In: Hadjisavvas, S.S., Komlósi S, N. (eds.) Handbook of Generalized Convexity and Generalized Monotonicity. Nonconvex Optimization and Its Applications, vol. 76, pp 237–292. Springer (2005)
McDonald, A.M., Pontil, M., Stamos, D.: New perspectives on k-support and cluster norms. J. Mach. Learn. Res. 17(155), 1–38 (2016)
Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. Q. J. Math. 11(1), 50–59 (1960)
Moreau, J.J.: Inf-convolution, sous-additivité, convexité des fonctions numériques. J. Math. Pures Appl. (9) 49, 109–154 (1970)
Nikolova, M.: Relationship between the optimal solutions of least squares regularized with l0-norm and constrained by k-sparsity. Appl. Comput. Harmon. Anal. 41(1), 237–265 (2016)
Obozinski, G., Bach, F.: A unified perspective on convex structured sparsity Hierarchical, symmetric, submodular norms and beyond. Preprint (2016)
Rockafellar, R.T.: Conjugate Duality and Optimization CBMS-NSF regional conference series in applied mathematics society for industrial and applied mathematics (1974)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Rockafellar, T.R.: Convex Analysis. Princeton University Press, Princeton (1970)
Rubinov, A.: Abstract convexity and global optimization, vol. 44 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2000)
Singer, I.: Abstract Convex Analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, New York (1997)
Tono, K., Takeda, A., Gotoh, J.-Y.: Efficient DC algorithm for constrained sparse optimization. Preprint (2017)