Pith. sign in

REVIEW 2 major objections 7 minor 40 references

Tensorized algorithms and scalable filtering methods for hidden Markov and factorial hidden Markov models

T0 review · 2 major / 7 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Tensorized filtering cuts fHMM cost from O(M²) to O(M·ΣMₖ)

desk verdict Clean tensorized fHMM filtering with real speedup, but no code and no real-data validation. read the letter →

arxiv 2607.07008 v1 pith:XUOD6YA3 submitted 2026-07-08 stat.ML cs.LG

Roxana Barrios , Ioannis Sgouralis This is my paper
classification stat.MLcs.LG
keywords factorialhiddenMarkovmodeltensoralgebraforwardfilteringcontractionKroneckerproducttime-seriesanalysisViterbidecodingcomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Factorial hidden Markov models (fHMMs) represent time-series driven by multiple independent hidden processes, but standard filtering becomes intractable because the combined state-space grows as the product of subsystem sizes. This paper shows that by keeping the multidimensional tensor structure of an fHMM intact—rather than flattening it into a single large vector as standard HMM conversion does—the forward filtering recursion can be rewritten using successive tensor contractions along each subsystem's mode. The key identity is that the Kronecker-product transition matrix of the equivalent HMM (Eq. 2.17) can be applied not as one O(M²) matrix-vector product but as K separate mode-k contractions, each costing O(M·Mₖ). This drops the per-iteration cost from O(M²) to O(M·ΣMₖ), where M = ΠMₖ, yielding a speedup factor of ΠMₖ/ΣMₖ. The authors prove the tensorized filters produce numerically identical results to standard vectorized filters and confirm this across 10⁶ random parameter settings with discrepancies at machine-epsilon level.

What carries the argument

Kronecker product factorization of fHMM transition matrix (Eq. 2.17); mode-k tensor contraction replacing matrix-vector multiplication (Eq. 3.25); vectorization/inverse-vectorization pair (Eqs. 2.1–2.2) mapping between flattened HMM vectors and folded fHMM tensors; successive mode-k stretch identity (Eq. 2.8) for initial distributions.

What would settle it

Construct an fHMM where subsystems are not independent—for example, where the transition matrix of subsystem k depends on the state of subsystem j≠k—and show that the tensor contraction formula (Eq. 3.25) no longer produces the correct filtered distributions. Alternatively, demonstrate a numerical regime where the tensorized and vectorized algorithms diverge beyond machine precision for independent subsystems, contradicting the claimed equivalence.

Watch

Extended reading notes

Core claim

