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

Resumo Técnico: Sobre a Determinação da Taxa de Convergência de um Produto Infinito de Matrizes Estocásticas

Enunciado do Problema
O artigo aborda a análise de produtos infinitos de matrizes estocásticas, um componente fundamental em protocolos de consenso para controle distribuído, estimação e otimização. Embora a convergência de tais produtos para uma matriz de posto um seja bem estabelecida para "conjuntos convergentes" específicos (ex: matrizes de dispersão/scrambling, matrizes de Sarymsakov), determinar a taxa de convergência permanece um desafio. Especificamente, os autores investigam se seminormas de consenso submultiplicativas podem ser usadas para limitar uniformemente a taxa de convergência para todas as matrizes dentro de um determinado conjunto convergente. Uma questão central é se existe uma única seminorma na qual cada matriz de um conjunto convergente atue como uma contração (ou seja, possua um valor de seminorma estritamente menor que 1), garantindo assim a convergência exponencial.

Metodologia
Os autores empregam o arcabouço de seminormas de consenso, definidas no subespaço $M_{n \times n}$ de matrizes com somas iguais por linha. Uma seminorma de consenso $|\cdot|$ satisfaz $|M|=0$ se, e somente se, $M = \mathbf{1}c$ (uma matriz de posto um). A análise baseia-se em:

1. Submultiplicatividade: A propriedade $|M_1 M_2| \leq |M_1||M_2|$, que vincula o valor da seminorma à taxa de convergência.
2. Semirraio Espectral Conjunto: Uma adaptação novel do raio espectral conjunto, definida usando uma seminorma de consenso em vez de uma norma de matriz padrão, para caracterizar o comportamento assintótico de produtos infinitos.
3. Argumentos Topológicos: Utilização da densidade de conjuntos específicos de matrizes (como matrizes estocásticas positivas) no espaço de todas as matrizes estocásticas para derivar contradições em relação à existência de seminormas de contração uniformes.
4. Propriedade de Hajnal: Aproveitamento de um resultado conhecido de que o produto de uma matriz não-scrambling com uma matriz estocástica específica pode não ser convergente.

Principais Contribuições e Resultados

1. Não Existência de Seminormas de Contração Uniformes para Conjuntos Convergentes Gerais
O artigo refina resultados anteriores para provar que nem todos os conjuntos convergentes admitem uma única seminorma de consenso submultiplicativa na qual todas as matrizes sejam contrações.

• Teorema 1: Para $n > 2$, não existe uma seminorma de consenso submultiplicativa $|\cdot|$ tal que $|S| < 1$ para todo $S$ no conjunto $R$ (matrizes estocásticas com diagonais positivas e um grafo enraizado) ou no conjunto $K$ (matrizes de Sarymsakov).
• Teorema 3: Se um conjunto convergente $C$ é denso no conjunto de todas as matrizes estocásticas $S_{n \times n}$, e existe uma seminorma onde todos os $S \in C$ são contrações, então $C$ deve ser um subconjunto das matrizes de dispersão (scrambling matrices).
• Implicação: Como $R$ e $K$ são densos em $S_{n \times n}$ mas contêm matrizes não-scrambling, nenhuma seminorma única pode limitar a taxa de convergência para todas as matrizes nesses conjuntos. Isso contrasta com o conjunto de matrizes de dispersão ($S$) e matrizes duplamente estocásticas com grafos fracamente conectados ($D$), onde tais seminormas (ex: o coeficiente de ergodicidade ou o segundo maior valor singular) de fato existem.

2. Propriedade de Contração de Produto Finito
O artigo estabelece que, embora matrizes individuais em um conjunto convergente compacto possam não ser contrações em uma determinada seminorma, produtos finitos delas eventualmente tornam-se contrações.

• Corolário 2: Para todo conjunto convergente compacto $C$ e toda seminorma de consenso submultiplicativa, existe um inteiro finito $k$ tal que o produto de quaisquer $k$ matrizes de $C$ é uma contração (ou seja, $|S_k \cdots S_1| < 1$).
• Este resultado generaliza a propriedade conhecida para matrizes de dispersão (onde um comprimento de produto finito garante a dispersão) para seminormas de consenso gerais.

3. Semirraio Espectral Conjunto e Taxas de Convergência
Os autores introduzem o semirraio espectral conjunto $\sigma(C)$, definido como o limite do supremo da raiz de ordem $t$ da seminorma de produtos de comprimento $t$.

• Teorema 4: Um conjunto compacto $C$ é convergente se, e somente se, $\sigma(C) < 1$. Além disso, se $\sigma(C) < 1$, a taxa de convergência é exponencial, limitada por $\delta^t$ para qualquer $\delta > \sigma(C)$.
• Isso fornece um mecanismo teórico para limitar taxas de convergência mesmo quando matrizes individuais não são contrações, desde que o semirraio espectral conjunto seja menor que um.

Significância e Alegações
O artigo alega esclarecer as limitações do uso de seminormas submultiplicativas para limitar taxas de convergência em consenso distribuído.

• Demonstra que a propriedade "agradável" de possuir uma única seminorma de contração não é universal; ela falha para classes importantes como $R$ e $K$ quando $n > 2$.
• Destaca que a capacidade de determinar taxas de convergência via uma única seminorma está intimamente ligada à densidade topológica do conjunto de matrizes e à propriedade de dispersão (scrambling).
• O artigo postula que, embora matrizes individuais possam não ser contrações, o comportamento "conjunto" (capturado pelo semirraio espectral conjunto) garante que produtos finitos eventualmente contraiam, oferecendo um caminho para limites de taxa para conjuntos convergentes gerais.
• Os autores concluem observando questões em aberto: especificamente, se a propriedade de contração de produto finito (Corolário 2) ocorre com um $k$ limitado por uma função da dimensão $n$ para todas as seminormas, ou se existem seminormas onde tal limite não existe.