Feature request / implementation guidance: Sparse HMM transition matrices

I'd like to extend the hidden Markov model implementation so that it can handle transition matrices that are very sparse.

For my usecase, I'd like to extend it such that computations with thousands of states are possible (where most transitions are impossible). This will also aid in resolution of https://github.com/tensorflow/probability/issues/1435 as it's possible to approximate HSMMs as HMMs [R. Langrock, W. Zucchini, 2011].

Questions:

• Would anyone know how feasible it is to achieve this and if this would provide gains over the current implementation?
• What would this involve? Would it be possible to use tensorflow's sparse tensors or perhaps linear operators?
• Would any help be possible? No worries if not, but I would love pointers on how to get started on this.

Start by examining the existing hidden Markov model implementation and how it represents transition matrices. Investigate whether TensorFlow sparse tensors or linear operators can support the requested computations, using the HSMM approximation context and issue #1435 as background. Done would mean enabling efficient HMM computations with thousands of states and very sparse transitions.