Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computationally efficient sparse clustering   We study statistical and computational limits of clustering when the means of
the centres are sparse and their dimension is possibly much larger than the
sample size. Our theoretical analysis focuses on the model $X_i = z_i \theta +
\varepsilon_i, ~z_i \in \{-1,1\}, ~\varepsilon_i \thicksim \mathcal{N}(0,I)$,
which has two clusters with centres $\theta$ and $-\theta$. We provide a finite
sample analysis of a new sparse clustering algorithm based on sparse PCA and
show that it achieves the minimax optimal misclustering rate in the regime
$\|\theta\| \rightarrow \infty$.
  Our results require the sparsity to grow slower than the square root of the
sample size. Using a recent framework for computational lower bounds -- the
low-degree likelihood ratio -- we give evidence that this condition is
necessary for any polynomial-time clustering algorithm to succeed below the BBP
threshold. This complements existing evidence based on reductions and
statistical query lower bounds. Compared to these existing results, we cover a
wider set of parameter regimes and give a more precise understanding of the
runtime required and the misclustering error achievable. Our results imply that
a large class of tests based on low-degree polynomials fail to solve even the
weak testing task.

26
The categories of this paper are: bayes-an
19
The categories of this paper are: eess
17
The categories of this paper are: q-fin
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
11
The categories of this paper are: hep-lat
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
20
The categories of this paper are: acc-phys
21
The categories of this paper are: adap-org
9
The categories of this paper are: nlin
25
The categories of this paper are: patt-sol
14
The categories of this paper are: math-ph
29
The categories of this paper are: funct-an