Riepilogo Tecnico: Problemi di Prossimità Generalizzata delle Matrici II

Definizione del Problema

Questo articolo estende lo studio dei problemi di prossimità generalizzata delle matrici, originariamente affrontati in [13]. Il problema fondamentale cerca una matrice $X$ che minimizzi la distanza rispetto a una data matrice $A$ sotto vincoli specifici. La forma generalizzata considerata qui coinvolge tre matrici date $A, B, C$ e minimizza la funzione obiettivo:
$$\min_{X \in S} \|A - BXC\|$$
dove $S$ rappresenta un insieme ammissibile definito da vari vincoli (ad esempio, rango, norma, simmetria, struttura, positività). L'articolo investiga specificamente tre estensioni rispetto alla formulazione standard con norma di Frobenius ($\|\cdot\|_F$) trovata in [13]:

1. Termini Affini: L'inclusione di termini affini come $dx^TE$ o $Dxe^T$ nella funzione obiettivo.
2. Prodotti di Kronecker: La sostituzione dei prodotti matriciali standard con prodotti di Kronecker (ad esempio, $B \otimes X \otimes C$) e la generalizzazione dei vincoli di rango al rango di Kronecker.
3. Norme di Schatten: La generalizzazione della norma di Frobenius a norme arbitrariamente invarianti per ortogonalità, specificamente le norme $p$ di Schatten ($\|\cdot\|_{\sigma,p}$).

Metodologia

L'articolo adotta un approccio duale: derivare soluzioni in forma chiusa per casi specifici e sviluppare un algoritmo iterativo del primo ordine (zeroth-order) per il caso generale.

1. Soluzioni in Forma Chiusa

Gli autori identificano quattro varianti specifiche del problema che ammettono soluzioni in forma chiusa, estendendo i risultati di [13]:

• Prossimità Generalizzata Affina: Problemi che coinvolgono termini come $\|A - BXC + Dxe^T\|_F$. Questi vengono trasformati in problemi di prossimità generalizzata standard utilizzando operatori di proiezione (Proposizione 3.2).
• Prodotto di Kronecker Separabile: Minimizzare $\|A - B \otimes X \otimes C\|_F$. Questo viene risolto introducendo un operatore di riorganizzazione $R$ che trasforma la struttura di Kronecker in un problema standard di prossimità delle matrici (Proposizione 3.3).
• Rango di Kronecker Generalizzato: Minimizzare $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ soggetto a $\text{rank}_\otimes(X) \le r$. Questo si riduce a un problema standard con vincolo di rango tramite l'operatore di riorganizzazione e le proprietà della decomposizione ai valori singolari (SVD) dei prodotti di Kronecker (Proposizione 3.4, Algoritmo 1).
• Traccia Parziale Prescritta: Minimizzare $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ soggetto a un vincolo di traccia parziale $\text{tr}_P(X(W \otimes I)) = \lambda W$. Questo viene ridotto a un problema di autovalori prescritti o a un problema con vincolo di rango (Proposizione 3.5, Corollario 3.6).

2. Non Esistenza di Risultati di Tipo Mirsky

L'articolo investiga se il teorema di Eckart–Young–Mirsky (che afferma che la migliore approssimazione di rango $r$ è indipendente dalla norma invarianti per ortogonalità utilizzata) si estenda al problema generalizzato $\min_{\text{rank}(X) \le r} \|A - BXC\|$.

• Risultato: Gli autori dimostrano che nessun risultato di tipo Mirsky vale quando $B$ e $C$ non sono matrici identità.
• Evidenza: Attraverso un controesempio (Esempio 4.2), dimostrano che il minimizzatore per il problema generalizzato con vincolo di rango dipende dalla specifica norma di Schatten ($p=1, 2, \infty$) scelta. Questo contrasta con il problema standard di approssimazione di rango, dove la soluzione è universale per tutte le norme invarianti per ortogonalità.

3. Algoritmo Iterativo (Algoritmo 3)

