RECORD
Low-rank tensor methods for Markov chains with applications to tumor progression models
Numerical Analysis · Submitted 15 Jun 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We derive a convergent iterative method using low-rank formats satisfying this condition.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Continuous-time Markov chains describing interacting processes exhibit a state space that grows exponentially in the number of processes. This state-space explosion renders the computation or storage of the time-marginal distribution, which is defined as the solution of a certain linear system, infeasible using classical methods. We consider Markov chains whose transition rates are separable functions, which allows for an efficient low-rank tensor representation of the operator of this linear system. Typically, the right-hand side also has low-rank structure, and thus we can reduce the cost for computation and storage from exponential to linear. Previously known iterative methods also allow for low-rank approximations of the solution but are unable to guarantee that its entries sum up to one as required for a probability distribution. We derive a convergent iterative method using low-rank formats satisfying this condition. We also perform numerical experiments illustrating that the marginal distribution is well approximated with low rank.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Continuous-time Markov chains describing interacting processes exhibit a state space that grows exponentially in the number of processes. | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s1 | This state-space explosion renders the computation or storage of the time-marginal distribution, which is defined as the solution of a certain linear system, infeasible using classical methods. | background 0.95 | 0.07 | 0.03 | asserted 1.00 |
| s2 | We consider Markov chains whose transition rates are separable functions, which allows for an efficient low-rank tensor representation of the operator of this linear system. | method 0.58 | 0.31 | 0.10 | asserted 0.97 |
| s3 | Typically, the right-hand side also has low-rank structure, and thus we can reduce the cost for computation and storage from exponential to linear. | result 0.52 | 0.46 | 0.28 | asserted 0.89 |
| s4 | Previously known iterative methods also allow for low-rank approximations of the solution but are unable to guarantee that its entries sum up to one as required for a probability distribution. | gap 0.92 | 0.05 | 0.04 | asserted 1.00 |
| s5 | We derive a convergent iterative method using low-rank formats satisfying this condition. | contribution 0.88 | 0.97 | 0.41 | asserted 1.00 |
| s6 | We also perform numerical experiments illustrating that the marginal distribution is well approximated with low rank. | result 0.90 | 0.97 | 0.19 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Continuous-time Markov chains describing interacting processes exhibit a state space that grows exponentially in the number of processes. This state-space explosion renders the computation or storage of the time-marginal distribution, which is defined as the solution of a certain linear system, infeasible using classical methods. We consider Markov chains whose transition rates are separable functions, which allows for an efficient low-rank tensor representation of the operator of this linear system. Typically, the right-hand side also has low-rank structure, and thus we can reduce the cost for computation and storage from exponential to linear. Previously known iterative methods also allow for low-rank approximations of the solution but are unable to guarantee that its entries sum up to one as required for a probability distribution. We derive a convergent iterative method using low-rank formats satisfying this condition. We also perform numerical experiments illustrating that the marginal distribution is well approximated with low rank.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.