On Determining the Convergence Rate of an Infinite Product of Stochastic Matrices

Sintesi Tecnica: Sull'Determinazione del Tasso di Convergenza di un Prodotto Infinito di Matrici Stocastiche

Enunciato del Problema
Il saggio affronta l'analisi dei prodotti infiniti di matrici stocastiche, una componente fondamentale nei protocolli di consenso per il controllo distribuito, la stima e l'ottimizzazione. Sebbene la convergenza di tali prodotti verso una matrice di rango uno sia ben stabilita per specifici "insiemi convergenti" (ad esempio, matrici scrambling, matrici di Sarymsakov), determinare il tasso di convergenza rimane una sfida. Nello specifico, gli autori indagano se seminormi di consenso submoltiplicativi possano essere utilizzati per limitare uniformemente il tasso di convergenza per tutte le matrici all'interno di un dato insieme convergente. Una domanda chiave è se esista una singola seminorma nella quale ogni matrice di un insieme convergente agisca come una contrazione (ovvero, abbia un valore di seminorma strettamente minore di 1), garantendo così una convergenza esponenziale.

Metodologia
Gli autori utilizzano il quadro delle seminorme di consenso, definite sullo sottospazio $M_{n \times n}$ delle matrici con somme di righe uguali. Una seminorma di consenso $|\cdot|$ soddisfa $|M|=0$ se e solo se $M = \mathbf{1}c$ (una matrice di rango uno). L'analisi si basa su:

1. Submoltiplicatività: La proprietà $|M_1 M_2| \leq |M_1||M_2|$, che collega il valore della seminorma al tasso di convergenza.
2. Semiraggio Spettrale Congiunto: Un adattamento originale del raggio spettrale congiunto, definito utilizzando una seminorma di consenso anziché una norma matriciale standard, per caratterizzare il comportamento asintotico dei prodotti infiniti.
3. Argomenti Topologici: Utilizzare la densità di specifici insiemi di matrici (come le matrici stocastiche positive) nello spazio di tutte le matrici stocastiche per derivare contraddizioni riguardanti l'esistenza di seminorme di contrazione uniformi.
4. Proprietà di Hajnal: Sfruttare un risultato noto secondo cui il prodotto di una matrice non-scrambling con una specifica matrice stocastica può essere non-convergente.

Contributi Chiave e Risultati

1. Non Esistenza di Seminorme di Contrazione Uniformi per Insiemi Convergenti Generali
Il saggio perfeziona risultati precedenti per dimostrare che non tutti gli insiemi convergenti ammettono una singola seminorma di consenso submoltiplicativa in cui tutte le matrici siano contrazioni.

• Teorema 1: Per $n > 2$, non esiste una seminorma di consenso submoltiplicativa $|\cdot|$ tale che $|S| < 1$ per ogni $S$ nell'insieme $R$ (matrici stocastiche con diagonali positive e un grafo radicato) o nell'insieme $K$ (matrici di Sarymsakov).
• Teorema 3: Se un insieme convergente $C$ è denso nell'insieme di tutte le matrici stocastiche $S_{n \times n}$, ed esiste una seminorma in cui tutti gli $S \in C$ sono contrazioni, allora $C$ deve essere un sottoinsieme delle matrici scrambling.
• Implicazione: Poiché $R$ e $K$ sono densi in $S_{n \times n}$ ma contengono matrici non-scrambling, nessuna singola seminorma può limitare il tasso di convergenza per tutte le matrici in questi insiemi. Ciò contrasta con l'insieme delle matrici scrambling ($S$) e delle matrici doppia stocastiche con grafi debolmente connessi ($D$), dove tali seminorme (ad esempio, il coefficiente di ergodicità o il secondo valore singolare più grande) esistono.

2. Proprietà di Contrazione del Prodotto Finito
Il saggio stabilisce che, sebbene le singole matrici in un insieme convergente compatto possano non essere contrazioni in una data seminorma, i loro prodotti finiti diventano eventualmente contrazioni.

• Corollario 2: Per ogni insieme convergente compatto $C$ e ogni seminorma submoltiplicativa, esiste un intero finito $k$ tale che il prodotto di qualsiasi $k$ matrici da $C$ sia una contrazione (ovvero, $|S_k \cdots S_1| < 1$).
• Questo risultato generalizza la proprietà nota per le matrici scrambling (dove una lunghezza di prodotto finito garantisce la proprietà scrambling) a tutte le seminorme di consenso.

3. Semiraggio Spettrale Congiunto e Tassi di Convergenza
Gli autori introducono il semiraggio spettrale congiunto $\sigma(C)$, definito come il limite del supremo della radice $t$-esima della seminorma di prodotti di lunghezza $t$.

• Teorema 4: Un insieme compatto $C$ è convergente se e solo se $\sigma(C) < 1$. Inoltre, se $\sigma(C) < 1$, il tasso di convergenza è esponenziale, limitato da $\delta^t$ per ogni $\delta > \sigma(C)$.
• Questo fornisce un meccanismo teorico per limitare i tassi di convergenza anche quando le singole matrici non sono contrazioni, a condizione che il semiraggio spettrale congiunto sia minore di uno.

Significatività e Rivendicazioni
Il saggio sostiene di chiarire i limiti dell'uso di seminorme submoltiplicative per limitare i tassi di convergenza nel consenso distribuito.

• Dimostra che la "bella" proprietà di avere una singola seminorma di contrazione non è universale; fallisce per classi importanti come $R$ e $K$ quando $n > 2$.
• Evidenzia come la capacità di determinare i tassi di convergenza tramite una singola seminorma sia strettamente legata alla densità topologica dell'insieme di matrici e alla proprietà scrambling.
• Il saggio postula che, sebbene le singole matrici possano non essere contrazioni, il comportamento "congiunto" (catturato dal semiraggio spettrale congiunto) assicura che i prodotti finiti diventino eventualmente contrazioni, offrendo una via per i limiti di tasso per gli insiemi convergenti generali.
• Gli autori concludono notando questioni aperte: specificamente, se la proprietà di contrazione del prodotto finito (Corollario 2) si applichi con un $k$ limitato da una funzione della dimensione $n$ per tutte le seminorme, o se esistano seminorme in cui tale limite non esiste.