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

技術要約：確率行列の無限積における収束率の決定について

問題提起
本論文は、分散制御、推定、および最適化におけるコンセンサス・プロトコルの基本要素である、確率行列の無限積の解析を取り扱う。特定の「収束集合」（スクランブリング行列やサリムサコフ行列など）に対して、そのような積がランク1の行列に収束することは十分に確立されているが、その「収束率」を決定することは依然として困難な課題である。具体的には、劣乗法的（submultiplicative）なコンセンサス・セミノルムを用いることで、与えられた収束集合内のすべての行列に対して収束率を一様に抑え込むことができるか否かを調査している。鍵となる問いは、ある収束集合内のすべての行列が（すなわち、セミノルムの値が1未満となる）縮小写像として作用するような単一のセミノルムが存在するかどうかであり、これが指数関数的な収束を保証することになる。

手法
著者らは、行和が等しい行列の空間 $M_{n \times n}$ 上で定義されたコンセンサス・セミノルムの枠組みを用いている。コンセンサス・セミノルム $|\cdot|$ は、$M = \mathbf{1}c$（ランク1の行列）である場合に限り $|M|=0$ となる。分析は以下の要素に基づいている：

1. 劣乗法性（Submultiplicativity）: 性質 $|M_1 M_2| \leq |M_1||M_2|$ は、セミノルムの値と収束率を結びつける。
2. 結合スペクトル・セミラジアス（Joint Spectral Semiradius）: 標準的な行列ノルムではなく、コンセンサス・セミノルムを用いて定義された、無限積の漸近的挙動を特徴付けるための、ジョイント・スペクトル・半径の新たな適応版。
3. 位相的議論: 特定の行列集合（正の確率行列など）の全確率行列空間内における密度を利用して、一様な縮小セミノルムの存在に関する矛盾を導き出す。
4. Hajnalの性質: 非スクランブリング行列と特定の確率行列の積が非収束となり得るという既知の結果を活用する。

主要な貢献と結果

1. 一般的な収束集合に対する一様縮小セミノルムの非存在
本論文は、すべての収束集合が、すべての行列を縮小写像とする単一の劣乗的コンセンサス・セミノルムを持つわけではないことを証明するために、先行研究の結果を精緻化している。

• 定理1: $n > 2$ の場合、集合 $R$（正の対角成分と根付きグラフを持つ確率行列）または集合 $K$（サリムサコフ行列）のすべての $S$ に対して $|S| < 1$ となるような劣乗的コンセンサス・セミノルム $|\cdot|$ は存在しない。
• 定理3: 収束集合 $C$ が全確率行列集合 $S_{n \times n}$ において稠密であり、かつすべての $S \in C$ が縮小写像となるセミノルムが存在する場合、$C$ はスクランブリング行列の部分集合でなければならない。
• 示唆: $R$ および $K$ は $S_{n \times n}$ において稠密であるが、非スクランブリング行列を含んでいるため、これらの集合内のすべての行列の収束率を一様に抑え込む単一のセミノルムは存在しない。これは、スクランブリング行列の集合 ($S$) や、弱連結グラフを持つ二重確率行列の集合 ($D$) において、そのようなセミノルム（例えば、エルゴディシティ係数や第2最大特異値など）が存在することとは対照的である。

2. 有限積の縮小特性
本論文は、コンパクトな収束集合内の個々の行列は、与えられたセミノルムにおいて縮小写馬ットではない場合があるものの、それらの有限の積は最終的に縮小写像になることを確立している。

• 系2: すべてのコンパクトな収束集合 $C$ とすべての劣乗的コンセンサス・セミノルムに対して、任意の $k$ 個の行列の積が縮小写像（すなわち $|S_k \cdots S_1| < 1$）となるような有限の整数 $k$ が存在する。
• この結果は、スクランブリング行列（有限の積の長さがスクランブリングを保証する）に関する既知の性質を、一般的なコンセンサス・セミノルムへと一般化したものである。

3. 結合スペクトル・セミラジアスと収束率
著者らは、長さ $t$ の積のセミノルムの $t$ 乗根の上限の極限として定義される結合スペクトル・セミラジアス $\sigma(C)$ を導入している。

• 定理4: コンパクトな集合 $C$ が収束するための必要十分条件は $\sigma(C) < 1$ である。さらに、$\sigma(C) < 1$ であれば、収束率は指数関数的であり、$\delta^t$ （ただし $\delta > \sigma(C)$）によって抑えられる。
• これは、個々の行列が縮小写像でなくても、結合スペクトル・セミラジアスが1未満であれば、有限の積が最終的に縮小することを保証し、収束率を抑え込むための理論的メカニズムを提供する。

意義と主張
本論文は、分散コンセンサスにおける収束率を抑え込むための劣乗的セミノルムの使用に関する限界を明らかにすることを主張している。

• 「良好な」性質である「単一の縮小セミノルムを持つこと」は普遍的なものではないことを示している。これは、$n > 2$ の場合、$R$ や $K$ といった重要なクラスにおいて失敗する。
• 単一のセミノルムを通じて収束率を決定できる能力は、行列集合の位相的な密度およびスクランブリング特性と密接に関連していることを強調している。
• 個々の行列は縮小写像ではないかもしれないが、「結合的」な挙動（結合スペクトル・セミラジアスによって捉えられる）は、有限の積が最終的に縮小することを保証しており、これが一般の収束集合に対するレート境界への道筋となる。
• 著者らは、未解決の問いとして、特に、有限積の縮小特性（系2）において、$k$ がすべてのセミノルムに対して次元 $n$ の関数によって抑えられるのか、あるいはそのような境界が存在しないセミノルムが存在するのか、という点を挙げている。