Technische Samenvatting: Generalized Matrix Nearness Problems II

Probleemdefinitie

Dit artikel breidt de studie van generalized matrix nearness problems uit, oorspronkelijk behandeld in [13]. Het fundamentele probleem zoekt een matrix $X$ die de afstand tot een gegeven matrix $A$ minimaliseert onder specifieke constraints. De hier beschouwde generalisatie omvat drie gegeven matrices $A, B, C$ en minimaliseert de doelfunctie:
$$\min_{X \in S} \|A - BXC\|$$
waarbij $S$ een toelaatbare verzameling voorstelt die wordt gedefinieerd door diverse constraints (bijvoorbeeld rang, norm, symmetrie, structuur, positiviteit). Het artikel onderzoekt specifiek drie uitbreidingen op de standaard Frobenius-normformulering ($\|\cdot\|_F$) zoals gevonden in [13]:

1. Affiene Termen: Het opnemen van affiene termen zoals $dx^TE$ of $Dxe^T$ in de doelfunctie.
2. Kronecker-producten: Het vervangen van standaard matrixproducten door Kronecker-producten (bijvoorbeeld $B \otimes X \otimes C$) en het generaliseren van rangconstraints naar Kronecker-rang.
3. Schatten-normen: Het generaliseren van de Frobenius-norm naar willekeurige orthogonaal invariantenormen, specifiek Schatten $p$-normen ($\|\cdot\|_{\sigma,p}$).

Methodologie

Het artikel hanteert een tweeledige aanpak: het afleiden van gesloten-vorm oplossingen voor specifieke gevallen en het ontwikkelen van een iteratief algoritme van nulde orde voor het algemene geval.

1. Gesloten-vorm Oplossingen

De auteurs identificeren vier specifieke varianten van het probleem die gesloten-vorm oplossingen toelaten, waarmee de resultaten van [13] worden uitgebreid:

• Affiene Generalized Nearness: Problemen die termen bevatten zoals $\|A - BXC + Dxe^T\|_F$. Deze worden getransformeerd tot standaard generalized nearness-problemen met behulp van projectie-operatoren (Propositie 3.2).
• Scheidbaar Kronecker-product: Het minimaliseren van $\|A - B \otimes X \otimes C\|_F$. Dit wordt opgelost door een herschikingsoperator $R$ in te voeren die de Kronecker-structuur transformeert tot een standaard matrix nearness-probleem (Propositie 3.3).
• Generalized Kronecker-rang: Het minimaliseren van $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ onderhevig aan $\text{rank}_\otimes(X) \le r$. Dit reduceert tot een standaard rang-constrained probleem via de herschikingsoperator en eigenschappen van singuliere waarden decompositie (SVD) van Kronecker-producten (Propositie 3.4, Algoritme 1).
• Vooraf bepaalde partiële trace: Het minimaliseren van $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ onderhevig aan een partiële trace-constraint $\text{tr}_P(X(W \otimes I)) = \lambda W$. Dit wordt gereduceerd tot een vooraf bepaald eigenwaardeprobleem of een rang-constrained probleem (Propositie 3.5, Corollarium 3.6).

2. Non-bestaan van Mirsky-type Resultaten

Het artikel onderzoekt of de stelling van Eckart–Young–Mirsky (die stelt dat de beste rang-$r$ benadering onafhankelijk is van de gebruikte orthogonaal invariantenorm) uitbreidt naar het generaliseprobleem $\min_{\text{rank}(X) \le r} \|A - BXC\|$.

• Resultaat: De auteurs bewijzen dat geen Mirsky-type resultaat geldt wanneer $B$ en $C$ geen eenheidsmatrices zijn.
• Bewijs: Via een tegenvoorbeeld (Voorbeeld 4.2) tonen ze aan dat de minimalizer voor het rang-constrained generaliseprobleem afhankelijk is van de gekozen specifieke Schatten-norm ($p=1, 2, \infty$). Dit staat in contrast met het standaard rang-benaderingsprobleem, waarbij de oplossing universeel is voor alle orthogonaal invariantenormen.

3. Iteratief Algoritme (Algoritme 3)

