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

Titel: Veel (de meeste?) criteria voor kolomsubsetselectie zijn NP-moeilijk voor een klein aantal kolommen

Auteurs: Ilse C.F. Ipsen en Arvind K. Saibaba (North Carolina State University)

---

1. Probleemstelling

Het paper onderzoekt het probleem van de kolomsubsetselectie (Column Subset Selection Problem - CSSP). Gegeven een reële $m \times n$ matrix $A$, is het doel om een subset van $k$ representatieve kolommen $C \in \mathbb{R}^{m \times k}$ te selecteren. De focus ligt specifiek op het geval waarin $k$ relatief klein is, namelijk $1 \le k \le \min\{\text{rank}(A), m/3\}$.

De auteurs analyseren de computationele complexiteit van diverse optimalisatiecriteria die worden gebruikt om deze subset te kiezen. Deze criteria omvatten:

• Maximalisatie: Absoluut volume, S-optimaliteit, relatief volume en stabiele rang (stable rank).
• Minimalisatie: Normen (2-norm, Frobenius-norm, Schatten $p$-normen voor $p>2$), pseudo-inversenormen, en conditienummers (voor verschillende normcombinaties).

De centrale vraag is of deze problemen in polynomiale tijd oplosbaar zijn, of dat ze tot de klasse van NP-moeilijke (NP-hard) problemen behoren, en of er Polynomial Time Approximation Schemes (PTAS) bestaan die een goede benadering kunnen garanderen.

2. Methodologie

De auteurs hanteren een systematische aanpak om de complexiteit te bepalen:

1. Reductie naar Beslissingsproblemen: In plaats van direct de optimalisatieproblemen aan te pakken, formuleren ze deze als beslissingsproblemen (bijv. "Bestaat er een subset met een volume groter dan $b$?").
2. NP-Hardheid Bewijzen: Ze voeren een polynomiale tijdreductie uit vanuit het bekende NP-complete probleem "Exact Cover by 3 Sets" (X3C).
   • Ze construeren een matrix $A$ met eenheid-norm kolommen die de verzamelingen van het X3C-probleem vertegenwoordigt.
   • Ze tonen aan dat een X3C-instantie een oplossing heeft dan en slechts dan als de matrix $A$ een submatrix $C$ heeft met orthonormale kolommen.
   • Ze leiden optimale waarden af voor de selectiecriteria (bijv. maximale volume = 1 voor orthonormale kolommen). Hierdoor is het vinden van de optimale waarde equivalent aan het oplossen van X3C.
3. Inapproximabiliteit (Geen PTAS): Om te bewijzen dat er geen PTAS bestaat, creëren ze een "gap" tussen de optimale waarde en een suboptimale drempelwaarde. Ze tonen aan dat het NP-moeilijk is om de criteria te benaderen binnen deze gap.
   • Ze maken gebruik van singular value interlacing (verstrengeling van singuliere waarden) om te tonen dat het verwijderen van kolommen bepaalde eigenschappen (zoals relatief volume en conditienummer) monotoon beïnvloedt. Dit stelt hen in staat om de analyse te beperken tot matrices met slechts twee kolommen om de hardheid van benadering te bewijzen.

3. Belangrijkste Bijdragen

De paper introduceert en analyseert de volgende nieuwe en bestaande criteria:

1. Relatief Volume (Nieuw criterium):

   • Gedefinieerd als $rvol(C) = \text{vol}(C) / \|C\|_2^k$.
   • Dit criterium is omgekeerd evenredig met een macht van het conditienummer en kan dus slecht geconditioneerde matrices detecteren, in tegenstelling tot het absolute volume.
   • Bewezen NP-moeilijk en geen PTAS mogelijk.

2. Uitgebreide NP-Hardheid Resultaten:

   • De auteurs bewijzen NP-hardheid voor een breed scala aan criteria, waaronder $p$-norm pseudo-inversen, $p$-norm conditienummers (voor $p \ge 2$), en stabiele rang maximalisatie.
   • Ze verduidelijken dat minimalisatie van de Frobenius-norm van de matrix zelf ($\|C\|_F$) wel in polynomiale tijd oplosbaar is (via een greedy algoritme), wat een belangrijke uitzondering is.

