Distance to nearest skew-symmetric matrix polynomials of bounded rank

Technische Samenvatting: Afstand tot de dichtstbijzijnde vrijsymmetrische matrixpolynoom van begrensde rang

Probleemstelling
Het artikel behandelt een gestructureerd matrix-nabijheidsprobleem: gegeven een $m \times m$ matrixpolynoom $P(\lambda)$ van graad $d$ (met complexe coëfficiënten), is het doel om een vrijsymmetrische matrixpolynoom $S(\lambda)$ te vinden van dezelfde graad (of maximaal $d$) en een gespecificeerde evene rang $2r$ (waarbij $2 \le 2r \le m-1$) die de Frobenius-afstand tot $P(\lambda)$ minimaliseert.

Dit probleem generaliseert het bekende "afstand tot singulariteit"-probleem. Terwijl de afstand tot singulariteit streeft naar de dichtstbijzijnde singuliere matrixpolynoom (rang $< m$), richt dit werk zich op een specifieke, lagere rang $2r$. De auteurs merken op dat voor vrijsymmetrische matrices de rang altijd even is, wat de beperking van een evene rang $2r$ natuurlijk maakt. Het probleem wordt geformuleerd als het minimaliseren van de som van de gekwadrateerde Frobenius-normen van de verschillen tussen de coëfficiëntmatrices van $P(\lambda)$ en $S(\lambda)$.

Methodologie
De voorgestelde aanpak, genaamd GEARS (Generic Eigenstructures and Alternating direction method for Rank 2r approximation of Skew-symmetric matrix polynomials), berust op recente theoretische vooruitgang met betrekking tot de generieke eigenstructuren van vrijsymmetrische matrixpolynomen.

1. Generieke Factorisatie (Theoretische Fundering):
   De kern van de methode is een parametrisatie van de verzameling vrijsymmetrische matrixpolynomen met een rang van maximaal $2r$. Bouwend op resultaten uit [17, 18], maken de auteurs gebruik van Stelling 3.1, die stelt dat de verzameling van dergelijke polynomen de afsluiting is van een "generieke verzameling" $G^{ss}_{d, 2r, m}$. Elk element in deze generieke verzameling kan worden gefactoriseerd als:
   $$S(\lambda) = U(\lambda)V(\lambda)^T - V(\lambda)U(\lambda)^T$$
   waarbij $U(\lambda)$ een matrixpolynoom is van graad $\lfloor d/2 \rfloor$ en $V(\lambda)$ een matrixpolynoom is van graad $\lceil d/2 \rceil$, beide met dimensies $m \times r$.

2. Alternating Least Squares (Algoritmische Implementatie):
   Het minimalisatieprobleem wordt geherformuleerd met behulp van de vectorisatie-operator ($\text{vec}$) en de Kronecker-product. Door de factorisatie in de afstandmetriek te substitueren, wordt het probleem een niet-convexe optimalisatietaak over de coëfficiënten van $U(\lambda)$ en $V(\lambda)$.
   De auteurs lossen dit op met behulp van een Alternating Least Squares (ALS) strategie:

   • Fixeer $U(\lambda)$ en los op voor $V(\lambda)$ door een lineair kleinste kwadratenprobleem te minimaliseren met betrekking tot een gestructureerde matrix $M(U(\lambda))$.
   • Fixeer de zojuist berekende $V(\lambda)$ en los op voor $U(\lambda)$ op een vergelijkbare wijze.
   • Itereer tot convergentie. De reeks afstanden is gegarandeerd monotoon niet-toenemend.

