D. Achlioptas and F. Mcsherry, On spectral learning of mixtures of distributions. Learning Theory, pp.458-469, 2005.

P. Ahrendt, The Multivariate Gaussian Probability Distribution, 2005.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Machine Learning, vol.75, pp.245-248, 2009.

D. Arthur and S. Vassilvitskii, k-means++ -the advantages of careful seeding. SODA, 2007.

M. Belkin and K. Sinha, Toward Learning Gaussian Mixtures with Arbitrary Separation, Conference On Learning Theory (COLT), 2010.

M. Bojarski, A. Choromanska, and K. Choromanski, Structured adaptive and random spinners for fast machine learning computations, 2016.
URL : https://hal.archives-ouvertes.fr/hal-02010086

A. Bourrier, R. Gribonval, and P. Perez, Compressive Gaussian Mixture Estimation, ICASSP, pp.6024-6028, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00799896

K. Bredies and H. K. Pikkarainen, Inverse problems in spaces of measures, ESAIM: Control, 2013.

E. J. Candès and C. Fernandez-granda, Super-resolution from noisy data, Journal of Fourier Analysis and Applications, vol.19, issue.6, pp.1229-1254, 2013.

A. Chatalic, R. Gribonval, and N. Keriven, Large-Scale High-Dimensional Clustering with Fast Sketching, ICASSP 2018 -IEEE International Conference on Acoustics, Speech and Signal Processing, pp.4714-4718, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701121

K. Choromanski and V. Sindhwani, Recycling Randomness with Structure for Sublinear time Kernel Expansions. ICML, 2016.

T. M. Cover and J. A. Thomas, Elements of Information Theory, 1991.

F. Cucker and S. Smale, On the mathematical foundations of learning, Bulletin of the American Mathematical Society, vol.39, issue.1, pp.1-49, 2002.

S. Dasgupta and L. J. Schulman, A Two-Round Variant of EM for Gaussian Mixtures, Uncertainty in Artificial Intelligence, pp.152-159, 2000.

F. De-castro, D. Gamboa, J. Henrion, and . Lasserre, Exact solutions to super resolution on semi-algebraic domains in higher dimensions, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01114328

J. Duchi, Derivations for Linear Algebra and Optimization, 2007.

V. Duval and G. Peyré, Exact support recovery for sparse spikes deconvolution, Foundations of Computational Mathematics, vol.15, issue.5, pp.1315-1355, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00839635

A. A. Fedotov, P. Harremoës, and F. Topsøe, Refinements of Pinsker's Inequality, IEEE Trans. Inf. Theor, vol.49, issue.6, pp.1491-1498, 2003.

A. Feuerverger and R. A. Mureika, The Empirical Characteristic Function and Its Applications, Annals of Statistics, vol.5, issue.1, pp.88-97, 1977.

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, 2012.

M. R. Garey, D. S. Johnson, and H. S. Witsenhausen, The complexity of the generalized Lloyd -Max problem, IEEE Trans. Inf. Theory, vol.28, issue.2, pp.255-256, 1982.

L. Giffon, V. Emiya, L. Ralaivola, and H. Kadri, QuicK-means: Acceleration of K-means by learning a fast transform, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02174845

S. Graf, H. Luschgy, and G. Pagès, Optimal quantizers for Radon random vectors in a Banach space, J. Approx. Theory, vol.144, issue.1, pp.27-53, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00004668

R. Gribonval, G. Blanchard, N. Keriven, and Y. Traonmilin, Compressive Statistical Learning with Random Feature Moments, 2020.
URL : https://hal.archives-ouvertes.fr/hal-01544609

N. Keriven, A. Bourrier, R. Gribonval, and P. Pérèz, Sketching for Large-Scale Learning of Mixture Models, IEEE International Conference on Acoustic, Speech and Signal Processing, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01208027

N. Keriven, N. Tremblay, Y. Traonmilin, and R. Gribonval, Compressive k-means, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01386077

N. Keriven, A. Bourrier, R. Gribonval, and P. Pérez, Sketching for Large-Scale Learning of Mixture Models, Information and Inference, vol.7, issue.3, pp.447-508, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01208027

Q. Le, T. Sarlós, and A. J. Smola, Fastfood -Approximating Kernel Expansions in Loglinear Time. arXiv, vol.28, pp.1-29, 2013.

Q. Li and G. Tang, The Nonconvex Geometry of Low-Rank Matrix Optimizations with General Objective Functions, 2016.

P. Massart, Concentration Inequalities and Model Selection, Lecture Notes in Mathematics, vol.1896, 2007.

I. Pinelis, An approach to inequalities for the distributions of infinite-dimensional martingales, Probability in Banach Spaces, 8, Proceedings of the 8th International Conference, vol.30, pp.128-134, 1992.

D. Pollard, Quantization and the method of k -means, IEEE Trans. Information Theory, vol.28, issue.2, pp.199-205, 1982.

C. Poon, N. Keriven, and G. Peyré, The geometry of off-the-grid compressed sensing, pp.1-64, 2020.
URL : https://hal.archives-ouvertes.fr/hal-02484957

B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet, Hilbert space embeddings and metrics on probability measures, The Journal of Machine Learning Research, vol.11, pp.1517-1561, 2010.

H. Steinhaus, Sur la division des corps matériels en parties, British Journal of Mathematical and Statistical Psychology, Cl. III, vol.IV, issue.12, pp.801-804, 1956.

Y. Traonmilin and R. , Stable recovery of low-dimensional cones in hilbert spaces: One RIP to rule them all, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01207987

S. Vempala and G. Wang, A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, vol.68, issue.4, pp.841-860, 2004.