Structured matrix factorization length

Technische Samenvatting: Gestructureerde Matrixfactorisatie Lengte

Probleemstelling
Het artikel behandelt het probleem van het bepalen van het minimale aantal gestructureerde matrices dat nodig is om een gegeven vierkante matrix $A \in \mathbb{C}^{n \times n}$ te factoriseren. Hoewel de bestaande literatuur heeft vastgesteld dat elke (of generieke) complexe matrix kan worden uitgedrukt als een product van een specifts aantal gestructureerde matrices (bijv. $2n+5$ of $\lfloor n/2 \rfloor + 1$ Toeplitz-matrices), bleven het exacte minimale aantal voor een specifieke matrix, en de geometrische eigenschappen van de verzameling van dergelijke producten, grotendeels onverkend. De auteurs generaliseren deze vraagstelling naar willekeurige matrixstructuren gedefinieerd door affiene variëteiten $X \subseteq \mathbb{C}^{n \times n}$. De centrale vraag is: Wat is de kleinste integer $r$ waarvoor $A = M_1 \cdots M_r$ met $M_i \in X$?

Methodologie en Raamwerk
De auteurs formuleren dit probleem met behulp van de instrumenten uit de algebraïsche meetkunde. Ze definiëren de $X$-factorisatielengte, aangeduid als $FL_X(A)$, als de minimale $r$ waarvoor een exacte factorisatie bestaat. Om gevallen aan te pakken waarin een exacte factorisatie mogelijk niet bestaat maar wel willekeurig dichtbij benaderd kan worden, introduceren zij de border $X$-factorisatielengte, $\overline{FL}_X(A)$.

Belangrijke methodologische componenten zijn:

1. Factorisatievariëteiten: De auteurs definiëren de $r$-de $X$-factorisatievariëteit, $\mu_r(X)$, als de Zariski-sluiting van de afbeelding van de matrixvermenigvuldigingsafbeelding $m_r: X^{\times r} \to \mathbb{C}^{n \times n}$. De border lengte is de kleinste $r$ waarvoor $A \in \mu_r(X)$.
2. Topologische Equivalentie: Zij bewijzen dat voor irreducibele affiene variëteiten $X$ (wat de meeste standaard gestructureerde matrices omvat) de Zariski-sluiting en de Euclidische sluiting van de verzameling van producten van lengte $r$ samenvallen. Dit maakt het mogelijk om de border lengte te interpreteren via limieten van producten.
3. Dimensie- en Graad-analyse: Het artikel onderzoekt de dimensie en graad van $\mu_r(X)$. Dimensies worden berekend met behulp van de rang van de differentiaal van de vermenigvuldigingsafbeelding bij specifieke "speciale punten". Graden worden geschat met behulp van numerieke algebraïsche meetkunde (homotopie-continuatie) voor gevallen waar analytische berekening onhandelbaar is.
4. Definiërende Vergelijkingen via Verplaatsingsrang (Displacement Rank): Om ondergrenzen voor de factorisatielengte te vinden en definiërende vergelijkingen voor de variëteiten af te leiden, maken de auteurs gebruik van het concept van verplaatsingsrang. Zij tonen aan dat als matrices in $X$ een begrensde verplaatsingsrang hebben met betrekking tot bepaalde operatoren, de verplaatsingsrang van een product $A$ een ondergrens biedt voor de factorisatielengte van $A$.
5. Alternerende Minimalisatie: Voor numerieke berekening van factorisaties stellen de auteurs een alternerend kleinste-kwadraten (ALS) algoritme voor. Deze methode optimaliseert iteratief één factor tegelijk terwijl de andere vast worden gehouden, waardoor het probleem wordt gereduceerd tot lineaire kleinste kwadraten voor elke stap.

Belangrijkste Bijdragen en Resultaten
Het artikel levert verschillende specifieke bijdragen voor verschillende matrixstructuren:

