12 problems

Sparse PCA threshold conjecture. There exists a critical sparsity threshold $\gamma^*\in(0,1)$ such that, if $\gamma\geq\gamma^*$, both the information-theoretic and computational…

In sparse principal component analysis, let $m$ denote the sparsity level and $n$ the number of samples. In the regime $m\gg\sqrt{n}$, recovery of the planted sparse principal comp…

Deterministic $T_1$ bound. There exists a constant $C$ such that, whenever

Ding–Kunisky–Wein runtime conjecture. The runtime

Sparse PCA runtime conjecture. For any $\lambda$ in the hard regime

Let $X$ have prior distribution $P_0$, and consider the rank-one symmetric matrix estimation model … where $Z_{i,j}$ are standard Gaussian noises. Assume $\mathbb{E}_{P_0}[X]=0$ an…

Consider planted Gaussian matrix models with an information-theoretic threshold and a spectral threshold, including sparse PCA, submatrix localization, and Gaussian mixture cluster…

Sparse PCA computational-statistical gap conjecture. No polynomial-time algorithm can consistently detect the spike or recover the support of $v$ if…

Let $u$ and $v$ be the factors in the matrix model considered by Rangan et al., and let AMP denote the corresponding approximate message passing algorithm. Rangan et al.'s AMP opti…

Consider the single-spike model with dimension $p$, sample size $n$, spike support size $k$, and signal strength $\beta$. Let $\mathbf{z}$ denote the sparse spike, and let…

Let $\mathbf{z}$ be the sparse spike in the single-spike model, and let $k$ denote its $\ell_0$-sparsity. An algorithm is computationally efficient if it runs in polynomial time. C…

Sparse principal-component conjecture. The lower bound is tight, and the gap can be closed by using a sparse principal component method to find the relevant features. This would id…