Voor gevallen waarin gesloten-vorm oplossingen niet bestaan (specifiek voor general Schatten-normen en complexe constraints), stellen de auteurs een iteratief algoritme voor gebaseerd op Dykstra's projectiemethode (Algoritme 2), gespecialiseerd voor Schatten-normen (Algoritme 3).

• Mechanisme: Het algoritme wisselt af tussen twee stappen:
  1. $X$-update: Lost een generalized matrix nearness-probleem op in de Frobenius-norm (met behulp van methoden uit [13] of de in Sectie 3 afgeleide gesloten-vorm oplossingen).
  2. $Y$-update: Lost een proximal operator-probleem op voor de Schatten-norm $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$. De auteurs leiden expliciete gesloten-vorm updates af voor de singuliere waarden van $Y$ voor $p=1$ (nucleaire norm), $p=\infty$ (spectrale norm) en algemene $p \in (1, \infty)$ (Lemma's 5.5–5.7).
• Kernkenmerk: Het algoritme is van nulde orde; het berekent geen expliciete gradiënten of subgradiënten. Het vertrouwt puur op numerieke lineaire algebra-operaties (SVD's en matrixvermenigvuldigingen).
• Convergentie: Het algoritme is bewezen te convergeren naar een globale minimalizer vanuit elk startpunt. De convergentiesnelheid is sublineair (vanwege het ontbreken van sterke convexiteit in Schatten-normen voor $p \neq 2$), hoewel numerieke experimenten in de praktijk een bijna lineair gedrag suggereren.

Kernresultaten

• Gesloten-vorm Uitbreidingen: Het artikel biedt expliciete oplossingen voor affiene, scheidbare Kronecker-, Kronecker-rang- en partiële trace-varianten van het generalized nearness-probleem.
• Theoretische Beperking: Het stelt vast dat de universaliteit van de oplossing over verschillende orthogonaal invariantenormen (Mirsky's stelling) bezwijkt in aanwezigheid van niet-eenheidsmultipllicatoren $B$ en $C$.
• Algoritmische Prestaties:
  • Snelheid: In numerieke experimenten (Sectie 6) presteert Algoritme 3 aanzienlijk beter dan algemene convex-optimalisatie-oplossers (specifiek CVX met de SCS-oplosser). Voor grote dimensies faalt CVX vaak om binnen redelijke tijdslimieten te convergeren, terwijl Algoritme 3 snel convergeert.
  • Nauwkeurigheid: Algoritme 3 bereikt machinenvaardigheid ($\approx 10^{-15}$) in de forward error, terwijl CVX fluctuerende fouten vertoont (variërend van $10^{-7}$ tot $10^3$) en vaak faalt om constraints te voldoen (bijvoorbeeld in systeemidentificatietaken).
  • Veelzijdigheid: Het algoritme behandelt succesvol niet-standaard convex doelen (bijvoorbeeld Schatten $3/2$-norm) en niet-convex constraints (bijvoorbeeld rangconstraints, vooraf bepaalde eigenwaarden) die ontoegankelijk zijn voor standaardoplossers zoals CVX.

Betekenis en Claims

Het artikel claimt het veld van matrix nearness-problemen te bevorderen door:

1. Uitbreiding van Oplosbaarheid: Het bieden van gesloten-vorm oplossingen voor nieuwe klassen van problemen die affiene termen en Kronecker-structuren bevatten.
2. Verduidelijking van Theoretische Grenzen: Het aantonen van de beperkingen van het uitbreiden van klassieke benaderingstheorema's (Mirsky) naar generalisatiesettingen.
3. Aanbieden van een Robuust Alternatief: Het voorstellen van een iteratief algoritme dat globaal convergent, gradiëntvrij en rekenkundig superieur is aan algemene oplossers.
4. Benadrukken van Structurele Exploitatie: De auteurs benadrukken dat het exploiteren van specifieke matrixstructuren via numerieke lineaire algebra (zoals gedaan in [13] en dit werk) betere prestaties en bredere toepasbaarheid (inclusief niet-convex gevallen) oplevert dan het uitsluitend vertrouwen op algemene convex-optimalisatiekaders.

Het werk wordt gepresenteerd als een vervolg op [13], waarbij de filosofie behouden blijft om optimalisatieproblemen op te lossen zonder afgeleideberekeningen, thereby het rijke van matrixruimten benutend.