• Definities en Theorie: Het introduceert formeel de begrippen gestructureerde matrixfactorisatielengte en border lengte, en legt hun relatie vast met secant-variëteiten en tensorrang-theorie.
• Toeplitz- en Hankel-matrices:
  • De auteurs bewijzen dat de dimensie van de $r$-de Toeplitz- (en Hankel-) factorisatievariëteit $\min\{n^2, 2r(n-1) + 1\}$ is.
  • Zij bevestigen dat de generieke factorisatielengte voor Toeplitz-matrices $\lfloor n/2 \rfloor + 1$ is.
  • Zij leveren computationeel bewijs voor de graad van deze variëteiten (bijv. $\deg \mu_2(T_4) = 474$) met behulp van numerieke algebraïsche meetkunde.
  • Zij demonstreren dat $FL_X(A)$ en $\overline{FL}_X(A)$ niet altijd samenvallen, waarbij zij voorbeelden geven waar een matrix meer factoren vereist voor exacte representatie dan voor benadering.
• Andere Structuren:
  • Bidiagonaal/Tridiagonaal: Zij karakteriseren de variëteiten $\mu_r(UBD_n)$ en $\mu_r(TD_n)$ als variëteiten van $k$-diagonale matrices, waarbij zij hun dimensies en generieke lengtes bepalen.
  • Antisymmetrisch (Skew-Symmetric): Zij berekenen de dimensies van $\mu_r(\Lambda_n)$ voor diverse $n$ en $r$, en tonen aan dat voor een oneven $n$, inversibele matrices niet gefactoriseerd kunnen worden in antisymmetrische matrices.
  • Companion-matrices: Zij stellen vast dat de generieke lengte $n$ is en dat de dimensie van $\mu_r(C_n)$ gelijk is aan $\min\{rn, n^2\}$.
  • Spoorloze Symmetrische Matrices: Bij het onderzoeken van deze orthogonaal invariante structuur, bewijzen zij dat voor $n \ge 3$ de generieke factorisatielengte 2 is, en dat elke matrix een product is van maximaal 10 dergelijke matrices.
• Onder- en Bovengrenzen:
  • Ondergrenzen: De methode van de verplaatsingsrang levert ondergrenzen voor de border lengte op. Voor Toeplitz-matrices leidt dit tot grenzen gebaseerd op de rang van $\nabla_{Z_0}(A)$ en $\nabla_{Z_1, Z_0}(A)$.
  • Bovengrenzen: Het artikel suggereert het gebruik van alternerende minimalisatie om factorisaties te vinden, wat een praktische aanpak biedt voor het numeriek construeren van deze.
• Numerieke Voorbeelden: De auteurs passen het algoritme van alternerende minimalisatie toe op specifieke $3 \times 3$ en $5 \times 5$ Toeplitz-factorisatieproblemen, waarbij zij convergentie naar lage residuen aantonen en bekende rationale factorisaties herstellen.

Betekenis
Het artikel claimt betekenis als het eerste werk dat systematisch de notie van gestructureerde matrixfactorisatielengte als een algebraïsch-geometrisch object introduceert en formaliseert. Door het probleem te kaderen binnen de theorie van affiene variëteiten, secant-variëteiten en tensorrangen, biedt het een verenigd raamwerk om de complexiteit van matrixfactorisaties over diverse structuren (Toeplitz, Hankel, bidiagonaal, etc.) te bestuderen.

De auteurs benadrukken dat hun aanpak het mogelijk maakt om fundamentele invarianten (dimensie, graad) te berekenen en de definiërende vergelijkingen voor deze factorisatievariëteiten af te leiden. Bovendien biedt de ontwikkeling van de verplaatsingsrang-methode voor ondergrenzen en het alternerende minimalisatie-algoritme voor bovengrenzen zowel theoretische inzichten als computationele hulpmiddelen. Het artikel concludeert door toekomstige richtingen te identificeren, waaronder de theoretische bepaling van graden voor Toeplitz-variëteiten, de studie van Euclidische afstand-graden, en de uitbreiding van deze concepten naar reële algebraïsche meetkunde en gemengde-structuur factorisaties.