caa a22 4500 605478384 CHVBK 20210128100405.0 cr unu---uuuuu 210128e20150901xx s 000 0 eng 10.1007/s10994-015-5511-2 doi (NATIONALLICENCE)springer-10.1007/s10994-015-5511-2 Convex relaxations of penalties for sparse correlated variables with bounded total variation [Elektronische Daten] [Eugene Belilovsky, Andreas Argyriou, Gaël Varoquaux, Matthew Blaschko] We study the problem of statistical estimation with a signal known to be sparse, spatially contiguous, and containing many highly correlated variables. We take inspiration from the recently introduced k-support norm, which has been successfully applied to sparse prediction problems with correlated features, but lacks any explicit structural constraints commonly found in machine learning and image processing. We address this problem by incorporating a total variation penalty in the k-support framework. We introduce the (k,s) support total variation norm as the tightest convex relaxation of the intersection of a set of sparsity and total variation constraints. We show that this norm leads to an intractable combinatorial graph optimization problem, which we prove to be NP-hard. We then introduce a tractable relaxation with approximation guarantees that scale well for grid structured graphs. We devise several first-order optimization strategies for statistical parameter estimation with the described penalty. We demonstrate the effectiveness of this penalty on classification in the low-sample regime, classification with M/EEG neuroimaging data, and image recovery with synthetic and real data background subtracted image recovery tasks. We extensively analyse the application of our penalty on the complex task of identifying predictive regions from low-sample high-dimensional fMRI brain data, we show that our method is particularly useful compared to existing methods in terms of accuracy, interpretability, and stability. The Author(s), 2015 Structured sparsity nationallicence Feature selection nationallicence Brain decoding nationallicence k -Support nationallicence Total variation nationallicence Belilovsky Eugene Inria Saclay, Palaiseau, France aut Argyriou Andreas Inria Saclay, Palaiseau, France aut Varoquaux Gaël Inria Saclay, Palaiseau, France aut Blaschko Matthew Inria Saclay, Palaiseau, France aut Machine Learning Springer US; http://www.springer-ny.com 100/2-3(2015-09-01), 533-553 0885-6125 100:2-3<533 2015 100 10994 https://doi.org/10.1007/s10994-015-5511-2 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-015-5511-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Belilovsky Eugene Inria Saclay, Palaiseau, France aut NATIONALLICENCE 700 1- Argyriou Andreas Inria Saclay, Palaiseau, France aut NATIONALLICENCE 700 1- Varoquaux Gaël Inria Saclay, Palaiseau, France aut NATIONALLICENCE 700 1- Blaschko Matthew Inria Saclay, Palaiseau, France aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 100/2-3(2015-09-01), 533-553 0885-6125 100:2-3<533 2015 100 10994