Dificultad Computacional para Certificar Límites en Problemas de PCA Restringido

Dada una matriz aleatoria simétrica n × n extraída del conjunto ortogonal gaussiano (GOE), consideramos el problema de certificar un límite superior en el valor máximo de la forma cuadrática ^⊤? ? sobre todos los vectores? en un conjunto de restricciones? ⊂ ℝⁿ. Para cierta clase de conjuntos de restricciones normalizados, demostramos que, condicionado a cierta conjetura de teoría de la complejidad, ningún algoritmo en tiempo polinómico puede certificar un límite superior mejor que el mayor valor propio de?. Un caso especial notable incluido en nuestros resultados es el hipercubo? = ±1/√nⁿ, que corresponde al problema de certificar límites sobre el Hamiltoniano del modelo de cristal de espín de Sherrington-Kirkpatrick de la física estadística. Nuestros resultados sugieren una notable brecha entre optimización y certificación para este problema. Nuestra prueba avanza en dos pasos. Primero, damos una reducción del problema de detección en el modelo Wishart con picos negativos al problema de certificación anterior. Luego, proporcionamos evidencia de que este problema de detección de Wishart es computacionalmente difícil por debajo del umbral espectral clásico, mostrando que ningún polinomio de bajo grado puede (en promedio) distinguir entre los modelos con picos y sin picos. Este método para predecir umbrales computacionales fue propuesto en una secuencia de trabajos recientes sobre la jerarquía de suma de cuadrados y se conjectura que es correcto para una amplia clase de problemas. Nuestra prueba puede verse como la construcción de una distribución sobre matrices simétricas que parece computacionalmente indistinguible del GOE, sin embargo, está soportada en matrices cuyo máximo sobre la forma cuadrática es mucho mayor que la de una matriz GOE.