Límites Inferiores Computacionales para PCA Disperso

En el contexto de la detección de componentes principales dispersos, presentamos evidencia sobre la existencia de un costo estadístico a pagar por la eficiencia computacional. Medimos el rendimiento de una prueba por la menor fuerza de señal que puede detectar y proponemos un método computacionalmente eficiente basado en programación semidefinida. También demostramos que el rendimiento estadístico de esta prueba no puede ser mejorado estrictamente por ningún método computacionalmente eficiente. Nuestros resultados pueden verse como límites inferiores teóricos de complejidad condicionados a las suposiciones de que algunas instancias del problema de cliques plantados no pueden resolverse en tiempo polinómico aleatorizado.