Statistik- och maskininlärningsalgoritmer tillämpas ofta på högdimensionella data. I många av dessa applikationer data är knapp, och ofta mycket dyrare än beräkningstiden. Vi tillhandahåller den första prov-effektiv polynom-tid estimator för högdimensionella sfäriska Gaussiska blandningar. För blandningar av alla k d-dimensionella sfäriska Gaussians, härleder vi en intuitiv spektral-uppskattare prover och körs i tiden O k, och (d 3 log 5 d), båda betydligt lägre än tidigare känt. Den konstanta faktorn O k är polynom för prov komplexitet och är exponentiellt för tiden komplexitet, återigen mycket mindre än vad som tidigare var känt. Vi visar också att det behövs 2 prover för alla algoritmer. Provets komplexitet är därför nästan optimal i fråga om antal dimensioner. Vi härleder också en enkel estimator för k-komponent endimensionella blandningar som använder O k log k  och 2 prover och körs i tid Õ k  och 3k+1. Våra andra tekniska bidrag inkluderar en snabbare algoritm för att välja en densitet uppskattning från en uppsättning distributioner, som minimerar l 1 avstånd till en okänd underliggande distribution.
För blandningar av sfäriska Gaussians, en polynom tid algoritm för den realistiska inställning med prov komplexitet O(dk 9 log 2 (d)/ε 4 ) föreslogs i REF Theorem 11].
Near-optimal-sample estimators for spherical Gaussian mixtures
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}