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/

Zendy Plus

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

Zendy Tools

Zendy Open

Given a random $n \times n$ symmetric matrix $\boldsymbol W$ drawn from theGaussian orthogonal ensemble (GOE), we consider the problem of certifying anupper bound on the maximum value of the quadratic form $\boldsymbol x^\top\boldsymbol W \boldsymbol x$ over all vectors $\boldsymbol x$ in a constraintset $\mathcal{S} \subset \mathbb{R}^n$. For a certain class of normalizedconstraint sets $\mathcal{S}$ we show that, conditional on certaincomplexity-theoretic assumptions, there is no polynomial-time algorithmcertifying a better upper bound than the largest eigenvalue of $\boldsymbol W$.A notable special case included in our results is the hypercube $\mathcal{S} =\{ \pm 1 / \sqrt{n}\}^n$, which corresponds to the problem of certifying boundson the Hamiltonian of the Sherrington-Kirkpatrick spin glass model fromstatistical physics.  Our proof proceeds in two steps. First, we give a reduction from thedetection problem in the negatively-spiked Wishart model to the abovecertification problem. We then give evidence that this Wishart detectionproblem is computationally hard below the classical spectral threshold, byshowing that no low-degree polynomial can (in expectation) distinguish thespiked and unspiked models. This method for identifying computationalthresholds was proposed in a sequence of recent works on the sum-of-squareshierarchy, and is believed to be correct for a large class of problems. Ourproof can be seen as constructing a distribution over symmetric matrices thatappears computationally indistinguishable from the GOE, yet is supported onmatrices whose maximum quadratic form over $\boldsymbol x \in \mathcal{S}$ ismuch larger than that of a GOE matrix.

Computational Hardness of Certifying Bounds on Constrained PCA Problems