Abstract

The so-called ℓ0\ell_0 pseudonorm on the Euclidean space Rd\mathbb{R}^d counts the number of nonzero components of a vector. We say that a sequence of norms is strictly increasingly graded (with respect to the ℓ0\ell_0 pseudonorm) if it is nondecreasing and that the sequence of norms of a vector xx becomes stationary exactly at the index ℓ0(x)\ell_0(x). In this paper, with any (source) norm, we associate sequences of generalized top-kk and kk-support norms, and we also introduce the new class of orthant-strictly monotonic norms (that encompasses the ℓp\ell_p norms, but for the extreme ones). Then, we show that an orthant-strictly monotonic source norm generates a sequence of generalized top-kk norms which is strictly increasingly graded. With this, we provide a systematic way to generate sequences of norms with which the level sets of the ℓ0\ell_0 pseudonorm are expressed by means of the difference of two norms. Our results rely on the study of orthant-strictly monotonic norms.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • ℓ0 pseudonorm
  • orthant-strictly monotonic norm
  • generalized top-k norm
  • generalized k-support norm
  • strictly graded sequence of norms

Mathematics Subject Classification

15A60, 46N10

References

  1. C. D. Aliprantis, K. C. Border: Infinite Dimensional Analysis, 2nd ed., Springer, Berlin (1999).https://doi.org/10.1007/978-3-662-03961-8Google Scholar
  2. A. Argyriou, R. Foygel, N. Srebro: Sparse prediction with the k-support norm, in: Proc. 25th Int. Conf. on Neural Information Processing Systems, Vol. 1, Lake Tahoe, Curran Associates, Red Hook (2012) 1457–1465.Google Scholar
  3. F. L. Bauer, J. Stoer, C. Witzgall: Absolute and monotonic norms, Numer. Math. 3 (1961) 257–264.https://doi.org/10.1007/BF01386026Google Scholar
  4. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., CMS Books in Mathematics, Springer, Berlin (2017:https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  5. R. Bhatia: Matrix Analysis, Graduate Texts in Mathematics 169, Springer, New York (1997).https://doi.org/10.1007/978-1-4612-0653-8Google Scholar
  6. G. Birkhoff: Orthogonality in linear metric spaces, Duke Math. J. 1/2 (1935) 169–172.https://doi.org/10.1215/S0012-7094-35-00115-6Google Scholar
  7. J.-P. Chancelier, M. De Lara: Hidden convexity in the l0 pseudonorm, J. Convex Analysis 28/1 (2021) 203–236.https://doi.org/10.68381/jca28015Google Scholar
  8. J.-P. Chancelier, M. De Lara: Capra-convexity, convex factorization and variational formulations for the l0 pseudonorm, Set-Valued Var. Analysis 30 (2022) 597–619.https://doi.org/10.1007/s11228-021-00606-zGoogle Scholar
  9. J.-P. Chancelier, M. De Lara: Constant along primal rays conjugacies and the l0 pseudonorm, Optimization 71/2 (2022) 355–386.https://doi.org/10.1080/02331934.2020.1822836Google Scholar
  10. Z. Fan, H. Jeong, Y. Sun, M. P. Friedlander: Atomic decomposition via polar alignment, Found. Trends Optimization 3/4 (2020) 280–366.https://doi.org/10.1561/2400000028Google Scholar
  11. J.-y. Gotoh, A. Takeda, K. Tono: Efficient DC algorithm for constrained sparse optimization, Math. Program. 169/1 (2018) 141–176.https://doi.org/10.1007/s10107-017-1181-0Google Scholar
  12. D. Gries: Characterization of certain classes of norms, Numer. Math. 10 (1967) 30–41.https://doi.org/10.1007/BF02165157Google Scholar
  13. D. Gries, J. Stoer: Some results on fields of values of a matrix, SIAM J. Numer. Analysis 4/2 (1967) 283–300.https://doi.org/10.1137/0704026Google Scholar
  14. J.-B. Hiriart-Urruty: Optimisation et Analyse Convexe, Presses Universitaires de France, Paris (1998).Google Scholar
  15. E. Marques de Sà, M.-J. Sodupe: Characterizations of *orthant-monotonic norms, Linear Algebra Appl. 193 (1993) 1–9.https://doi.org/10.1016/0024-3795(93)90267-RGoogle Scholar
  16. A. M. McDonald, M. Pontil, D. Stamos: New perspectives on k-support and cluster norms, J. Machine Learning Res. 17/155 (2016) 1–38.Google Scholar
  17. L. Mirsky: Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. 11/1 (1960) 50–59.https://doi.org/10.1093/qmath/11.1.50Google Scholar
  18. G. Obozinski, F. Bach: A unified perspective on convex structured sparsity: Hierarchical, symmetric, submodular norms and beyond, preprint (2016).Google Scholar
  19. K. Paul, D. Sain, K. Jha: On strong orthogonality and strictly convex normed linear spaces, J. Inequal. Appl. (2013), art. no. 242, 7 pp.https://doi.org/10.1186/1029-242X-2013-242Google Scholar
  20. T. R. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  21. D. Sain, K. Paul, K. Jha: Strictly convex space: Strong orthogonality and conjugate diameters, J. Convex Analysis 22 (2015) 1215–1225.https://doi.org/10.68381/jca22064Google Scholar
  22. K. Tono, A. Takeda, J.-y. Gotoh: Efficient DC algorithm for constrained sparse optimization, preprint (2017), published in revised form as [11].Google Scholar

Suggested citation

J.-P. Chancelier, M. De Lara. “Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the ℓ_0 Pseudonorm.” Journal of Convex Analysis 30 (2023), No. 3, 743–769. https://doi.org/10.68381/jca30036

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press.