Geometry of Sparsity-Inducing Norms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910040589336576 |
|---|---|
| author | Chancelier, Jean-Philippe de Lara, Michel Deza, Antoine Pournin, Lionel |
| author_facet | Chancelier, Jean-Philippe de Lara, Michel Deza, Antoine Pournin, Lionel |
| contents | Sparse optimization seeks an optimal solution with few nonzero entries. To achieve this, it is common to add to the criterion a penalty term proportional to the $\ell_1$-norm, which is recognized as the archetype of sparsity-inducing norms. In this approach, the number of nonzero entries is not controlled a priori. By contrast, in this paper, our motivation is to find an optimal solution with at most~$k$ nonzero coordinates (or for short, $k$-sparse vectors), where $k$ is a given sparsity threshold (or ``sparsity budget''). For this purpose, we study the class of generalized $k$-support dual~norms that arise from any given so-called source norm. When added as a penalty term, we provide conditions under which such generalized $k$-support dual~norms promote $k$-sparse solutions. The result follows from an analysis of the exposed faces of closed convex sets generated by $k$-sparse vectors, and of how primal support identification can be deduced from dual information. Finally, we study some of the geometric properties of the unit balls for the $k$-support dual~norms and their dual norms when the source norm belongs to the family of $\ell_p$-norms. In particular, we show a striking structural property: every proper face of the unit balls for the $k$-support dual~norms is a hypersimplex, i.e., the convex hull of $0/1$-valued points with the same $\ell_0$-norm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08651 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometry of Sparsity-Inducing Norms Chancelier, Jean-Philippe de Lara, Michel Deza, Antoine Pournin, Lionel Optimization and Control Sparse optimization seeks an optimal solution with few nonzero entries. To achieve this, it is common to add to the criterion a penalty term proportional to the $\ell_1$-norm, which is recognized as the archetype of sparsity-inducing norms. In this approach, the number of nonzero entries is not controlled a priori. By contrast, in this paper, our motivation is to find an optimal solution with at most~$k$ nonzero coordinates (or for short, $k$-sparse vectors), where $k$ is a given sparsity threshold (or ``sparsity budget''). For this purpose, we study the class of generalized $k$-support dual~norms that arise from any given so-called source norm. When added as a penalty term, we provide conditions under which such generalized $k$-support dual~norms promote $k$-sparse solutions. The result follows from an analysis of the exposed faces of closed convex sets generated by $k$-sparse vectors, and of how primal support identification can be deduced from dual information. Finally, we study some of the geometric properties of the unit balls for the $k$-support dual~norms and their dual norms when the source norm belongs to the family of $\ell_p$-norms. In particular, we show a striking structural property: every proper face of the unit balls for the $k$-support dual~norms is a hypersimplex, i.e., the convex hull of $0/1$-valued points with the same $\ell_0$-norm. |
| title | Geometry of Sparsity-Inducing Norms |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.08651 |