Many (most?) column subset selection criteria are NP hard for a few columns

Aquí presento un resumen técnico detallado del artículo "Many (most?) column subset selection criteria are NP hard for a few columns" de Ilse C.F. Ipsen y Arvind K. Saibaba.

1. Planteamiento del Problema

El artículo aborda el problema de la selección de subconjuntos de columnas (Column Subset Selection Problem - CSSP). Dada una matriz general $A \in \mathbb{R}^{m \times n}$, el objetivo es seleccionar un subconjunto de $k$ columnas ($C \in \mathbb{R}^{m \times k}$) que sean "representativas" según diversos criterios de optimización.

El estudio se centra específicamente en el caso donde se requieren pocas columnas, es decir, $1 \le k \le \min\{\text{rank}(A), m/3\}$. Los criterios de selección analizados incluyen:

• Maximización: Volumen absoluto, Optimalidad-S, Volumen relativo (un criterio nuevo), y Rango estable (Stable Rank).
• Minimización: Normas (2-norma, norma de Frobenius, normas de Schatten $p$-norma para $p>2$), normas de la pseudo-inversa, y números de condición (en 2-norma, Frobenius y mixtos).

El objetivo principal es establecer la clase de complejidad computacional de estos problemas, determinando si son resolubles en tiempo polinomial o si son intrínsecamente difíciles (NP-hard).

2. Metodología

Los autores emplean la teoría de la complejidad computacional para analizar estos problemas. Su estrategia se basa en los siguientes pilares:

• Reducción de Problemas NP-Completos: Para demostrar que un criterio es NP-duro (NP-hard), realizan una reducción en tiempo polinomial desde el problema NP-completo conocido como "Exact Cover by 3-Sets" (X3C).
  • Construyen una matriz $A$ con columnas de norma unitaria donde cada columna representa un subconjunto de 3 elementos.
  • Demuestran que la existencia de una solución óptima para el criterio de selección de columnas (por ejemplo, un submatriz con columnas ortonormales) es equivalente a la existencia de una solución exacta para el problema X3C.
• Formulación como Problemas de Decisión: Transforman los problemas de optimización en problemas de decisión (ej. "¿Existe un subconjunto con volumen $\ge b$?"). Para ello, derivan valores óptimos teóricos para cada criterio bajo la suposición de columnas ortonormales.
• Análisis de Aproximabilidad (PTAS): Para determinar si un problema admite un Esquema de Aproximación en Tiempo Polinomial (PTAS), buscan un "hueco" (gap) entre el valor óptimo y un valor subóptimo específico. Si es NP-duro aproximar el problema más allá de cierto umbral, entonces no existe PTAS (a menos que P=NP).
• Herramientas Matemáticas: Utilizan propiedades de los valores singulares (interlacing), desigualdades de Hadamard, relaciones entre normas de Schatten, y expresiones para pseudo-inversas de matrices particionadas.

3. Contribuciones Clave

El artículo presenta seis contribuciones principales:

1. Introducción del "Volumen Relativo": Proponen un nuevo criterio de maximización del volumen relativo ($rvol(C) = vol(C) / \|C\|_2^k$). A diferencia del volumen absoluto, este criterio es sensible a la condición de la matriz (es inversamente proporcional a una potencia del número de condición), permitiendo detectar matrices mal condicionadas.
2. Pruebas Rigurosas de Inaproximabilidad: Proporcionan demostraciones formales de los umbrales de inaproximabilidad para la minimización de la norma 2 de la pseudo-inversa y la minimización del número de condición en norma 2, corrigiendo o refinando resultados anteriores de la literatura.
3. Nuevos Resultados de NP-Dureza: Demuestran que los siguientes criterios son NP-duros:
   • Minimización de la pseudo-inversa en normas $p$ ($p \ge 2$).
   • Minimización del número de condición en normas $p$ y mixtas ($p \ge 2$).
   • Maximización del rango estable y del rango estable $p$-estable ($p > 2$).
4. Ausencia de PTAS: Establecen que la mayoría de los criterios analizados no admiten un PTAS. Esto incluye la minimización de la pseudo-inversa en norma de Frobenius y normas de Schatten ($p>2$), así como la minimización de números de condición en normas de Frobenius y mixtas.
5. Derivación de Valores Óptimos: Calculan los valores óptimos teóricos para todos los criterios de selección de columnas (volumen, normas, pseudo-inversas, etc.) cuando las columnas son ortonormales, lo cual es esencial para formular los problemas de optimización como problemas de decisión.
6. Expresiones para Pseudo-Inversas Particionadas: Derivan expresiones y cotas inferiores para las pseudo-inversas de matrices particionadas, herramientas útiles para el análisis de la norma de la pseudo-inversa al añadir columnas.

4. Resultados Principales

La Tabla 1 del artículo resume los hallazgos, que pueden sintetizarse así:

• NP-Dureza: Casi todos los criterios de selección (volumen, volumen relativo, optimalidad-S, normas, pseudo-inversas, números de condición y rangos estables) son NP-duros cuando $k$ es pequeño. La única excepción notable mencionada es la minimización de la norma de Frobenius de la submatriz $C$, que puede resolverse en tiempo polinomial mediante un algoritmo voraz (seleccionar las columnas con menor norma 2).
• Inaproximabilidad (No PTAS): La mayoría de los criterios no admiten un PTAS. Se establecen umbrales específicos de inaproximabilidad, por ejemplo:
  • Volumen: Factor $2\sqrt{2}/3$.
  • Volumen Relativo: Factor $1/\sqrt{2}$.
  • Norma 2 de la pseudo-inversa: Factor $2/\sqrt{3}$.
  • Número de condición 2-norma: Factor $\sqrt{2}$.
• Caso Especial (Frobenius): La minimización de la norma de Frobenius de la submatriz $C$ es polinomial, pero la minimización de la norma de Frobenius de la pseudo-inversa $C^\dagger$ (relacionada con el diseño óptimo A) es NP-duro y no admite PTAS.

5. Significado e Impacto

Este trabajo es fundamental para la teoría de la aproximación matricial y el diseño experimental por las siguientes razones:

• Límites Teóricos: Establece límites claros sobre lo que es computacionalmente posible. Al demostrar que la mayoría de los criterios "óptimos" son NP-duros y no aproximables eficientemente, justifica por qué en la práctica se utilizan algoritmos heurísticos, aleatorizados o voraces, en lugar de buscar soluciones exactas.
• Nuevas Métricas: La introducción del volumen relativo ofrece una herramienta teórica superior para la selección de columnas cuando la estabilidad numérica (condicionamiento) es crítica, superando las limitaciones del volumen absoluto.
• Conexión con Diseño Óptimo: Los resultados sobre la minimización de la norma de la pseudo-inversa en norma de Frobenius tienen implicaciones directas en el diseño óptimo A (minimización de la traza de la matriz de covarianza), un problema central en estadística y diseño de experimentos.
• Unificación: El artículo unifica el análisis de complejidad para una amplia gama de criterios (normas, condiciones, rangos) bajo un marco común de reducción desde X3C, proporcionando una referencia completa para futuros investigadores en álgebra lineal numérica y teoría de la complejidad.

En conclusión, el paper demuestra que, salvo contadas excepciones, encontrar el subconjunto óptimo de columnas bajo criterios de calidad estándar es un problema computacionalmente intratable, lo que refuerza la necesidad de desarrollar y analizar algoritmos de aproximación y heurísticas en lugar de algoritmos exactos.