Subexponential hardness of certifying non-negative PCA
Let \bW∈Rsymn×n\bW \in \mathbb{R}^{n \times n}_{\mathrm{sym}}\bW∈Rsymn×n be drawn from the Gaussian orthogonal ensemble, and let λ+(\bW)\lambda^+(\bW)λ+(\bW) denote the non-negative principal component analysis o…