The central mechanism is the replacement of the single matrix-vector product Π·A_{n−1} (where Π = Π_K ⊗ ··· ⊗ Π_1 is the Kronecker-product transition matrix of size M×M) with K successive mode-k tensor contractions A_{n−1} ×_{1,2} Π_1 ··· ×_{1,2} Π_K, operating on the folded tensor filter Ã_{n−1} = vect⁻¹(A_{n−1}). This is valid because the Kronecker product structure of the transition matrix (Eq. 2.17) and initial distribution (Eq. 2.16) decomposes exactly into independent per-subsystem mode-k products (Eq. 2.9–2.10). The same tensor-stretch decomposition applies to the Viterbi decoding recursion. The result is that an fHMM with K subsystems of sizes M_1,…,M_K can be filtered at cost O(N·M·

Load-bearing premise

The entire speedup rests on the K subsystems evolving independently—each subsystem's transition depends only on its own previous state, not on any other subsystem's state. This independence is what makes the combined transition matrix factor as a Kronecker product. If subsystems are coupled (one chain's transition depends on another's current state), the factorization breaks and the tensor contraction scheme does not apply in its current form.

Editorial extensions

If this is right

  • fHMMs with dozens or hundreds of subsystems—previously intractable—become computable, opening factorial modeling to domains like multi-channel neuroscience, energy disaggregation, and genomics where many independent latent chains are natural.
  • Any Bayesian inference procedure for fHMMs that requires repeated marginal likelihood evaluation (e.g., Metropolis-Hastings, model selection, evidence-based comparison) benefits directly, since each likelihood evaluation now costs O(N·M·ΣMₖ) instead of O(N·M²).
  • The tensor contraction formulation is natively supported by optimized numerical libraries (NumPy, MATLAB), so the speedup is immediately realizable without custom kernels or specialized hardware.
  • The decoding (Viterbi) recursion admits an analogous tensorization, so both evaluation and decoding for fHMMs are accelerated by the same structural insight.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The approach should extend to backward smoothing (the backward pass of forward-backward), since the backward recursion has the same transition-matrix structure and the same Kronecker factorization applies.
  • Online or streaming filtering—where data arrive sequentially and parameters are updated—would benefit disproportionately, since the per-step cost reduction compounds over long time-series.
  • Models with structured coupling between subsystems (e.g., conditional dependencies in transitions) might be partially tensorizable if the coupling is low-rank or sparse, though the exact Kronecker factorization would break.
  • The observation that arranging subsystems in descending size order improves performance (Section 4.1.4) suggests cache or memory-layout effects that could be further optimized by reordering tensor modes dynamically.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The manuscript develops tensorized forward filtering and Viterbi decoding algorithms for factorial hidden Markov models (fHMMs). The key insight is that the Kronecker-product structure of the equivalent HMM's transition matrix (Eq. 2.17) and initial probability vector (Eq. 2.16) can be exploited directly via successive tensor contractions (Eqs. 3.22-3.27), avoiding explicit construction of the exponentially large equivalent HMM state-space. The per-iteration cost is reduced from O(M^2) to O(M * sum(M_k)), where M = prod(M_k). The approach is validated numerically against the standard vectorized algorithm across 10^6 random trials with machine-epsilon agreement (Table 2) and runtime benchmarks confirming the predicted asymptotic scaling (Figures 1-2).

Significance. The paper addresses a well-known computational bottleneck in fHMM inference. The core mathematical contribution—replacing a single Kronecker-structured matrix-vector product with successive mode-k tensor contractions—is clean and correct, resting on standard multilinear algebra identities (Eqs. 2.7-2.10). The numerical validation is thorough: 10^6 repetitions with discrepancies at machine epsilon (Table 2) provide strong evidence of numerical equivalence. The runtime benchmarks (Figures 1-2) empirically confirm the predicted O(N * M * sum(M_k)) scaling. The memory efficiency of avoiding explicit construction of the full transition matrix is a practical strength. The observation in Section 4.1.4 that subsystem ordering affects runtime is a useful practical finding. The methods are directly applicable to marginal likelihood evaluation, which underpins model selection and Metropolis-Hastings-based training in nonconjugate settings, as the authors note in Section 5.

major comments (2)
  1. The paper claims novelty (Section 3.2: 'new tensor based computational algorithms for fHMM that extend beyond the existing literature') but does not discuss or compare against existing fast fHMM implementations, most notably the FactorialHMM package by Schweiger et al. [26], which also exploits the factorial structure for exact inference. The asymptotic complexity of the method in [26] should be compared against the proposed tensorized scheme to clarify what computational advantage, if any, is gained. Without this comparison, the novelty claim is not fully substantiated. At minimum, the authors should state the relationship between their tensor-contraction approach and existing structured approaches, and clarify whether the speedup is relative only to the naive Kronecker-product baseline or also to prior fast methods. This is load-bearing for the paper's positioning as a novel scalable方法
  2. The cost analysis in Eq. (3.28) gives the asymptotic cost as O(N * M * sum(M_k)), but the paper does not discuss the constant factors or overhead associated with successive tensor contractions versus a single matrix-vector product. In practice, for small subsystems or small K, the overhead of K separate contraction operations (each involving reshaping and memory layout operations) may dominate, potentially making the tensorized approach slower than the vectorized one below some crossover point. Figure 1 suggests such a crossover exists at small sizes. The authors should discuss this regime more explicitly, perhaps providing the crossover sizes, so practitioners know when the tensorized approach is beneficial. This does not affect correctness but is important for the practical scalability claims.
minor comments (7)
  1. Table 1: Row 22 reads '21 (2,2,4)' but should read '22 (2,2,4)'. This is a typographical error in the subscript correspondence table.
  2. Section 4 states 'MATLAB (R2026a, update 2)' but reference [30] cites 'MATLAB 2025a, Version R2025a'. Please reconcile the version numbers.
  3. Section 4.1.2: The specific speedup factors cited ('approximately 4500x' and 'approximately 45x') are not directly traceable from Figure 1. Adding a table with measured speedup ratios at representative sizes would strengthen the quantitative claims.
  4. Section 4.1.4: The observation that descending-size ordering (M1 > M2 > M3) is faster is interesting but the explanation is not provided. A brief discussion of why contraction order affects runtime (e.g., intermediate tensor sizes) would strengthen this result.
  5. Section 3.2.2: The Viterbi decoding algorithm for fHMM is presented but its computational complexity is not stated explicitly. For completeness, the asymptotic cost should be compared with the HMM Viterbi cost of O(N * M^2).
  6. The paper does not discuss numerical stability of the tensorized scheme beyond the accuracy benchmark. For very long sequences (large N), the forward filtering recursion involves repeated normalization (Eqs. 3.23, 3.26). A brief remark on log-space implementation or underflow prevention would be welcome, especially given the claim of scalability to large datasets.
  7. Section 2.4.1: The statement 'Each column of Pi corresponds to a departing state, and each row corresponds to a possible arriving state' is a convention choice. Stating this explicitly as a convention (rather than implying it is universal) would be appropriate, as the opposite convention appears in some textbooks.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; derivation is self-contained

full rationale

The paper's central claim—that tensorized fHMM filtering achieves O(N·M·ΣM_k) cost versus O(N·M²) for naive vectorized filtering—follows from a straightforward chain: (1) fHMM subsystem independence (Eq 2.12) implies the combined transition matrix factors as a Kronecker product (Eq 2.17), which is a standard probability result; (2) standard multilinear algebra identities (Eqs 2.7–2.10) relate Kronecker products of matrices to tensor mode-products/contractions; (3) substituting the Kronecker structure into the standard forward filtering recursion (Eqs 3.7–3.12) yields the tensorized recursion (Eqs 3.22–3.27); (4) per-contraction cost O(M·M_k) sums to O(M·ΣM_k) (Eq 3.28). No step reduces to its own output by definition. The numerical validation (Section 4.1.1) compares two independently implemented algorithms across 10^6 repetitions, finding machine-epsilon agreement—this is genuine cross-validation, not a fitted-parameter-renamed-as-prediction pattern. Self-citations to Pressé & Sgouralis [20,27–29] provide background context but are not load-bearing for the mathematical derivation, whose proofs are supplied in supplementary materials. The Kronecker factorization assumption is the defining property of fHMMs (Ghahramani & Jordan 1995, cited as [6]), correctly and transparently stated, not an ansatz smuggled in via self-citation. The derivation is self-contained against an external baseline implementation with no circular reduction identified.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new free parameters, no new axioms beyond the standard fHMM modeling assumptions, and no invented entities. The contribution is purely algorithmic: a reformulation of known filtering recursions using tensor operations that exploits the known Kronecker structure of fHMM transition matrices. All mathematical objects (tensors, Kronecker products, mode-k contractions) are standard.

assumptions (3)
  • domain assumption Markov property per subsystem: p(s_n^k | s_{n-1}^k, s_{n-2}^k, ...) = p(s_n^k | s_{n-1}^k) for each subsystem k (Eq. 2.12)
    This is the defining assumption of fHMMs and is necessary for the transition matrix to factor as a Kronecker product (Eq. 2.17). Without it, the tensor contraction scheme does not apply.
  • domain assumption Conditional independence of subsystems given observations: the emission distribution p(w_n | s_n^{1:K}) may depend on all subsystems but the subsystem transitions do not depend on each other.
    Stated in Section 2.4.2. This is what allows the transition dynamics to factor into separate per-subsystem transition matrices.
  • standard math Standard multilinear algebra identities: Kronecker product properties, tensor contraction definitions, and the correspondence between Kronecker products and outer products (Eqs. 2.7-2.10).
    These are well-established results in multilinear algebra (cited: Kolda & Bader 2009, De Lathauwer et al. 2000). The paper uses them to derive the tensorized filtering recursions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tensorized algorithms and scalable filtering methods for hidden Markov and factorial hidden Markov models." pith.science (2026). https://pith.science/paper/XUOD6YA3

@misc{pith2026260707008,
  author       = {Pith},
  title        = {Pith review of: Tensorized algorithms and scalable filtering methods for hidden Markov and factorial hidden Markov models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XUOD6YA3}},
  note         = {Machine review of arXiv:2607.07008}
}
read the original abstract

