GRETA

Over the past few years, many problems of automatically computing sparse representations of data have been addressed through convex optimization formulations. This holds both for contributions in machine learning and signal processing. However, aiming at sparsity actually involves an l0 “norm” regularization/constraint, and the convex optimization way is essentially a proxy to achieve this sparsity – through the recourse to an l1 norm, which itself is a proxy to the l0. In this project, we want to set the focus on another way of dealing with the sparsity objective, which, to our opinion, has been neglected recently: greedy methods. From a broad perspective, greedy algorithms constitute another way of approximating the solution of an l0 based problems and we think there is a lot of interesting questions that accompany the use of greedy methods. In particular, we will carry out our research along three different axis. First, we will devote time to develop new projection/matching pursuit-based algorithms, focusing on two specific points: on the one hand, we will be interested in making use of elaborate data structures and algorithms (e.g. kd-tree, hash tables, graph algorithms) to speed up matching pursuit learning, and, on the other hand, we will devise new pursuit algorithms capable of handling structured sparsity. Second, we aim at analyzing the properties of greedy methods in terms of generalization ability: results exist that establish conditions for (perfect) recoverability of the ’hidden’ or unobserved signal, but few exist that draw the connection with the generalization ability of the learned function – the question of using a loss function different from the squared error is one issue directly connected to this line of research. Finally, on a broader scope, we would like to elucidate some connections between pivotal quantities such as (mutual) incoherence, Babel function and spark that appear in the signal processing literature and VC-dimension, Rademacher complexities and algorithmic stability, which are notions widely used in machine learning. The former quantities are essential to prove results on recoverability while the latter play a central role to demonstrate the consistency of learning procedures: we anticipate that these notions are closely related and this is our purpose to precisely establish their connections.