F. Alizadeh and D. D. Goldfarb, Second-order cone programming, Math. Program., Ser. B, vol.95, issue.1, pp.3-51, 2003.

R. Baraniuk, M. Davenport, R. Devore, and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx, vol.28, issue.3, pp.253-263, 2008.

J. Bien, J. Taylor, and R. Tibshirani, A Lasso for hierarchical interactions, Ann. Statist, vol.41, issue.3, pp.1111-1141, 2013.

P. E. Blöchl, Generalized separable potentials for electronic-structure calculations, Phys. Rev. B, vol.41, pp.5414-5416, 1990.

T. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comp. Harm. Anal, vol.27, issue.3, pp.265-274, 2009.

T. Blumensath and M. E. Davies, Normalized iterative hard thresholding: Guaranteed stability and performance, IEEE J. Selected Topics in Signal Proc, vol.4, issue.2, pp.298-309, 2010.

E. J. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, vol.346, issue.9, pp.589-592, 2008.

E. J. Candès and J. Romberg, 1 -magic: Recovery of sparse signals via convex programming, 2005.

Y. Chen, Y. Chi, and A. J. Goldsmith, Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Trans. Inf. Theory, issue.7, pp.4034-4059, 2015.

N. H. Choi, W. Li, and J. Zhu, Variable selection with the strong heredity constraint and its oracle property, J. Amer. Statist. Assoc, vol.105, issue.489, pp.354-364, 2010.

A. Cohen, R. Devore, and C. Schwab, Convergence rates of best n-term Galerkin approximations for a class of elliptic spdes, Found. Comp. Math, vol.10, issue.6, pp.615-646, 2010.

L. Comminges and A. S. Dalalyan, Tight conditions for consistency of variable selection in the context of high dimensionality, Ann. Statist, vol.40, issue.5, pp.2667-2696, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00602211

L. Comminges and A. S. Dalalyan, Tight conditions for consistent variable selection in high dimensional nonparametric regression, J. Mach. Learn. Res, vol.19, pp.187-206, 2012.
URL : https://hal.archives-ouvertes.fr/inria-00566721

A. Dalalyan, Y. Ingster, and A. B. Tsybakov, Statistical inference in compound functional models. Probability Theory and Related Fields, vol.158, pp.513-532, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00725663

R. Devore, G. Petrova, and P. Wojtaszczyk, Approximation of functions of few variables in high dimensions, Constr. Approx, vol.33, pp.125-143, 2011.

S. J. Dibangoye, C. Amato, O. Buffet, and F. Charpillet, Exploiting separability in multiagent planning with continuous-state mdps, Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '14, pp.1281-1288, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01092066

S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing

/. Birkhäuser and . Springer, , 2013.

L. M. Ghiringhelli, J. Vybíral, S. V. Levchenko, C. Draxl, and M. Scheffler, Big data of materials science: Critical role of the descriptor, Phys. Rev. Lett, vol.114, issue.10, p.105503, 2015.

G. Goel, I. Chou, and E. O. Voit, System estimation from metabolic time-series data, Bioinformatics, vol.24, issue.21, pp.2505-2511, 2008.

A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions, pp.301-312, 1981.

D. L. Hanson and F. T. Wright, A bound on tail probabilities for quadratic forms in independent random variables, Ann. Math. Stat, vol.42, issue.3, pp.1079-1083, 1971.

M. Holtz, Sparse grid quadrature in high dimensions with applications in finance and insurance, vol.77, 2010.

J. Huang, J. L. Horowitz, and F. Wei, Variable selection in nonparametric additive models, Ann. Statist, vol.38, issue.4, pp.2282-2313, 2010.

V. Kekatos and G. B. Giannakis, Sparse volterra and polynomial regression models: Recoverability and estimation, Trans. Sig. Proc, vol.59, issue.12, pp.5907-5920, 2011.

V. Koltchinskii and M. Yuan, Sparse recovery in large ensembles of kernel machines, 21st Annual Conference on Learning Theory (COLT), pp.229-238, 2008.

