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

Resumo Técnico: Complexidade Computacional da Seleção de Subconjuntos de Colunas

1. Problema Investigado

O artigo aborda o problema de Seleção de Subconjunto de Colunas (Column Subset Selection - CSS). Dada uma matriz real $A \in \mathbb{R}^{m \times n}$, o objetivo é selecionar um subconjunto de $k$ colunas ($C \in \mathbb{R}^{m \times k}$) que sejam "representativos" de $A$. O foco do trabalho é o regime onde o número de colunas selecionadas é pequeno, especificamente $1 \le k \le \min\{\text{rank}(A), m/3\}$.

Os autores analisam a complexidade computacional de diversos critérios de otimização para essa seleção, incluindo:

• Maximização de volume absoluto e S-otimalidade.
• Minimização de normas (2-norm, norma de Frobenius, normas de Schatten $p$ para $p > 2$).
• Minimização da norma da pseudo-inversa.
• Minimização do número de condição (em várias normas).
• Maximização do "rank estável" (stable rank).
• Novo critério: Maximização do volume relativo (inversamente proporcional a uma potência do número de condição).

A questão central é determinar se esses problemas pertencem à classe P (solúveis em tempo polinomial) ou se são NP-difíceis (NP-hard), e se admitam Esquemas de Aproximação em Tempo Polinomial (PTAS).

2. Metodologia

A estratégia dos autores baseia-se na Teoria da Complexidade Computacional, utilizando reduções polinomiais a partir de problemas NP-completos conhecidos.

• Problema de Redução: Os autores utilizam o problema Exact Cover by 3-Sets (X3C), que é NP-completo.
• Construção da Instância: Eles constroem uma matriz $A$ com colunas de norma unitária, onde cada coluna corresponde a um conjunto de 3 elementos do problema X3C. Os elementos não nulos da coluna são $1/\sqrt{3}$.
• Equivalência Lógica: Demonstram que uma instância de X3C possui uma cobertura exata se e somente se a matriz $A$ possui um subconjunto de $k$ colunas que são ortonormais.
• Conexão com Critérios: Para cada critério de seleção, derivam os valores ótimos teóricos (quando as colunas são ortonormais).
  • Se o critério atingir seu valor ótimo, as colunas são ortonormais $\implies$ X3C é verdadeiro.
  • Se o critério não atingir o ótimo (ou estiver abaixo de um certo limiar), X3C é falso.
• Prova de NP-Dificuldade: Ao mostrar que encontrar o valor ótimo é equivalente a resolver X3C, provam que o problema de otimização é NP-difícil.
• Prova de Inaproximabilidade (Sem PTAS): Para mostrar que não existe um PTAS, os autores estabelecem um "gap" (lacuna) entre o valor ótimo e o melhor valor possível em casos onde X3C é falso. Eles analisam submatrizes com apenas 2 colunas para derivar limites superiores/inferiores rigorosos, demonstrando que aproximar o critério além desse gap resolveria X3C, implicando $P=NP$.

3. Principais Contribuições

1. Introdução do Volume Relativo: Propõem o critério de "maximização do volume relativo" ($rvol(C) = vol(C) / \|C\|_2^k$). Diferente do volume absoluto, o volume relativo é capaz de detectar matrizes mal condicionadas, sendo inversamente proporcional a uma potência do número de condição.
2. Provas Rigorosas de Limites de Aproximação: Fornecem provas formais para os limiares de inaproximabilidade (thresholds) que diferem e refinam resultados anteriores da literatura (especificamente de [9]), especialmente para a minimização da norma 2 da pseudo-inversa e do número de condição 2-norm.
3. Generalização para Normas de Schatten e Mistas: Estendem os resultados de NP-dificuldade e inaproximabilidade para:
   • Minimização de pseudo-inversa em normas $p$ ($p \ge 2$).
   • Minimização de números de condição em normas mistas (ex: $\kappa_D(C) = \|C\|_F \|C^\dagger\|_2$).
   • Maximização do rank estável e $p$-rank estável para $p > 2$.
4. Derivação de Valores Ótimos: Calculam os valores ótimos exatos para todos os critérios considerados quando as colunas são ortonormais, permitindo a formulação dos problemas de otimização como problemas de decisão.
5. Expressões para Pseudo-inversas Partitionadas: Derivam expressões e limites inferiores para a norma da pseudo-inversa de matrizes partitionadas, ferramentas úteis para a análise teórica.

4. Resultados Chave

A Tabela 1 do artigo resume a complexidade dos critérios. Os resultados principais são:

• NP-Difíceis: A maioria dos critérios listados é NP-difícil, incluindo:

  • Maximização de Volume, S-otimalidade e Volume Relativo.
  • Minimização de Normas (2-norm e Schatten $p$ para $p > 2$).
  • Minimização de Normas da Pseudo-inversa (2-norm, Frobenius, Schatten $p$).
  • Minimização de Números de Condição (2-norm, Frobenius, Schatten $p$, mistos).
  • Maximização de Rank Estável.
  • Exceção: A minimização da norma de Frobenius de $C$ pode ser resolvida em tempo polinomial (algoritmo guloso).

• Inaproximabilidade (Ausência de PTAS): A maioria dos critérios não admite um Esquema de Aproximação em Tempo Polinomial (PTAS), a menos que $P=NP$.

  • Volume Relativo: Inaproximável dentro de um fator de $1/\sqrt{2}$.
  • Volume Absoluto: Inaproximável dentro de um fator de $2\sqrt{2}/3$.
  • Norma 2 da Pseudo-inversa: Inaproximável dentro de um fator de $2/\sqrt{3}$ (limiar derivado rigorosamente, corrigindo/alterando o anterior).
  • Norma de Frobenius da Pseudo-inversa: Inaproximável dentro de um fator de $\sqrt{1 + 1/(4k)}$.
  • Número de Condição 2-norm: Inaproximável dentro de um fator de $\sqrt{2}$.
  • Rank Estável: Inaproximável dentro de um fator de $3/4$.

5. Significado e Impacto

• Fundamentação Teórica: O trabalho estabelece limites fundamentais sobre o que é computacionalmente viável na seleção de colunas. Ele confirma que, para a maioria dos critérios de qualidade (especialmente aqueles relacionados à estabilidade numérica e condicionamento), não existem algoritmos eficientes (polinomiais) que garantam soluções ótimas ou aproximações arbitrariamente boas.
• Guia para Prática: Os resultados sugerem que, na prática, deve-se recorrer a algoritmos heurísticos, aleatórios ou locais (como algoritmos guloso ou de amostragem por volume), sabendo que eles não garantem o ótimo global.
• Novos Critérios: A introdução do "Volume Relativo" oferece uma métrica mais robusta para seleção de colunas em contextos onde o condicionamento da matriz é crítico, superando a limitação do volume absoluto que pode ser alto mesmo para matrizes mal condicionadas.
• Aplicações: Os resultados são relevantes para áreas como Design de Experimentos Ótimos (A-optimal design), onde a minimização da norma da pseudo-inversa (traço) é crucial, e em métodos de redução de dimensionalidade e interpolação.

Em suma, o artigo fornece uma análise completa e rigorosa da complexidade intrínseca dos problemas de seleção de colunas, demonstrando que a busca por subconjuntos ótimos sob critérios comuns é computacionalmente proibitiva na maioria dos casos.