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

기술 요약: 확률적 행렬의 무한 곱에 대한 수렴 속도 결정에 관하여

문제 정의
본 논문은 분산 제어, 추정 및 최적화의 핵심 요소인 확률적 행렬의 무한 곱 분석을 다룬다. 특정 "수렴 집합"(예: 스크램블링 행렬, 사림사코프(Sarymsakov) 행렬)에 대해 이러한 곱이 랭크-1 행렬로 수렴한다는 것은 잘 알려져 있으나, 그 수렴 속도를 결정하는 것은 여전히 어려운 과제로 남아 있다. 구체적으로, 저자들은 부가적(submultiplicative) 합의 세미노름(consensus seminorm)을 사용하여 주어진 수렴 집합 내의 모든 행렬에 대해 수렴 속도를 균일하게 바운드할 수 있는지 조사한다. 핵심 질문은 모든 행렬이 주어진 세미노름에서 축약(contraction)이 되도록 하는(즉, 세미노름 값이 1보다 작은) 단일 세미노름이 존재하는가 하는 것이며, 이는 지수적 수렴을 보장한다.

방법론
저자들은 행의 합이 동일한 행렬들의 부분 공간 $M_{n \times n}$에서 정의된 합의 세미노로(consensus seminorm) 프레임워크를 사용한다. 합의 세미노름 $|\cdot|$은 $|M|=0$일 때 오직 $M = \mathbf{1}c$(랭크-1 행렬)인 경우에만 성립한다. 분석은 다음 사항들에 기초한다:

1. 부가성(Submultiplicativity): $|M_1 M_2| \leq |M_1||M_2|$라는 성질은 세미노름 값과 수렴 속도를 연결한다.
2. 결합 스펙트럴 세미레이디우스(Joint Spectral Semiradius): 무한 곱의 점근적 거동을 특징짓기 위해 표준 행렬 노름 대신 합의 세미노름을 사용하는, 결합 스펙트럴 레이디우스의 새로운 변형을 정의한다.
3. 위상적 논증: 특정 행렬 집합(양의 확률적 행렬 등)의 모든 확률적 행렬 공간 내에서의 조밀성(density)을 활용하여, 균일한 축약 세미노름의 존재에 대한 모순을 도출한다.
4. Hajnal의 성질: 비스크램블링(non-scrambling) 행렬과 특정 확률적 행렬의 곱이 수렴하지 않을 수 있다는 기지의 결과를 활용한다.

주요 기여 및 결과

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: 모든 압축적 수렴 집합 $C$와 모든 부가적 합의 세미노름에 대하여, $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)이 모든 세미노름에 대해 차원 $n$의 함수로 제한되는 $k$를 갖는지, 아니면 그러한 바운드가 존재하지 않는 세미노름이 존재하는지에 대한 의문을 제기하며 마무리한다.