English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Clustering mixtures of Gaussian distributions is a fundamental andchallenging problem that is ubiquitous in various high-dimensional dataprocessing tasks. While state-of-the-art work on learning Gaussian mixturemodels has focused primarily on improving separation bounds and theirgeneralization to arbitrary classes of mixture models, less emphasis has beenpaid to practical computational efficiency of the proposed solutions. In thispaper, we propose a novel and highly efficient clustering algorithm for $n$points drawn from a mixture of two arbitrary Gaussian distributions in$\mathbb{R}^p$. The algorithm involves performing random 1-dimensionalprojections until a direction is found that yields a user-specified clusteringerror $e$. For a 1-dimensional separation parameter $\gamma$ satisfying$\gamma=Q^{-1}(e)$, the expected number of such projections is shown to bebounded by $o(\ln p)$, when $\gamma$ satisfies $\gamma\leqc\sqrt{\ln{\ln{p}}}$, with $c$ as the separability parameter of the twoGaussians in $\mathbb{R}^p$. Consequently, the expected overall running time ofthe algorithm is linear in $n$ and quasi-linear in $p$ at $o(\ln{p})O(np)$, andthe sample complexity is independent of $p$. This result stands in contrast toprior works which provide polynomial, with at-best quadratic, running time in$p$ and $n$. We show that our bound on the expected number of 1-dimensionalprojections extends to the case of three or more Gaussian components, and wepresent a generalization of our results to mixture distributions beyond theGaussian model.

Linear Time Clustering for High Dimensional Mixtures of Gaussian Clouds