V. Koltchinskii and M. Yuan, Sparsity in multiple kernel learning, Ann. Statist, vol.38, issue.6, pp.3660-3695, 2010.

Y. Lin and H. H. Zhang, Component selection and smoothing in multivariate nonparametric regression, Ann. Statist, vol.34, issue.5, pp.2272-2297, 2006.

L. Meier, S. Van-de-geer, and P. Bühlmann, High-dimensional additive modeling, Ann. Statist, vol.37, issue.6B, pp.3779-3821, 2009.

E. Mossel, R. O'donnell, and R. Servedio, Learning juntas, 35th Annual ACM Symposium on Theory of Computing (STOC), pp.206-212, 2003.

B. Nazer and R. D. Nowak, Sparse interactions: Identifying high-dimensional multilinear systems via compressed sensing, 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.1589-1596, 2010.

Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, Society for Industrial and Applied Mathematics, 1994.

E. Novak and H. Triebel, Function spaces in lipschitz domains and optimal rates of convergence for sampling, Constr. Approx, vol.23, issue.3, pp.325-350, 2006.

E. Novak and H. Wo?niakowski, Approximation of infinitely differentiable multivariate functions is intractable, J. Compl, vol.25, pp.398-404, 2009.

P. Radchenko and G. M. James, Variable selection using adaptive nonlinear interaction structures in high dimensions, J. Amer. Statist. Assoc, vol.105, pp.1541-1553, 2010.

G. Raskutti, M. J. Wainwright, and B. Yu, Minimax-optimal rates for sparse additive models over kernel classes via convex programming, J. Mach. Learn. Res, vol.13, issue.1, pp.389-427, 2012.

H. Rauhut, Compressive sensing and structured random matrices. Theoretical foundations and numerical methods for sparse recovery, vol.9, pp.1-92, 2010.

P. Ravikumar, J. Lafferty, H. Liu, and L. Wasserman, Sparse additive models, J. Royal Statist. Soc.: Series B (Statistical Methodology), vol.71, issue.5, pp.1009-1030, 2009.

K. Schnass and J. Vybíral, Compressed learning of high-dimensional sparse functions, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.3924-3927, 2011.

S. Shan and G. G. Wang, Survey of modeling and optimization strategies to solve highdimensional design problems with computationally-expensive black-box functions, Struct. Multidiscip. Optim, vol.41, issue.2, pp.219-241, 2010.

C. B. Storlie, H. D. Bondell, B. J. Reich, and H. H. Zhang, Surface estimation, variable selection, and the nonparametric oracle property, Statistica Sinica, vol.21, issue.2, pp.679-705, 2011.

H. Tyagi, A. Krause, and B. Gärtner, Efficient sampling for learning sparse additive models in high dimensions, Advances in Neural Information Processing Systems (NIPS) 27, pp.514-522, 2014.

H. Tyagi, A. Kyrillidis, B. Gärtner, and A. Krause, Learning sparse additive models with interactions in high dimensions, 19th International Conference on Artificial Intelligence and Statistics (AISTATS), pp.111-120, 2016.

H. Tyagi, A. Kyrillidis, B. Gärtner, and A. Krause, Algorithms for learning sparse additive models with interactions in high dimensions. Information and Inference: A, Journal of the IMA, p.8, 2017.

R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed Sensing: Theory and Applications, pp.210-268, 2012.

J. Vybíral, Sampling numbers and function spaces, J. Compl, vol.23, issue.4-6, pp.773-792, 2007.

J. Vybíral, Widths of embeddings in function spaces, J. Compl, vol.24, issue.4, pp.545-570, 2008.

M. Wahl, Variable selection in high-dimensional additive models based on norms of projections, 2015.

A. Winkelbauer, Moments and absolute moments of the normal distribution, 2014.

Y. Yang and S. T. Tokdar, Minimax-optimal nonparametric regression in high dimensions, Ann. Statist, vol.43, issue.2, pp.652-674, 2015.

P. Zhu, J. Morelli, and S. Ferrari, Value function approximation for the control of multiscale dynamical systems, 2016 IEEE 55th Conference on Decision and Control (CDC), pp.5471-5477, 2016.