3. Nieuwe Inapproximabiliteit Drempels:

   • Ze leveren rigoureuze bewijzen voor drempelwaarden die afwijken van eerdere literatuur (zoals [9]).
   • Voorbeeld: Voor de minimalisatie van de pseudo-inverse in de 2-norm is de drempel $\sqrt{3}/2$ (in plaats van $(\sqrt{3}/2)^{1/(k-1)}$).
   • Voor de Frobenius-norm van de pseudo-inverse is de drempel $\sqrt{1 + 1/(4k)}$.

4. Analytische Afleidingen:

   • Ze leiden optimale waarden af voor alle onderzochte criteria voor matrices met eenheid-norm kolommen.
   • Ze presenteren uitdrukkingen voor gepartitioneerde pseudo-inversen en afgeleide ondergrenzen voor hun normen, wat relevant is voor A-optimale design en trace-optimalisatie.

4. Kernresultaten

De resultaten worden samengevat in Tabel 1 van het paper en kunnen als volgt worden geconcludeerd:

• NP-Moeilijkheid: De meeste criteria (volume, relatief volume, S-optimaliteit, normen, pseudo-inversen, conditienummers, stabiele rang) zijn NP-moeilijk. Dit betekent dat er geen polynomiale tijd algoritmen voor bestaan, tenzij P = NP.
• Geen PTAS: Voor de meeste criteria bestaat er geen Polynomial Time Approximation Scheme. Het is NP-moeilijk om deze problemen binnen een bepaalde factor (de "gap") van de optimale oplossing te benaderen.
  • Uitzondering: Minimalisatie van de Frobenius-norm van de matrix $C$ zelf is polynomiaal oplosbaar.
  • Uitzondering: Voor Schatten $p$-norm minimalisatie ($p>2$) en conditienummer minimalisatie ($p>2$) konden de auteurs geen PTAS-onbenaderbaarheid bewijzen (vanwege de complexiteit van het creëren van een gap), hoewel NP-hardheid wel geldt.
• Specifieke Drempels:
  • Relatief volume: Benadering binnen factor $1/\sqrt{2}$ is NP-moeilijk.
  • Volume: Benadering binnen factor $2\sqrt{2}/3$ is NP-moeilijk.
  • 2-norm conditienummer: Benadering binnen factor $\sqrt{2}$ is NP-moeilijk.

5. Betekenis en Impact

De resultaten van dit paper hebben aanzienlijke implicaties voor het veld van numerieke lineaire algebra en optimalisatie:

1. Fundamentele Beperkingen: Het paper bevestigt dat het selecteren van een optimale kolomsubset voor diverse veelgebruikte criteria fundamenteel computationeel moeilijk is. Dit legt een theoretische grens aan de efficiëntie van algoritmen voor deze taken.
2. Validatie van Heuristieken: Omdat exacte oplossingen onmogelijk zijn in polynomiale tijd (voor de meeste criteria), onderstreept het werk het belang van heuristische benaderingen (zoals greedy algoritmen, lokale optimalisatie of randomisatie) en randomized algorithms.
3. Nieuw Criterium: De introductie van relatief volume biedt een robuust alternatief voor absolute volume, omdat het rekening houdt met de conditie van de matrix, wat cruciaal is voor numerieke stabiliteit in toepassingen zoals regressie en ontwerp van experimenten.
4. Toepassingen: De resultaten zijn direct relevant voor gebieden zoals:
   • A-optimaal ontwerp (trace-minimalisatie van de pseudo-inverse).
   • Data compressie en feature selectie.
   • Numerieke lineaire algebra (bepalen van rang en basis).

Samenvattend biedt dit paper een uitgebreide complexiteitsanalyse die de grenzen van wat berekenbaar is voor kolomsubsetselectie duidelijk maakt, en levert het nieuwe inzichten en bewijzen die de theoretische basis van dit onderzoeksveld versterken.