G. Puy, M. Davies, and R. Gribonval, Linear embeddings of lowdimensional subsets of a hilbert space to R m, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01157992

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis, 2013.

E. J. Candès and Y. Plan, Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements, IEEE Transactions on Information Theory, vol.57, issue.4, pp.2342-2359, 2011.
DOI : 10.1109/TIT.2011.2111771

A. Eftekhari and M. Wakin, New analysis of manifold embeddings and signal recovery from compressive measurements, Applied and Computational Harmonic Analysis, vol.39, issue.1, 2014.
DOI : 10.1016/j.acha.2014.08.005

B. Adcock, A. C. Hansen, C. Poon, and B. Roman, BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING, Forum of Mathematics, Sigma, vol.94840, 2013.
DOI : 10.1017/S0962492900002816

M. Vetterli and T. Blu, Sampling signals with finite rate of innovation, IEEE Transactions on Signal Processing, vol.50, issue.6, pp.1417-1428, 2002.
DOI : 10.1109/TSP.2002.1003065

N. Thaper, S. Guha, P. Indyk, and N. Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data , SIGMOD '02, pp.428-439, 2002.
DOI : 10.1145/564691.564741
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.2078

A. Bourrier, R. Gribonval, and P. Pérez, Compressive Gaussian Mixture estimation, 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp.6024-6028, 2013.
DOI : 10.1109/ICASSP.2013.6638821
URL : https://hal.archives-ouvertes.fr/hal-00799896

T. Blumensath, Sampling and Reconstructing Signals From a Union of Linear Subspaces, IEEE Transactions on Information Theory, vol.57, issue.7, pp.4660-4671, 2011.
DOI : 10.1109/TIT.2011.2146550

A. Bourrier, M. E. Davies, T. Peleg, and P. Pérez, Fundamental Performance Limits for Ideal Decoders in High-Dimensional Linear Inverse Problems, IEEE Transactions on Information Theory, vol.60, issue.12, pp.7928-7946, 2014.
DOI : 10.1109/TIT.2014.2364403
URL : https://hal.archives-ouvertes.fr/hal-00908358

J. C. Robinson, Dimensions, embeddings, and attractors, ser. Cambridge Tracts in Mathematics, 2011.

M. Talagrand, Majorizing measures: the generic chaining, The Annals of Probability, vol.24, issue.3, pp.1049-1103, 1996.
DOI : 10.1214/aop/1065725175

K. L. Clarkson, Tighter bounds for random projections of manifolds, Proceedings of the twenty-fourth annual symposium on Computational geometry , SCG '08, pp.39-48, 2008.
DOI : 10.1145/1377676.1377685

H. Rauhut, Compressive sensing and structured random matrices, Theoretical Foundations and Numerical Methods for Sparse Recovery, ser. Radon Series on Computational and Applied Mathematics, pp.1-92, 2010.

S. Dirksen, Tail bounds via generic chaining, Electronic Journal of Probability, vol.20, issue.0, pp.1-29, 2015.
DOI : 10.1214/EJP.v20-3760

T. T. Cai and A. Zhang, ROP: Matrix recovery via rank-one projections, The Annals of Statistics, vol.43, issue.1, pp.102-138, 2015.
DOI : 10.1214/14-AOS1267SUPP

Y. Chen, Y. Chi, and A. J. Goldsmith, Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming, IEEE Transactions on Information Theory, vol.61, issue.7, pp.4034-4059, 2015.
DOI : 10.1109/TIT.2015.2429594

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

R. G. Baraniuk, M. Davenport, R. Devore, and M. Wakin, A Simple Proof of the Restricted Isometry Property for Random Matrices, Constructive Approximation, vol.159, issue.2, pp.253-263, 2008.
DOI : 10.1007/s00365-007-9003-x

U. Ayaz, S. Dirksen, and H. Rauhut, Uniform recovery of fusion frame structured sparse signals, Applied and Computational Harmonic Analysis, vol.41, issue.2, pp.341-361, 2016.
DOI : 10.1016/j.acha.2016.03.006

R. Kueng, H. Rauhut, and U. Terstiege, Low rank matrix recovery from rank one measurements, Applied and Computational Harmonic Analysis, vol.42, issue.1, 2015.
DOI : 10.1016/j.acha.2015.07.007

S. Bahmani and J. Romberg, Sketching for simultaneously sparse and low-rank covariance matrices, 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp.357-360, 2015.
DOI : 10.1109/CAMSAP.2015.7383810

D. Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, vol.66, issue.4, pp.671-687, 2003.
DOI : 10.1016/S0022-0000(03)00025-4

J. Bourgain, S. Dirksen, and J. Nelson, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Geometric and Functional Analysis, vol.1, issue.58, pp.1009-1088, 2015.
DOI : 10.1007/s00039-015-0332-9

B. Adcock and A. C. Hansen, A Generalized Sampling Theorem for Stable Reconstructions in Arbitrary Bases, Journal of Fourier Analysis and Applications, vol.35, issue.11, pp.685-716, 2012.
DOI : 10.1007/s00041-012-9221-x

S. Dirksen, Dimensionality Reduction with Subgaussian Matrices: A Unified Theory, Foundations of Computational Mathematics, vol.14, issue.1, pp.1-30, 2015.
DOI : 10.1007/s10208-015-9280-x

B. Klartag and S. Mendelson, Empirical processes and random projections, Journal of Functional Analysis, vol.225, issue.1, pp.229-245, 2005.
DOI : 10.1016/j.jfa.2004.10.009
URL : http://doi.org/10.1016/j.jfa.2004.10.009

S. Mendelson, A. Pajor, and N. Tomczak-jaegermann, Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis, Geometric and Functional Analysis, vol.17, issue.4, pp.1248-1282, 2007.
DOI : 10.1007/s00039-007-0618-7

R. G. Baraniuk and M. B. Wakin, Random Projections of Smooth Manifolds, Foundations of Computational Mathematics, vol.26, issue.1, pp.51-77, 2009.
DOI : 10.1007/s10208-007-9011-z

W. Mantzel and J. Romberg, Compressed subspace matching on the continuum, Information and Inference, vol.4, issue.2, 2015.
DOI : 10.1093/imaiai/iav008

S. Oymak, B. Recht, and M. Soltanolkotabi, Isometric sketching of any set via the restricted isometry property, 2015.

K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical methods for physics and engineering, 2006.

G. Puy, R. Technicolor, and . France, Before, he was at INRIA in the PANAMA Research team He obtained the Ph He also obtained the M.Sc. degree in Electrical and Electronics Engineering from EPFL and the Engineering Diploma (M.Sc.) from Supélec, France He received the EPFL Chorafas Foundation award in 2013 and the EPFL Doctorate award in 2015. His research interests are in the field of signal processing, image processing and machine learning. He works on the design of efficient sampling methods for high dimensional data (compressive sampling), low-dimensional representations, and non-linear reconstruction methods using convex and nonconvex optimization His work concerns both theory and applications, mainly in imaging problems, 2009.

M. E. Davies, 12F'15) holds the Jeffrey Collins Chair in Signal and Image Processing at UoE, where he also leads the Edinburgh Compressed Sensing Research Group, and is Head of the Institute for Digital Communications (IDCOM) He received an M.A. in engineering from Cambridge University in 1989 where he was awarded a Foundation Scholarship, and a Ph.D. degree in nonlinear dynamics and signal processing from University College London (UCL) in 1993. He was awarded, 1987.