A common method for the representation and analysis of time-series data is the hidden Markov model (HMM), where each observation is associated with a hidden state that evolves over time. However, many real-world systems are influenced by multiple independent factors, which are more naturally represented by factorial hidden Markov models (fHMM), where several hidden Markov chains jointly generate the observed data. Although an fHMM provides a richer and more realistic representation of many real-world systems, it can be reformulated as an equivalent HMM, but with a significantly larger state-space, leading to a severe increase in computational cost. In particular, the forward filtering algorithm, which is central to evaluation, decoding, and estimation tasks, becomes prohibitively expensive even for small systems. This work focuses on developing scalable methods for time-series analysis using tensor algebra to exploit the multidimensional structure of fHMM directly, without constructing intermediate HMM representations. Our novel filtering approach significantly improves computational performance and enables the efficient analysis of large systems and datasets, extending the scope of fHMM and providing a practical framework for data intensive applications.

Figures

Figures reproduced from arXiv: 2607.07008 by the authors.

Figure 1
Figure 1. , the vectorized algorithm allows only tests up to 27 indicating a much narrowed score of possible applications in size-critical scenarios. 100 105 M 1 10-4 10-2 100 102 wall time (sec) 100 105 M 2 10-4 10-2 100 102 wall time (sec) 100 105 M 3 10-4 10-2 100 102 wall time (sec) 100 105 N 10-4 10-2 100 102 wall time (sec) vectorized algorithm tensorized algorithm [PITH_FULL_IMAGE:figures/full_fig_p019_1.png] view at source ↗
Figure 2
Figure 2. Assessment of the runtime perfor￾mance of the vectorized and tensorized filtering algo￾rithms. In this figure all sizes M1:3 are equal to R and vary simultaneously. Dashed lines indicate the theoretically derived asymptotic costs which increase sextically and quartically for the vectorized and ten￾sorized algorithms, respectively. 10 1 10 2 10 3 m 10 -3 10 -2 10 -1 10 0 10 1 10 2 wall time (sec) M 1<M 2<M 3 M 1>M 2>… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [26]

    Computational Statistics and Data Analysis , year =

    Liu, Wei and others , title =. Computational Statistics and Data Analysis , year =

    work page

  2. [1]

    R., Millman , K

    Charles R. Harris and K. Jarrod Millman and St. Array programming with. 2020 , month = sep, journal =. doi:10.1038/s41586-020-2649-2 , publisher =

    work page doi:10.1038/s41586-020-2649-2 2020

  3. [2]

    Journal of Biomedical Optics , year =

    Förster, Theodor , title =. Journal of Biomedical Optics , year =. doi:10.1117/1.JBO.17.1.011002 , pmid =

    work page doi:10.1117/1.jbo.17.1.011002

  4. [3]

    Wieb , title =

    van der Meer, B. Wieb , title =. FRET - Förster Resonance Energy Transfer: From Theory to Applications , editor =. 2013 , chapter =. doi:10.1002/9783527656028.ch03 , url =

    work page doi:10.1002/9783527656028.ch03 2013

  5. [4]

    and Schmid, S

    Hellenkamp, B. and Schmid, S. and Doroshenko, O. and Opanasyuk, O. and K. Precision and accuracy of single-molecule. Nature Methods , volume =. 2018 , doi =

    work page 2018

  6. [5]

    , title =

    Ghahramani, Zoubin and Jordan, Michael I. , title =. Advances in Neural Information Processing Systems , volume =. 1995 , url =

    work page 1995

  7. [6]

    SIAM Journal on Matrix Analysis and Applications , volume =

    De Lathauwer, Lieven and De Moor, Bart and Vandewalle, Joos , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2000 , month = jul, doi =

    work page 2000

  8. [7]

    and Bader, Brett W

    Kolda, Tamara G. and Bader, Brett W. , title =. SIAM Review , volume =. 2009 , doi =

    work page 2009

