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

Titolo: Molti (la maggior parte?) criteri di selezione di sottoinsiemi di colonne sono NP-difficili per un numero ridotto di colonne

1. Il Problema

Il lavoro affronta il problema della Selezione di Sottinsieme di Colonne (Column Subset Selection - CSS). Dato un generico matrice reale $A \in \mathbb{R}^{m \times n}$, l'obiettivo è selezionare $k$ colonne rappresentative $C \in \mathbb{R}^{m \times k}$ (dove $1 \le k \le \min\{\text{rank}(A), m/3\}$) che ottimizzino specifici criteri matematici.

Il paper si concentra sulla complessità computazionale di diversi criteri di ottimizzazione popolari, tra cui:

• Massimizzazione del volume e S-ottimalità.
• Minimizzazione delle norme (norma 2, norma di Frobenius, norme di Schatten $p$ per $p > 2$) della matrice $C$.
• Minimizzazione delle norme della pseudo-inversa $C^\dagger$.
• Minimizzazione del numero di condizione (nelle norme 2, Frobenius, Schatten $p$ e miste).
• Massimizzazione del rango stabile (stable rank).
• Un nuovo criterio introdotto dagli autori: la massimizzazione del volume relativo.

L'ipotesi centrale è che, quando il numero di colonne richieste $k$ è sufficientemente piccolo rispetto alla dimensione della matrice, la maggior parte di questi problemi di ottimizzazione sia intrattabile dal punto di vista computazionale.

2. Metodologia

Gli autori adottano un approccio basato sulla teoria della complessità computazionale per classificare la difficoltà di questi problemi. La strategia si articola in tre fasi principali:

1. Riduzione da problemi NP-completi:
   Per dimostrare che un criterio è NP-difficile, gli autori eseguono una riduzione in tempo polinomiale dal problema NP-completo noto come Exact Cover by 3-Sets (X3C).

   • Costruiscono una matrice $A$ con colonne a norma unitaria, dove ogni colonna corrisponde a un insieme di 3 elementi.
   • Dimostrano che l'esistenza di una soluzione esatta per X3C è equivalente all'esistenza di un sottogruppo di colonne $C$ che soddisfi un valore ottimale specifico per il criterio in esame (ad esempio, volume massimo o condizione numero minimo).

2. Derivazione di Valori Ottimali:
   Per formulare i problemi di ottimizzazione come problemi decisionali (necessari per la teoria NP), gli autori derivano i valori ottimali teorici per ciascun criterio quando le colonne sono ortonormali.

   • Ad esempio, mostrano che il volume massimo per colonne a norma unitaria è 1, e ciò si verifica se e solo se le colonne sono ortonormali.
   • Derivano espressioni per le pseudo-inverse partizionate per analizzare le proprietà delle norme.

3. Analisi di Inapprossimabilità (Assenza di PTAS):
   Per dimostrare che molti criteri non ammettono uno Schema di Approssimazione in Tempo Polinomiale (PTAS), gli autori creano un "gap" tra il valore ottimale e un valore sub-ottimale.

   • Utilizzano il Lemma di Interlacciamento dei Valori Singolari per mostrare che rimuovere colonne può solo peggiorare (o migliorare in modo monotono) certi criteri.
   • Dimostrano che per istanze "false" di X3C, il valore del criterio non può superare una certa soglia di inapprossimabilità. Se un algoritmo potesse approssimare il criterio oltre questa soglia, potrebbe risolvere X3C, implicando $P = NP$.

3. Contributi Chiave

I principali contributi del lavoro sono:

1. Introduzione del Volume Relativo: Gli autori definiscono il volume relativo ($rvol(C) = vol(C) / \|C\|_2^k$), che è inversamente proporzionale a una potenza del numero di condizione. A differenza del volume assoluto, questo criterio è in grado di rilevare matrici mal condizionate. Dimostrano che anche la massimizzazione del volume relativo è NP-difficile e priva di PTAS.
2. Estensione dei Risultati di Complessità: Generalizzano i risultati noti (prevalentemente per la norma 2) a una vasta gamma di criteri, inclusi:
   • Minimizzazione delle pseudo-inverse nelle norme di Schatten $p$ ($p > 2$).
   • Minimizzazione del numero di condizione in norme miste e di Schatten.
   • Massimizzazione del rango stabile e del $p$-rango stabile.
3. Nuove Soglie di Inapprossimabilità: Forniscono dimostrazioni rigorose per le soglie di inapprossimabilità (fattori di approssimazione) che differiscono e spesso migliorano quelli presenti in letteratura precedente (es. [9]). Ad esempio, per la minimizzazione della norma 2 della pseudo-inversa, la soglia è $\sqrt{3}/2$, diversa da quella riportata in lavori precedenti.
4. Eccezioni Polinomiali: Identificano che la minimizzazione della norma di Frobenius di $C$ è risolvibile in tempo polinomiale (tramite un algoritmo greedy che seleziona le colonne con la norma 2 più piccola), fornendo un confine chiaro tra problemi trattabili e intrattabili.

4. Risultati Principali

La Tabella 1 del paper (e i teoremi associati) riassume le conclusioni per $k \le \min\{\text{rank}(A), m/3\}$:

Punti salienti dei risultati:

• La maggior parte dei criteri di selezione, specialmente quelli legati alla stabilità numerica (condizione numero, pseudo-inversa) e alla geometria (volume), sono NP-difficili.
• La maggior parte di questi problemi non ammette un PTAS, il che significa che non esistono algoritmi in tempo polinomiale che possano garantire un'approssimazione arbitrariamente vicina alla soluzione ottima.
• L'unica eccezione significativa è la minimizzazione della norma di Frobenius della matrice stessa, che è risolvibile in modo efficiente.

5. Significato e Implicazioni

Questo lavoro ha profonde implicazioni per la comunità della matematica computazionale e dell'analisi numerica:

• Limiti Teorici: Stabilisce un confine teorico rigoroso su cosa sia possibile ottenere con algoritmi efficienti nella selezione di colonne. Suggerisce che per la maggior parte dei criteri di alta qualità (che garantiscono stabilità numerica o rappresentatività geometrica), non ci si può aspettare algoritmi esatti o approssimati di alta precisione in tempo polinomiale.
• Giustificazione degli Algoritmi Euristic: I risultati giustificano l'uso diffuso di algoritmi euristici, greedy o randomizzati (come il campionamento basato sul volume) nella pratica. Poiché i problemi sono intrattabili, queste approssimazioni sono spesso l'unica opzione praticabile per matrici di grandi dimensioni.
• Nuovi Criteri: L'introduzione del "volume relativo" offre un nuovo strumento per la selezione di colonne che tiene conto esplicitamente della condizione della matrice, un aspetto critico in applicazioni come il design sperimentale (A-optimal design) e l'analisi dei dati.
• Design Sperimentale: I risultati sulla minimizzazione della norma della pseudo-inversa in norma di Frobenius sono direttamente applicabili al problema di ottimizzazione della traccia nel design sperimentale A-ottimale, fornendo limiti fondamentali sulla complessità di tali problemi di progettazione.

In sintesi, il paper conferma che la ricerca di sottoinsiemi di colonne ottimali secondo criteri sofisticati è un problema computazionalmente intrattabile nella maggior parte dei casi, spingendo la ricerca verso lo sviluppo di algoritmi approssimati con garanzie di performance limitate o verso strategie euristica.