Clusters in Markov chains via singular vectors of Laplacian matrices

被引：0
|
作者：
Cole, Sam [1 ]
Kirkland, Steve [2 ]
机构：
[1] NielsenIQ, Chicago, IL 60606 USA
[2] Univ Manitoba, Dept Math, Winnipeg, MB, Canada
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2023年 / 660卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Markov chain; Stochastic matrix; Cluster; Left singular vector; Laplacian matrix; Contents; ALGORITHM; SUBSPACE; STATES;
D O I：
10.1016/j.laa.2022.11.015
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Suppose that T is a stochastic matrix. We propose an algo-rithm for identifying clusters in the Markov chain associated with T. The algorithm is recursive in nature, and in order to identify clusters, it uses the sign pattern of a left singular vec-tor associated with the second smallest singular value of the Laplacian matrix I-T. We prove a number of results that jus-tify the algorithm's approach, and illustrate the algorithm's performance with several numerical examples.(c) 2022 Elsevier Inc. All rights reserved.
引用
收藏
页码：1 / 39
页数：39
相关论文
共 39 条
  • [21] State space reconstruction of Markov chains via autocorrelation structure
    Jakovac, Antal
    Kurbucz, Marcell T.
    Telcs, Andras
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2024, 57 (31)
  • [22] Modeling statistical dependence of Markov chains via copula models
    Abegaz, Fentaw
    Naik-Nimbalkar, U. V.
    JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 2008, 138 (04) : 1131 - 1146
  • [23] Direction-of-Arrival Estimation Method for Principal Singular Vectors Based on Multiple Toeplitz Matrices
    Tang, Yaofeng
    Fan, Kuangang
    Lei, Shuang
    Cui, Junfeng
    WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2022, 2022
  • [24] Necessary and sufficient conditions for non-singular invariant probability measures for Feller Markov chains
    Costa, OLV
    Dufour, F
    STATISTICS & PROBABILITY LETTERS, 2001, 53 (01) : 47 - 57
  • [25] LEARNING PROBABILISTIC-AUTOMATA AND MARKOV-CHAINS VIA QUERIES
    TZENG, WG
    MACHINE LEARNING, 1992, 8 (02) : 151 - 166
  • [26] From Diffusions on Graphs to Markov Chains via Asymptotic State Lumping
    Adam Bobrowski
    Annales Henri Poincaré, 2012, 13 : 1501 - 1510
  • [27] POINCARE AND LOGARITHMIC SOBOLEV CONSTANTS FOR METASTABLE MARKOV CHAINS VIA CAPACITARY INEQUALITIES
    Schlichting, Andre
    Slowik, Martin
    ANNALS OF APPLIED PROBABILITY, 2019, 29 (06): : 3438 - 3488
  • [28] DQDB MODELING - PROBLEM COMPLEXITY REDUCTION AND SOLUTION VIA MARKOV-CHAINS
    CONTI, M
    GREGORI, E
    LENZINI, L
    IFIP TRANSACTIONS C-COMMUNICATION SYSTEMS, 1992, 5 : 47 - 62
  • [29] Optimal Kullback-Leibler Aggregation via Spectral Theory of Markov Chains
    Deng, Kun
    Mehta, Prashant G.
    Meyn, Sean P.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2011, 56 (12) : 2787 - 2802
  • [30] ERROR BOUNDS FOR AUGMENTED TRUNCATION APPROXIMATIONS OF MARKOV CHAINS VIA THE PERTURBATION METHOD
    Liu, Yuanyuan
    Li, Wendi
    ADVANCES IN APPLIED PROBABILITY, 2018, 50 (02) : 645 - 669
1234