
Sparse Support Recovery with Non-smooth Loss Functions
Degraux, Kévin; Peyré, Gabriel; Fadili, Jalal; Jacques, Laurent (2016), Sparse Support Recovery with Non-smooth Loss Functions, Advances in Neural Information Processing Systems (NIPS), Neural Information Processing Systems Foundation, Inc., p. 10
View/ Open
Type
Communication / ConférenceExternal document link
https://hal.archives-ouvertes.fr/hal-01658855Date
2016Conference title
Advances in Neural Information Processing Systems 29 (NIPS 2016)Conference date
2016-11Conference city
BarceloneConference country
SpainBook title
Advances in Neural Information Processing Systems (NIPS)Publisher
Neural Information Processing Systems Foundation, Inc.
Number of pages
10Pages
10
Metadata
Show full item recordAuthor(s)
Degraux, KévinInstitute of Information and Communication Technologies, Electronics and Applied Mathematics [ICTEAM]
Peyré, Gabriel
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Fadili, Jalal
Groupe de Recherche en Informatique, Image et Instrumentation de Caen [GREYC]
Jacques, Laurent
LTS2 - EPFL
Institute of Information and Communication Technologies, Electronics and Applied Mathematics [ICTEAM]
Abstract (EN)
In this paper, we study the support recovery guarantees of underdetermined sparse regression using the 1-norm as a regularizer and a non-smooth loss function for data fidelity. More precisely, we focus in detail on the cases of 1 and ∞ losses, and contrast them with the usual 2 loss. While these losses are routinely used to account for either sparse (1 loss) or uniform (∞ loss) noise models, a theoretical analysis of their performance is still lacking. In this article, we extend the existing theory from the smooth 2 case to these non-smooth cases. We derive a sharp condition which ensures that the support of the vector to recover is stable to small additive noise in the observations, as long as the loss constraint size is tuned proportionally to the noise level. A distinctive feature of our theory is that it also explains what happens when the support is unstable. While the support is not stable anymore, we identify an extended support " and show that this extended support is stable to small additive noise. To exemplify the usefulness of our theory, we give a detailed numerical analysis of the support stability/instability of compressed sensing recovery with these different losses. This highlights different parameter regimes, ranging from total support stability to progressively increasing support instability."Subjects / Keywords
Non-smooth Loss Functions; extended support; stability/instabilityRelated items
Showing items related by title and author.
-
Dossal, Charles; Fadili, Jalal; Peyré, Gabriel; Chabanol, Marie-Line (2012) Article accepté pour publication ou publié
-
Deledalle, Charles-Alban; Vaiter, Samuel; Peyré, Gabriel; Fadili, Jalal; Dossal, Charles (2012) Communication / Conférence
-
Salmon, Joseph; Deledalle, Charles-Alban; Vaiter, Samuel; Peyré, Gabriel; Fadili, Jalal (2013) Communication / Conférence
-
Fadili, Jalal; Peyré, Gabriel (2011) Communication / Conférence
-
Vaiter, Samuel; Fadili, Jalal; Peyré, Gabriel (2018) Article accepté pour publication ou publié