12 juin 2017

Catégorie : Post-doctorant

We offer a 2-year post-doctoral position (1 year renewable once) within the research center Inria in Rennes, France. The post-doc is granted by the French ANR project BECOSE (« BEyond COmpressive SEnsing : Sparse approximation algorithms for ill-conditioned inverse problems »). The post-doctoral topic is related to the analysis of greedy sparse recovery algorithms (See the “Scientific Context” section for more details). The post-doctoral fellow is expected to start between October 2017 and January 2018**. **The gross monthly salary is 2,621€.

You will join the Inria research center in Rennes, France (http://www.inria.fr/en/). Inria is the French National Institute for computer science and applied mathematics. Its goal is to promote“scientific excellence for technology transfer and society”. Inria has currently 2,700 employees graduated from the world’s top universities working in its labs. The post-doc will be supervised by Cédric Herzet, Rémi Gribonval and Charles Soussen (CRAN, Nancy).

You hold a PhD degree and have an outstanding academic record. You have solid knowledge in applied mathematics, and specifically in convex optimization, statistical analysis or greedy procedures. You have a good command of English as a working language.

The past decade has witnessed a tremendous interest in the concept of sparse representations in signal and image processing. One of the main reasons explaining this enthusiasm stands in the discovery of compressive sensing, a new sampling paradigm defying the theoretical limits established sixty years before by Shannon. Compressive sensing led many researchers to focus on inverse problems involving fairly-well conditioned dictionaries as those arising from random, independent measurements. Yet in many applications, the dictionaries relating the observations to the sought sparse signal are deterministic and ill-conditioned. As an extreme case of ill-conditioned setup, one can mention the “continuous” dictionaries recently considered in [1] where the atoms smoothly depend on some parameters taking their values in a continuous interval. In this scenario, many classical algorithms and theoretical analyses are likely to fail.

During the postdoc, we thus propose to revisit some well-known greedy procedures and their theoretical guarantees of success in the context of large-scale continuous dictionaries. The work will consist of finding proper solutions to adapt these procedures to a “continuous” setting and to characterize mathematically their behavior. Depending on the background of the candidate, several directions of investigation towards this goal may be foreseen. We mention some of them hereafter.

One possible axis of research will consist in extending and reinterpreting standard algorithms and their theoretical analyses in the continuous setup. This part of the work will leverage on the recent results of Candès, Peyré and their co-workers [1, 2] in the domain of convex optimization. Moreover, additional insights into the behavior of greedy procedures with continuous dictionaries will be gained by addressing the following problems:

- Improving the understanding of the “worst-case” behavior of standard greedy algorithms. Indeed, although the worst-case conditions of success are available for some greedy procedures (e.g., orthogonal matching pursuit (OMP) [3] or orthogonal least square (OLS) [4]), they still remain uncharacterized for most of them (e.g., IHT [5], Subspace Pursuit [6], etc) in the current literature.
- Characterizing the “average-case” behavior of greedy algorithms (e.g., what is their probability of recovering the support of the sparse vector given a distribution of the non-zero coefficients?). Although the latter question is well understood for algorithms based on convex relaxation, it still remains unanswered in the current literature for greedy algorithms.

[1] Candès, E. J. and Fernandez-Granda, C., Towards a mathematical theory of super-resolution,Comm. Pure Appl. Math, 67(6):906–956, June 2014.

[2] Duval, V. and Peyré, G., Exact support recovery for sparse spikes deconvolution,Foundations of Computational Mathematics, 15(5):1315–1355, 2015.

[3] Tropp, J., Greed is good: algorithmic results for sparse approximation, IEEE Transactions onInformation Theory, 50(10):2231–2242.

[4] Soussen, C., Gribonval, R., Idier, J., and Herzet, C., Joint *k*-step analysis of orthogonal matching pursuit and orthogonal least squares, IEEE Transactions on Information Theory, 59(5).

[5] Blumensath, T. and Davies, M. E., Iterative thresholding for sparse approximations, Journal of Fourier Analysis and Applications, 14(5-6):629–654.

[6] Dai, W. and Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Transactions on Information Theory, 55(5):2230–2249.

Please send your candidature (a resume, a cover letter and the names of two referees) in a single pdf file to

- Dr. Cédric Herzet, (https://people.rennes.inria.fr/Cedric.Herzet/)

INRIA Rennes-Bretagne Atlantique

e-mail : cedric.herzet@inria.fr - Dr. Rémi Gribonval, (https://people.irisa.fr/Remi.Gribonval/)

INRIA Rennes-Bretagne Atlantique

e-mail : remi.gribonval@inria.fr - Dr. Charles Soussen, (www.cran.univ-lorraine.fr/charles.soussen/)

CRAN, Nancy

e-mail : charles.soussen@univ-lorraine.fr

(c) GdR 720 ISIS - CNRS - 2011-2015.