Show all 40 references
  1. [8]

    and Kolda, Tamara G

    Bader, Brett W. and Kolda, Tamara G. , title =. 2007 , doi =

    2007

  2. [9]

    2005 , url =

    Kyriazis, Marios , title =. 2005 , url =

    2005

  3. [10]

    2020 , howpublished =

    Evans, Benjamin , title =. 2020 , howpublished =

    2020

  4. [11]

    Data Modeling for the Sciences: Applications, Basics, Computations , publisher =

    Press. Data Modeling for the Sciences: Applications, Basics, Computations , publisher =. 2023 , doi =

    2023

  5. [12]

    , title =

    Bishop, Christopher M. , title =. 2006 , isbn =

    2006

  6. [13]

    , title =

    Little, Max A. , title =. 2023 , isbn =

    2023

  7. [14]

    , title =

    Rabiner, Lawrence R. , title =. Proceedings of the IEEE , volume =. 1989 , month = feb, doi =

    1989

  8. [15]

    An Introduction to Infinite

    Sgouralis, Ioannis and Press. An Introduction to Infinite. Biophysical Journal , volume =. 2017 , issn =. doi:10.1016/j.bpj.2017.04.027 , url =

    2017 doi

  9. [16]

    2004 , publisher=

    Monte Carlo statistical methods , author=. 2004 , publisher=

    2004

  10. [17]

    2001 , publisher=

    Monte Carlo strategies in scientific computing , author=. 2001 , publisher=

    2001

  11. [18]

    Biophysical Journal , volume =

    Sgouralis, Ioannis and Press. Biophysical Journal , volume =. 2017 , issn =. doi:10.1016/j.bpj.2017.04.009 , url =

    2017 doi

  12. [19]

    , title =

    Murphy, Kevin P. , title =. 2012 , isbn =. doi:10.1007/978-0-387-46312-4 , url =

    2012 doi

  13. [20]

    2025 , note =

    Barrios, Roxana and Sgouralis, Ioannis , title =. 2025 , note =

    2025

  14. [21]

    and Press

    Sgouralis, Ioannis and Madaan, Shreya and Djutanta, Franky and Kha, Rachael and Hariadi, Rizal F. and Press. A Bayesian Nonparametric Approach to Single Molecule F. The Journal of Physical Chemistry B , volume =. 2019 , doi =

    2019

  15. [22]

    , title =

    Lakowicz, Joseph R. , title =. 1999 , address =

    1999

  16. [23]

    Applied and Computational Mathematics , year =

    Baranon, Mouhamadou Djima and Weke, Patrick Guge Oloo and Alladatin, Judicael and Ale, Boni Maxime and Langat, Amos Kipkorir , title =. Applied and Computational Mathematics , year =

  17. [24]

    Bioinformatics , year =

    Schweiger, Regev and Erlich, Yaniv and Carmi, Shai , title =. Bioinformatics , year =

  18. [25]

    and Nicholson, Ann E

    Rahman, Mohammad S. and Nicholson, Ann E. and Haffari, Gholamreza , title =. Journal of Computational Biology , year =

  19. [27]

    IET Signal Processing , year =

    Paeng, Jin Wook and Kwon, Junseok , title =. IET Signal Processing , year =

  20. [28]

    and Williamson, Sinead A

    Gong, Yiwei and Mierau, Susanna B. and Williamson, Sinead A. , title =. arXiv preprint arXiv:2411.04229 , year =

    arXiv

  21. [29]

    and Neubauer, Catherine E

    Orlov-Savko, Liubove and Jain, Abhinav and Gremillion, Gregory M. and Neubauer, Catherine E. and Canady, Jonroy D. and Unhelkar, Vaibhav , title =. Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , year =

  22. [30]

    Journal of Building Engineering , year =

    Liu, Siqi and Xie, Zhiyuan and Hu, Zhengwei , title =. Journal of Building Engineering , year =

  23. [31]

    Statistika: Statistics and Economy Journal , year =

    Saidane, Mohamed , title =. Statistika: Statistics and Economy Journal , year =

  24. [32]

    , title =

    Kumar, Partik and Abhyankar, Abhijit R. , title =. IEEE Transactions on Smart Grid , year =

  25. [33]

    IEEE Transactions on Smart Grid , year =

    Yan, Lei and Tian, Wei and Han, Jiayu and Li, Zuyi , title =. IEEE Transactions on Smart Grid , year =

  26. [34]

    IEEE Transactions on Audio, Speech, and Language Processing , year =

    Jean-Louis Durrieu and Jean-Philippe Thiran , title =. IEEE Transactions on Audio, Speech, and Language Processing , year =

  27. [35]

    IEEE Transactions on Audio, Speech, and Language Processing , year =

    Michael Wohlmayr and Michael Stark and Franz Pernkopf , title =. IEEE Transactions on Audio, Speech, and Language Processing , year =

  28. [36]

    Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation , year =

    Srivatsan Ramanujam and Jason Baldridge , title =. Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation , year =

  29. [37]

    Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics , year =

    Dingcheng Li and Tim Miller and William Schuler , title =. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics , year =

  30. [38]

    Journal of Business & Economic Statistics , year =

    Maciej Augustyniak and Luc Bauwens and Arnaud Dufays , title =. Journal of Business & Economic Statistics , year =

  31. [39]

    2025 , note =

    MATLAB 2025a , author =. 2025 , note =

    2025

  32. [40]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan , title =

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.