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

Technische Samenvatting: Over het Bepalen van de Convergentiesnelheid van een Oneindig Product van Stochastische Matrices

Probleemstelling
Het artikel behandelt de analyse van oneindige producten van stochastische matrices, een fundamenteel onderdeel in consensusprotocollen voor gedistribueerde controle, schatting en optimalisatie. Hoewel de convergentie van dergelijke producten naar een matrix met rang één goed gevestigd is voor specifieke "convergerende verzamelingen" (bijv. scrambling matrices, Sarymsakov matrices), blijft het bepalen van de convergentiesnelheid een uitdaging. Specifiek onderzoeken de auteurs of submultiplicatieve consensus-seminormen gebruikt kunnen worden om de convergentiesnelheid uniform te begrenzen voor alle matrices binnen een gegeven convergerende verzameling. Een cruciale vraag is of er een enkele seminorm bestaat waarin elke matrix van een convergerende verzameling een contractie is (dat wil zeggen, een seminormwaarde strikt kleiner dan 1 heeft), wat exponentiële convergentie garandeert.

Methodologie
De auteurs maken gebruik van het kader van consensus-seminormen, gedefinieerd op de deelruimte $M_{n \times n}$ van matrices met gelijke rij-sommen. Een consensus-seminorm $|\cdot|$ voldoet aan $|M|=0$ dan en slechts dan als $M = \mathbf{1}c$ (een matrix met rang één). De analyse steunt op:

1. Submultiplicativiteit: De eigenschap $|M_1 M_2| \leq |M_1||M_2|$, die de seminormwaarde koppelt aan de convergentiesnelheid.
2. Joint Spectral Semiradius: Een nieuwe adaptatie van de joint spectral radius, gedefinieerd met behulp van een consensus-seminorm in plaats van een standaard matrixnorm, om het asymptotische gedrag van oneindige producten te karakteriseren.
3. Topologische Argumenten: Het gebruik van de dichtheid van specifieke matrixverzamelingen (zoals positieve stochastische matrices) binnen de ruimte van alle stochastische matrices om tegenstrijdigheden af te leiden met betrekking tot het bestaan van uniforme contractie-seminormen.
4. Hajnal's Eigenschap: Het benutten van een bekend resultaat dat het product van een niet-scrambling matrix met een specifieke stochastische matrix niet-convergent kan zijn.

Belangrijkste Bijdragen en Resultaten

1. Niet-bestaan van Uniforme Contractie-seminormen voor Algemene Convergerende Verzamelingen
Het artikel verfijnt eerdere resultaten om te bewijzen dat niet alle convergerende verzamelingen een enkele submultiplicatieve consensus-seminorm toelaten waarin alle matrices contracties zijn.

• Theorema 1: Voor $n > 2$ bestaat er geen submultiplicatieve consensus-seminorm $|\cdot|$ zodanig dat $|S| < 1$ voor alle $S$ in de verzameling $R$ (stochastische matrices met positieve diagonalen en een gewortelde graaf) of de verzameling $K$ (Sarymsakov matrices).
• Theorema 3: Als een convergerende verzameling $C$ dicht is in de verzameling van alle stochastische matrices $S_{n \times n}$, en er bestaat een seminorm waarin alle $S \in C$ contracties zijn, dan moet $C$ een deelverzameling zijn van de scrambling matrices.
• Implicatie: Omdat $R$ en $K$ dicht zijn in $S_{n \times n}$ maar niet-scrambling matrices bevatten, kan geen enkele enkele seminorm de convergentiesnelheid voor alle matrices in deze verzamelingen begrenzen. Dit staat in contrast met de verzameling scrambling matrices ($S$) en dubbel stochastische matrices met zwak verbonden grafen ($D$), waar dergelijke seminormen (bijv. de coëfficiënt van ergodiciteit of de tweede grootste singuliere waarde) wel bestaan.

2. Eindig Product Contractie-eigenschap
Het artikel stelt vast dat hoewel individuele matrices in een compacte convergerende verzameling in een gegeven seminorm mogelijk geen contracties zijn, eindige producten van hen uiteindelijk contracties worden.

• Corollary 2: Voor elke compacte convergerende verzameling $C$ en elke submultiplicatieve consensus-seminorm bestaat er een eindig integer $k$ zodanig dat het product van een willekeurige $k$ matrices uit $C$ een contractie is (dat wil zeggen, $|S_k \cdots S_1| < 1$).
• Dit resultaat generaliseert de bekende eigenschap voor scrambling matrices (waarbij een eindige productlengte scrambling garandeert) naar algemene consensus-seminormen.

3. Joint Spectral Semiradius en Convergentiesnelheden
De auteurs introduceren de joint spectral semiradius $\sigma(C)$, gedefinieerd als de limiet van het supremum van de $t$-de wortel van de seminorm van producten van lengte $t$.

• Theorema 4: Een compacte verzameling $C$ is convergent dan en slechts dan als $\sigma(C) < 1$. Bovendien, als $\sigma(C) < 1$, is de convergentiesnelheid exponentieel, begrensd door $\delta^t$ voor elke $\delta > \sigma(C)$.
• Dit biedt een theoretisch mechanisme om convergentiesnelheden te begrenzen, zelfs wanneer individuele matrices geen contracties zijn, mits de joint spectral semiradius kleiner is dan één.

Betekenis en Claims
Het artikel beweert de beperkingen te verduidelijken van het gebruik van submultiplicatieve seminormen voor het begrenzen van convergentiesnelheden in gedistribueerde consensus.

• Het toont aan dat de "mooie" eigenschap van het hebben van een enkele contractie-seminorm niet universeel is; het faalt voor belangrijke klassen zoals $R$ en $K$ wanneer $n > 2$.
• Het benadrukt dat het vermogen om convergentiesnelheden te bepalen via een enkele seminorm nauw samenhangt met de topologische dichtheid van de matrixverzameling en de scrambling-eigenschap.
• Het artikel stelt dat hoewel individuele matrices mogelijk geen contracties zijn, het "gezamenlijke" gedrag (gevangen door de joint spectral semiradius) ervoor zorgt dat eindige producten uiteindelijk contrageren, wat een pad biedt naar snelheid-grenzen voor algemene convergerende verzamelingen.
• De auteurs concluderen door op te merken dat er openstaande vragen zijn: specifiek of de eindige product contractie-eigenschap (Corollary 2) standhoudt met een $k$ die begrensd wordt door een functie van dimensie $n$ voor alle seminormen, of dat er seminormen bestaan waarvoor een dergelijke begrenzing niet bestaat.