3. Specialisatie voor Matrixpencils (Graad $d=1$):
   Voor het specifieke geval van matrixpencils (graad 1), ontwikkelen de auteurs een efficiëntere variant, GEARS-SVD.

   • Zij maken gebruik van Stelling 5.3, die een rang-1 decompositie biedt voor vrijsymmetrische pencils: $S_0 - \lambda S_1 = \sum_{i=1}^r (u_i v_i^T - v_i u_i^T)$, waarbij $u_i$ constante vectoren zijn en $v_i$ lineaire polynoomvectoren zijn.
   • Deze structuur maakt het mogelijk om de ALS-stappen op te lossen door direct kleinere lineaire systemen op te lossen (via SVD en blokpartitionering), in plaats van het construeren van de grote Kronecker-productsystemen die in het algemene geval van polynomen worden gebruikt. Dit vermindert de computationele kosten aanzienlijk.

Belangrijkste Bijdragen

• Algoritme voor Willekeurige Evene Rang: In tegen tegenstelling tot eerdere methoden die primair de afstand tot singulariteit adresseerden (waarbij de rang $m-1$ of $m-2$ is), werkt dit algoritme voor elke gespecificeerde evene rang $2r \ge 2$.
• Theoretische Parametrisatie: Het artikel vestigt een constructieve parametrisatie van de afsluiting van de verzameling vrijsymmetrische polynomen van begrensde rang, wat het gebruik van factorisatie-gebaseerde optimalisatie mogelijk maakt.
• Efficiënte Solver voor Pencils: De afleiding van GEARS-SVD benut de specifieke eigenschappen van vrijsymmetrische pencils om de grote Kronecker-productformuleringen te vermijden, wat een aanzienlijke versnelling oplevert ten opzichte van de algemene GEARS-polynoomsolver.
• Numerieke Validatie: De auteurs bieden numerieke experimenten aan waarbij GEARS en GEARS-SVD worden vergeleken met bestaande methoden (Riemann-Oracle en Matrix-Valued Function benaderingen).

Resultaten
Numerieke experimenten uitgevoerd op willekeurige vrijsymmetrische matrixpolynomen en pencils (omvang tot $50 \times 50$) laten het volgende zien:

• Nauwkeurigheid: GEARS vindt oplossingen op afstanden die vergelijkbaar zijn met andere state-of-the-art methoden.
• Singulariteitskwaliteit: De door GEARS geproduceerde oplossingen zijn "singularer" (vertonen kleinere minimale singuliere waarden) dan die van concurrerende algoritmen, wat consistent is met de constructie van de methode.
• Prestaties: GEARS is aanzienlijk sneller dan de Riemann-Oracle en de MVF-algoritmen. Voor matrixpencils presteert GEARS-SVD beter dan het algemene GEARS-algoritme, vooral naarmate de matrixomvang toeneemt, vanwege het vermijden van grote Kronecker-productformuleringen.
• Schaalbaarheid: De looptijd schaalt redelijk met de matrixgrootte, waarbij het geval met reële velden ongeveer een orde van grootte sneller is dan het complexe geval bij vergelijkbare outputkwaliteit.

Betekenis en Claims
Het artikel claimt dat hun aanpak onderscheidend is van en complementair aan bestaande optimalisatiestrategieën (zoals Riemann-Oracle) door gebruik te maken van de specifieke algebraïsche structuur van vrijsymmetrische polynomen. De primaire betekenis ligt in het bieden van een verenigd kader dat:

1. Het afstand-tot-singulariteit probleem als een speciaal geval oplost.
2. Deze capaciteit uitbreidt naar het vinden van de dichtstbijzijnde polynoom van elke gespecificeerde evene rang.
3. Een computationeel efficiënt gespecialiseerd algoritme biedt voor het belangrijke geval van matrixpencils.

De auteurs merken bescheiden op dat hun methode momenteel beperkt is tot vrijsymmetrische structuren en dat uitbreidingen naar andere gestructureerde klassen (symmetrisch, palindromisch, etc.) voor toekomstig werk zijn gereserveerd. Het algoritme produceert een polynoom van exact rang $2r$ (tot afrondingsfouten) en is ontworpen als een praktisch hulpmiddel voor regeltechniek, systeemidentificatie en de analyse van differentiaal-algebraïsche vergelijkingen waar dergelijke gestructureerde low-rank benaderingen vereist zijn.