Per i casi in cui non esistono soluzioni in forma chiusa (specificamente per norme di Schatten generali e vincoli complessi), gli autori propongono un algoritmo iterativo basato sul metodo di proiezione di Dykstra (Algoritmo 2), specializzato per le norme di Schatten (Algoritmo 3).

• Meccanismo: L'algoritmo alterna due passaggi:
  1. Aggiornamento di $X$: Risolve un problema di prossimità generalizzata delle matrici nella norma di Frobenius (utilizzando metodi da [13] o le soluzioni in forma chiusa derivate nella Sezione 3).
  2. Aggiornamento di $Y$: Risolve un problema di operatore prossimale per la norma di Schatten $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$. Gli autori derivano aggiornamenti espliciti in forma chiusa per i valori singolari di $Y$ per $p=1$ (norma nucleare), $p=\infty$ (norma spettrale) e $p \in (1, \infty)$ generico (Lemma 5.5–5.7).
• Caratteristica Chiave: L'algoritmo è del primo ordine (zeroth-order); non calcola gradienti o subgradienti espliciti. Si basa puramente su operazioni di algebra lineare numerica (SVD e moltiplicazioni di matrici).
• Convergenza: È dimostrato che l'algoritmo converge a un minimizzatore globale da qualsiasi punto iniziale. Il tasso di convergenza è sublineare (a causa della mancanza di convessità forte nelle norme di Schatten per $p \neq 2$), sebbene gli esperimenti numerici suggeriscano un comportamento quasi lineare nella pratica.

Risultati Chiave

• Espansioni in Forma Chiusa: L'articolo fornisce soluzioni esplicite per le varianti affina, prodotto di Kronecker separabile, rango di Kronecker e traccia parziale del problema di prossimità generalizzata.
• Limitazione Teorica: Stabilisce che l'universalità della soluzione attraverso diverse norme invarianti per ortogonalità (teorema di Mirsky) si rompe in presenza di moltiplicatori non identità $B$ e $C$.
• Prestazioni Algoritmiche:
  • Velocità: Negli esperimenti numerici (Sezione 6), l'Algoritmo 3 supera significativamente i risolutori di ottimizzazione convessa generici (in particolare CVX con il risolvente SCS). Per dimensioni elevate, CVX spesso non riesce a convergere entro limiti di tempo ragionevoli, mentre l'Algoritmo 3 converge rapidamente.
  • Accuratezza: L'Algoritmo 3 raggiunge la precisione della macchina ($\approx 10^{-15}$) nell'errore in avanti, mentre CVX mostra errori fluttuanti (da $10^{-7}$ a $10^3$) e spesso non riesce a soddisfare i vincoli (ad esempio, in compiti di identificazione di sistemi).
  • Versatilità: L'algoritmo gestisce con successo obiettivi convessi non standard (ad esempio, norma di Schatten $3/2$) e vincoli non convessi (ad esempio, vincoli di rango, autovalori prescritti) che sono inaccessibili a risolutori standard come CVX.

Significato e Affermazioni

L'articolo afferma di avanzare il campo dei problemi di prossimità delle matrici attraverso:

1. Estensione della Risolvibilità: Fornendo soluzioni in forma chiusa per nuove classi di problemi che coinvolgono termini affini e strutture di Kronecker.
2. Chiarimento dei Confini Teorici: Dimostrando i limiti dell'estensione dei teoremi classici di approssimazione (Mirsky) a contesti generalizzati.
3. Offerta di un'Alternativa Robusta: Proponendo un algoritmo iterativo che è globalmente convergente, privo di gradienti e computazionalmente superiore ai risolutori generici.
4. Evidenziazione dello Sfruttamento Strutturale: Gli autori sottolineano che lo sfruttamento di strutture matriciali specifiche tramite algebra lineare numerica (come fatto in [13] e in questo lavoro) produce prestazioni migliori e una maggiore applicabilità (inclusi casi non convessi) rispetto al fare affidamento esclusivamente su framework di ottimizzazione convessa generale.

Il lavoro è presentato come un sequel di [13], mantenendo la filosofia di risolvere problemi di ottimizzazione senza calcoli di derivate, sfruttando così la ricca struttura degli spazi matriciali.