An approximation theory for Markov chain compression

Mark Fornace; Michael Lindsey

REVIEW 1 major objections 4 minor 1 cited by

An approximation theory for Markov chain compression

T0 review · 1 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper proves that any reversible Markov chain can be compressed to a selected subset of states with a rigorously controlled recovery error that decays as $1/t$, with no spectral-gap assumption.

desk verdict First rigorous full-dynamics error bounds for reversible Markov chain compression; proofs check out, numerics are honest, and the main caveat is the slow-mode assumption, not the math. read the letter →

arxiv 2506.22918 v3 pith:JE4LCYSX submitted 2025-06-28 math.NA cs.NAmath.PR

Mark Fornace , Michael Lindsey This is my paper · ORCID

classification math.NAcs.NAmath.PR MSC 65C4060J2765F5515A18

keywords MarkovchaincompressionNyströmapproximationcolumnsubsetselectionerrorboundscommittorfunctionsstatemodelsnuclearnormreversiblechains

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

The paper develops an approximation theory for compressing reversible Markov chains: given a subset of selected states, it constructs reduced dynamics that can be lifted back to the full state space, and it proves explicit spectral and nuclear norm bounds on how much the lifted dynamics differ from the exact dynamics over time. The central claim is that the recovery error is bounded by a constant times a Nyström approximation error of the pseudo-inverse Laplacian, divided by time. Because that Nyström error can be controlled by a recently introduced column subset selection algorithm, the bounds are algorithmically actionable: they certify reduced models a priori. The paper presents two compression schemes, a projective one based on committor functions and a structure-preserving one that keeps a Markov-chain interpretation, and validates both numerically on large systems.

What carries the argument

The load-bearing identity is a contour integral representation of the matrix exponential, $e^{-Lt} = \frac{1}{2\pi i} \oint e^{-1/z}(zI - K/t)^{-1}\,dz$, which converts the difference of two dynamics into the difference of two resolvents. That difference is bounded by the Nyström error $\varepsilon(I)$ of the kernel $K = L^+$ (or the killed-chain limit of it), and a universal contour integral gives the constant $3\sqrt{3}/(2\pi)$. For the structure-preserving scheme, a marked chain over an augmented state space supplies orthogonal projectors $W$ and $Q$ satisfying $Q^\top W = C$, so that the non-orthogonal compression becomes an orthogonal projection in a lifted space; the additional price is an obliqueness term $\psi_*(I) \leq |I|\varepsilon_*(I)$, controlled through mean first passage times.

What would settle it

Diagonalize a reversible chain with many comparable slow modes, such as a ring of weakly connected metastable clusters, pick a small subset $I$, compute the exact dynamics $P(t)$ and the compressed dynamics $P_I(t)$, and check whether the actual recovery error exceeds $\frac{3\sqrt{3}}{2\pi}\,\frac{\varepsilon_2(I)}{t}$ at any time after the initial transient; if it does, the central bound is false.

Watch

Extended reading notes

Core claim

For a reversible Markov chain with symmetric Laplacian generator $L$ and a nonempty set $I$ of selected states, the projectively compressed dynamics $P_I(t) = V e^{-V^\top L V t} V^\top$ with $V$ an orthonormal basis of the committor matrix recover the exact dynamics $P(t) = e^{-Lt}$ up to $\|P(t) - P_I(t)\|_{2,*} \leq \frac{3\sqrt{3}}{2\pi}\, \frac{\varepsilon_{2,*}(I)}{t}$, where $\varepsilon_{2,*}(I)$ is the Nyström approximation error of the fundamental matrix $K = L^+$ in the spectral and nuclear norms, defined through a killed-chain limit. The structure-preserving compression $P^{\mathrm{sp}}_I(t) = C e^{-C^\top L C t} C^\top$ obeys $\|P^{\mathrm{sp}}_I(t) - P(t)\|_* \leq \left(\frac{3\sqrt{3}}{2\pi} + |I|\frac{2}{\pi}\right) \frac{\varepsilon_*(I)}{t}$. If correct, these are the first rigorous, computable bounds on full time-dependent recovery error for Markov chain compression, and they require no spectral gap assumption.

Load-bearing premise

The selected subset $I$ must make the Nyström error of the pseudo-inverse kernel small, which in practice requires the chain to have few dominant slow modes relative to the subset size.

Editorial extensions

If this is right

Reduced Markov state models come with a priori, computable error certificates for all but the fastest and the infinitely late timescales.
The error decays as $1/t$, so once the unselected fast modes have relaxed, projected and structure-preserving compressions track the full dynamics quantitatively.
Column subset selection by nuclear maximization makes the bounds algorithmic and nearly optimal, with almost-linear scaling in the number of graph edges.
Structure preservation guarantees entrywise nonnegative, row-stochastic lifted dynamics, so the reduced model remains interpretable as a Markov chain over selected states.
Autocorrelation functions of any observable are approximated with the same norm bounds, connecting the theory to standard Markov state model validation practice.

Reading between the lines

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

Beyond the paper: the $1/t$ bound suggests a natural timescale separation criterion, namely select $I$ so that $\varepsilon(I)$ is small compared to the observation time $t$; this could be turned into an adaptive state-selection rule that the paper does not explicitly propose.
Beyond the paper: the same contour-integral and killed-chain machinery may extend to continuous state spaces through an initial basis projection step, using the singular-extension theorem, although the paper only sketches that direction.
Beyond the paper: because $\varepsilon_*$ involves the pseudo-inverse kernel $L^+$, the quality of the reduced model is tied to mean first passage times; one could plausibly design subset-selection criteria based directly on hitting-time statistics, a connection the paper leaves implicit.

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.

Desk Editor's Note

read the letter

The real news here is Theorem 2 and Theorem 3: for reversible chains, the recovery error of both projective and structure-preserving compression of P(t) = e^{-Lt} is bounded by a constant times the Nyström error of the pseudo-inverse kernel divided by t. That is the first rigorous, computable control on the full time-dependent dynamics rather than just eigenvalue or long-time limits. The contour-integral mechanism is genuinely new, and the marked-chain analysis for the structure-preserving case is clever without being gimmicky.

Credit where due: every main theorem has a complete proof in the appendices, and I spot-checked the resolvent difference and the contour optimization (the 3\sqrt{3}/2\pi constant) and found them correct. The numerical experiments compare against exact diagonalization on systems up to n=10^4 and against trajectory averages on a 10^6-state system; they are validating, not fitted. The a posteriori bounds in Theorem 3* are honestly computable and empirically tight. That is real evidence.

The soft spots are real but proportionate. First, the bounds are vacuous as t -> 0 and t -> infinity; the paper says this explicitly in Section 2.2, so it is not hidden. Second, the a priori control rests on Theorem 4B, which bounds the Nyström error by the nuclear eigenvalue tail of K = L^+. For a chain with many comparable slow modes, that tail is of order Tr[K], and the bound degrades to something no better than trivial. The phrase "algorithmically controllable" is thus somewhat stronger than what the theory actually delivers for a generic spectrum; the control is inherited from a tail assumption that is not quantified for typical MSM spectra. That is a domain-restriction caveat, not a proof flaw. Third, the |I| factor in Theorem 3 is empirically loose, which the authors admit in Section 6.1.

The load-bearing premise is that some small subset I makes the Nyström error small. That is exactly the standard MSM motivation, and the paper's contribution is to convert that premise into a clean error bound rather than to guarantee the premise. Given that the proofs are internally consistent and the numerics are genuine, I think the central argument holds up.

Who is this for? People working on Markov state models, coarse-graining, or Nyström approximation who want a rigorous framework with honest error control. It deserves a serious referee and should be published after minor revision. I would take it to reading group.

Referee Report

1 major / 4 minor

Summary. The paper develops an approximation theory for compressing reversible Markov chains. For a symmetric positive semidefinite Laplacian L obtained from a reversible chain, the authors define a projective compression P_I(t) based on Nyström approximation of the pseudoinverse K = L^+, and a structure-preserving compression P_I^sp(t) based on an induced chain over a selected subset I. The main results, Theorems 1-3, bound the recovery error by constants times the Nyström error ε(I) divided by t, with no spectral gap assumption. The paper also gives an a posteriori bound (Theorem 3*), an a priori selection guarantee via nuclear maximization (Theorems 4A and 4B), and numerical experiments on three systems of up to about 10^6 states.

Significance. If the results hold, this is the first rigorous, non-asymptotic approximation theory for the full time-dependent recovery error in Markov chain compression, connecting a Markov-chain problem to column subset selection and nuclear maximization. The paper provides complete proofs, several independently useful constructions (induced chain, marked chain, obliqueness norm), a posteriori bounds that are computable in practice, and an open-source implementation with reproducible experiments on webgraph and nucleic-acid secondary-structure systems. The main weakness is that the a priori control of ε(I) via Theorem 4B can be vacuous when the spectral tail of K decays slowly, so the practical guarantee is conditional on the existence of a small subset with small Nyström error; this is a domain restriction rather than an internal inconsistency.

major comments (1)

[Appendix B.2, proof of Theorem 2] The proof asserts that P_{I,γ}(t) = e^{-γt} P_I(t) for γ > 0. This identity is false in general: V_γ = orth((K_γ)_{:,I}) differs from V = orth(K_{:,I}) for finite γ, and one can check that V_γ^T L_γ V_γ ≠ V^T L V + γ I. For example, with L = [[2,-1],[-1,2]], I = {1}, γ = 1, a direct calculation gives V_γ^T L_γ V_γ = 2.4 while V^T L V + γ = 2.2. Consequently, the triangle inequality that follows does not control the desired quantity ∥P(t) - P_I(t)∥. The theorem is nevertheless salvageable by a simpler argument: apply Theorem 1 to the positive definite pair (L_γ, V_γ) to obtain ∥P_γ(t) - P_{I,γ}(t)∥ ≤ (3√3/(2π)) ε_γ(I)/t, and then pass γ → 0, using P_γ(t) → P(t), P_{I,γ}(t) → P_I(t), and ε_γ(I) → ε(I). This repair preserves the statement of Theorem 2 and its later use in Theorem 3* and Theorem 3, but the proof as written needs correction.

minor comments (4)

[Theorem 4B and Lemma E.1] The display of Theorem 4B appears to have a missing parenthesis in the second term; it should read ((s+1)/(s-r))(Tr[K] - Tr^{(r)}[K]) as in the proof. Similarly, the statement of Lemma E.1 writes Tr^{(k)}[K] where the proof uses Tr^{(r)}[K]; this is likely a typo.
[Abstract and Section 1.1] The phrase "algorithmically controllable bounds" is somewhat overstated: the a priori control via Theorem 4B is vacuous when the tail Tr[K] - Tr^{(r)}[K] is of order Tr[K], which is exactly the regime where no small subset can make ε(I) small. The body of the paper is careful about this, but the abstract and contributions section should qualify the claim, for instance by saying the bounds are controllable when the Nyström error is small, or by referring to the spectral-tail condition.
[Figure 4 caption] The caption refers to a "theoretical lower bound derived from the eigenvalues of L^+" without defining it; please state the formula for this lower bound in the caption or in the text.
[Notation throughout] The symbol P_I(t) is used both for the projective compression in Section 3 and for the general compression in Section 2, and the notation ∥·∥_{2,*} is introduced but not defined in the abstract; a brief reminder near the first use in the main text would help readers.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the recovery bounds are proven in-paper and hold for arbitrary subsets; the only inherited ingredient is the subset-selection guarantee from prior work, which is not assumed in the error theorems.

full rationale

The derivation chain for the central claims is self-contained. Theorem 1 is proved from Cauchy's integral formula, the refactoring identity (Lemma 2.2), and the resolvent bound (Lemma 2.3); the error constant is evaluated by an explicit contour optimization, and the discrepancy is expressed as a difference of resolvents whose norm is exactly epsilon/t via Eq. (24). Theorems 2 and 3 extend this to the Markov setting by a killed-chain limit (Lemmas 3.2 and B.2) and by a marked-chain/projection argument (Proposition 4.10, Lemma 4.12), respectively, and the obliqueness bound psi <= |I| epsilon is proved by a renewal-reward bijection in Proposition 4.14. No parameter is fitted to data, and no prediction is a renamed input: the compressed dynamics are defined directly from the selected subset I and the committor matrix C, and the theorems hold for every nonempty I and every t > 0 rather than only for optimized subsets. The only inherited ingredient is the a priori control of epsilon(I) by nuclear maximization, cited from the authors' prior work [28] (Theorem 4A) and extended here as Theorem 4B; that guarantee concerns the column subset selection problem and does not assume the recovery bounds of this paper, so it is external evidence rather than a circular step. The acknowledged limitation that the bounds are informative only when epsilon(I) is small (which requires few dominant slow modes) is a domain-restriction caveat, not a definitional or fitted-input circularity.

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

The theorems are parameter-free: they hold for every nonempty subset I, and the error is expressed through the Nyström error ε(I) of the (killed-limit) fundamental matrix K = L^+. No constants are fitted to data; the free parameters listed (subset size k, score tolerance ζ, sketching dimension z) are algorithmic choices that do not appear in the main bounds except through ε(I) and the |I| factor. The axioms are the domain restrictions (irreducibility, reversibility, finite state space) and standard cited results (matrix functional calculus, renewal theorems, DPP expectation bounds). The only axiom imported from the authors' own work is Theorem 4A of [28], which is disclosed as a restatement and used solely for the a priori control of ε_*; the central Theorems 1-3 do not rely on it.

free parameters (3)

subset size k = |I| = k = 5 in Figures 5-6; up to 100 in Figure 4
Model-size parameter chosen by the user or algorithm. The error bounds (Theorems 1-3*) hold for every nonempty I; k enters only through ε(I) and the |I| factor in Theorem 3. Not fitted to data.
relative error ζ in nuclear score estimation = ζ ≥ 0 allowed in Algorithm 1; value not specified numerically in the experiments
Tolerance for the greedy score estimates inherited from [28]; affects only the constants in Theorems 4A/4B. Not fitted to data.
sketching dimension z = z = 200 random vectors for Systems 2-3; z = O(log n) in the theory
Randomized sketch size for score estimation; an implementation parameter that does not appear in the main error bounds. Not fitted to make the bounds hold.

assumptions (6)

domain assumption The Markov chain is irreducible and reversible (satisfies detailed balance)
Sections 1.4 and 3.1. Reversibility is required for the symmetrized Laplacian L = -diag(h)R diag^{-1}(h); irreducibility gives the unique stationary distribution and the committor interpretation. All theorems are stated for this class.
domain assumption Finite discrete state space [n]
Section 1.4. The entire framework (matrices, Nyström approximation, stopping times) is finite-dimensional; continuous state spaces are deferred to future work (Section 1.1).
standard math Matrix functional calculus (Cauchy integral formula applied to matrix exponentials)
Lemma 2.1 and Equation (15) in Section 2.2 use e^{-s^{-1}} = (1/2πi)∮ e^{-1/z}(z-s)^{-1} dz for matrices with spectra in the right half-plane.
standard math Renewal-reward theorem (Aldous-Fill Proposition 2.3) and elementary renewal theorem
Equations (91), (95), and (96) in the proof of Proposition 4.14 relate cycle counts and expected cycle lengths; these classical results are cited to [2] and [56].
standard math DPP expectation bound E_k^DPP(M) ≤ (1 + r/(k-r+1))(Tr[M] - Tr^{(r)}[M]) and Schur concavity of the DPP expectation
Appendix E, used to prove Lemma E.1 and Theorem 4B; cited to [3, 10, 15, 35] and Schur [62].
domain assumption Theorem 4A of [28]: nuclear maximization is exponentially close to optimal subset selection for Laplacians
Section 5 and Appendix E. The a priori control of ε_*(I) is inherited from the authors' prior work [28] and is disclosed as a restatement. The core Theorems 1-3 do not depend on it.

invented entities (3)

Marked chain M°_I (last-visited-state labeling of the original chain) independent evidence
purpose: Augmented-space Markov chain used to derive the structure-preserving compression as an orthogonal projection of marked-chain dynamics and to prove Theorem 3 (Section 4.3, Proposition 4.10).
Fully specified: rate matrix and stationary distribution in Proposition 4.8, eigenvalues in Proposition 4.9, so every claimed property is checkable. It is a mathematical construction, not a new physical entity.
Induced chain M_I over the selected states independent evidence
purpose: Structure-preserving reduced dynamics with rate matrix R̂ = C̃^T R C̃ (Section 4.1); its symmetrized generator is L̂ = C^T L C, giving P^sp_I(t) = C e^{-L̂t} C^T.
Generalizes the known Aldous-Fill construction for the strict-partition case to soft committor weights; exact preservation of mean first passage times on I is proved (Corollary C.3), and its dynamics are directly simulable.
Obliqueness norm ψ(I) = ||L̂^{-1/2}(I - C^T C)L̂^{-1/2}|| independent evidence
purpose: Quantifies non-orthogonality of the committor compression; appears in the a posteriori Theorem 3* bounds (Definition 5).
Closed forms in terms of the fundamental matrix (Proposition C.15) and hitting times (Proposition 4.13) make it computable a posteriori from K alone.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An approximation theory for Markov chain compression." pith.science (2026). https://pith.science/paper/JE4LCYSX

@misc{pith2026250622918,
  author       = {Pith},
  title        = {Pith review of: An approximation theory for Markov chain compression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JE4LCYSX}},
  note         = {Machine review of arXiv:2506.22918}
}

read the original abstract

We develop a framework for the compression of reversible Markov chains with rigorous error control. Given a subset of selected states, we construct reduced dynamics that can be lifted to an approximation of the full dynamics, and we prove simple spectral and nuclear norm bounds on the recovery error in terms of a suitably interpreted Nystr\"{o}m approximation error. We introduce two compression schemes: a projective compression based on committor functions and a structure-preserving compression defined in terms of an induced Markov chain over the selected states. The Nystr\"{o}m error appearing in our bounds can be controlled using recent results on column subset selection by nuclear maximization. Numerical experiments validate our theory and demonstrate the scalability of our approach.

Figures

Figures reproduced from arXiv: 2506.22918 by the authors.

**Figure 2.** Depiction of sample trajectories from the original and marked chains [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

**Figure 3.** Decomposition of a trajectory into cycles for example states [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Performance of nuclear maximization as a function of [PITH_FULL_IMAGE:figures/full_fig_p031_4.png]

**Figure 5.** Figure 5: (Top) Spectral norm approximation error for projective (proj.) and structure [PITH_FULL_IMAGE:figures/full_fig_p032_5.png]

**Figure 6.** Figure 6: (Top) Comparison of the reduced dynamics using projective compression: [PITH_FULL_IMAGE:figures/full_fig_p033_6.png]

**Figure 7.** Figure 7: Resolvent error along ray for a randomly generated killed Laplacian [PITH_FULL_IMAGE:figures/full_fig_p067_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Nystr\"om Error Beyond $M$-Matrices: A Minimal Diagonally Dominant Obstruction
math.NA 2026-07 accept novelty 6.0 of 10

For symmetric diagonally dominant matrices, the Nyström nuclear-norm error can violate diminishing returns, with minimal counterexamples in dimension three (four for nonempty base sets).

Reference graph

Works this paper leans on

91 extracted references · 77 canonical work pages · cited by 1 Pith paper

[1]

Inequalities for rare events in time-reversible Markov chains I

B. D. Aldous and M. Brown. “Inequalities for rare events in time-reversible Markov chains I”. In: Lecture Notes-Monograph Series (1992)

1992
[2]

Aldous and J

D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs . Berkeley, 1995

1995
[3]

Spectral methods in machine learning and new strategies for very large datasets

M.-A. Belabbas and P. J. Wolfe. “Spectral methods in machine learning and new strategies for very large datasets”. en. In: Proc. Natl. Acad. Sci. U. S. A. 106 (2 Jan. 13, 2009), pp. 369–374

2009
[4]

Committors, first-passage times, fluxes, Markov states, milestones, and all that

A. Berezhkovskii and A. Szab´ o. “Committors, first-passage times, fluxes, Markov states, milestones, and all that”. In: J. Chem. Phys. 150 (5 Feb. 6, 2019), p. 054106

2019
[5]

An Improved Approximation Algorithm for the Column Subset Selection Problem

C. Boutsidis, M. W. Mahoney, and P. Drineas. “An Improved Approximation Algorithm for the Column Subset Selection Problem”. In: Proceedings of the 2009 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA) . Proceedings. Society for Industrial and Applied Mathematics, Jan. 4, 2009, pp. 968–977

2009
[6]

Approximating IMRL distributions by exponential distributions, with appli- cations to first passage times

M. Brown. “Approximating IMRL distributions by exponential distributions, with appli- cations to first passage times”. In: Annals of Probability 11 (2 May 1, 1983), pp. 419– 427

1983
[7]

Uncertainty in a Markov state model with missing states and rates: Application to a room temperature kinetic model obtained using high temperature molecular dynamics

A. Chatterjee and S. Bhattacharya. “Uncertainty in a Markov state model with missing states and rates: Application to a room temperature kinetic model obtained using high temperature molecular dynamics”. en. In: J. Chem. Phys. 143 (11 Sept. 21, 2015), p. 114109

2015
[8]

Nonlinear model reduction via discrete empirical interpolation

S. Chaturantabut and D. C. Sorensen. “Nonlinear model reduction via discrete empirical interpolation”. In: SIAM J. Sci. Comput. 32 (5 Jan. 1, 2010), pp. 2737–2764

2010

Show all 91 references

[9]

RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems

C. Chen, T. Liang, and G. Biros. “RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems”. In: SIAM Journal on Scientific Computing 43.6 (2021), pp. C411– C438. doi: 10.1137/20M1380624

2021 doi
[10]

Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations

Y. Chen et al. “Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations”. In: Communications on Pure and Applied Mathematics 78.5 (2025), pp. 995–1041. doi: https://doi.org/10.1002/cpa.22234. 34

2025 doi
[11]

Markov state models of biomolecular conformational dynamics

J. D. Chodera and F. No´ e. “Markov state models of biomolecular conformational dynamics”. en. In: Curr. Opin. Struct. Biol. 25 (Apr. 2014), pp. 135–144

2014
[12]

Discrete Green’s functions

F. Chung and S. -T. Yau. “Discrete Green’s functions”. en. In: J. Comb. Theory Ser. A. 91 (1-2 July 2000), pp. 191–214

2000
[13]

On selecting a maximum volume sub-matrix of a matrix and related problems

A. C ¸ivril and M. Magdon-Ismail. “On selecting a maximum volume sub-matrix of a matrix and related problems”. In: Theor. Comput. Sci. 410 (47 Nov. 6, 2009), pp. 4801–4811

2009
[14]

Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation

A. Cortinovis and D. Kressner. “Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation”. In: arXiv [math.NA] (Dec. 18, 2024)

2024
[15]

Determinantal point processes in randomized nu- merical linear algebra

M. Derezinski and M. W. Mahoney. “Determinantal point processes in randomized nu- merical linear algebra”. In: Notices of the American Mathematical Society 68 (1 2021), pp. 34–45. (Visited on 01/29/2024)

2021
[16]

Optimal state-space lumping in Markov chains

S. Derisavi, H. Hermanns, and W. H. Sanders. “Optimal state-space lumping in Markov chains”. en. In: Inf. Process. Lett. 87 (6 Sept. 2003), pp. 309–315

2003
[17]

Efficient volume sampling for row/column subset selection

A. Deshpande and L. Rademacher. “Efficient volume sampling for row/column subset selection”. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) (Las Vegas, NV, USA). IEEE, Oct. 2010...

2010
[18]

Adaptive sampling and fast low-rank matrix approxima- tion

A. Deshpande and S. Vempala. “Adaptive sampling and fast low-rank matrix approxima- tion”. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture notes in computer science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 292–303

2006
[19]

Estimating the eigenvalue error of Markov state models

N. Djurdjevac, M. Sarich, and C. Sch¨ utte. “Estimating the eigenvalue error of Markov state models”. en. In: Multiscale Model. Simul. 10 (1 Jan. 28, 2012), pp. 61–81. (Visited on 08/07/2025)

2012
[20]

P. G. Doyle and J. L. Snell. Random walks and electric networks . Vol. 22. American Mathematical Soc., 1984

1984
[21]

On the Nystr¨ om method for approximating a Gram matrix for improved kernel-based learning

P. Drineas and M. W. Mahoney. “On the Nystr¨ om method for approximating a Gram matrix for improved kernel-based learning”. In: J. Mach. Learn. Res. 6 (June 27, 2005), pp. 2153–2175

2005
[22]

Lattice QCD at the physical point: simulation and analysis details

S. D¨ urr et al. “Lattice QCD at the physical point: simulation and analysis details”. In: J. High Energy Phys. 2011 (8 Aug. 30, 2011), p. 148

2011
[23]

R. Durrett. Probability: Theory and Examples . en. Cambridge University Press, Apr. 18,
[24]

Modeling molecular kinetics with Milestoning

R. Elber et al. “Modeling molecular kinetics with Milestoning”. en. In: Wiley Interdiscip. Rev. Comput. Mol. Sci. 11 (4 July 2021)

2021
[25]

Computing time scales from reaction coordinates by mileston- ing

A. Faradjian and R. Elber. “Computing time scales from reaction coordinates by mileston- ing”. In: J. Chem. Phys. 120 (23 June 15, 2004), pp. 10880–10889

2004
[26]

RNA folding at elementary step resolution

C. Flamm et al. “RNA folding at elementary step resolution”. In: RNA 6 (3 2000), pp. 325– 338

2000
[27]

M. Fornace. nuclear-score-maximization. Comp. software. Version 1.0. 2024

2024
[28]

Fornace and M

M. Fornace and M. Lindsey. Column and row subset selection using nuclear scores: algo- rithms and theory for Nystr¨ om approximation, CUR decomposition, and graph Laplacian re- duction. 2024. arXiv: 2407.01698 [math.NA]. url: https://arxiv.org/abs/2407.01698

2024 arXiv
[29]

A Unified Dynamic Programming Frame- work for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed

M. E. Fornace, N. J. Porubsky, and N. A. Pierce. “A Unified Dynamic Programming Frame- work for the Analysis of Interacting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed”. In: ACS Synth. Biol. 9 (10 2020). PMID: 32910644, pp. 2665–2678

2020
[30]

NUPACK: Analysis and Design of Nucleic Acid Structures, Devices, and Systems

M. E. Fornace et al. “NUPACK: Analysis and Design of Nucleic Acid Structures, Devices, and Systems”. en. In: ChemRxiv (Nov. 11, 2022). (Visited on 04/22/2024). 35

2022
[31]

Computational methods for simulating and parameterizing nucleic acid secondary structure thermodynamics and kinetics

M. E. Fornace. “Computational methods for simulating and parameterizing nucleic acid secondary structure thermodynamics and kinetics”. 2022

2022
[32]

Frenkel and B

D. Frenkel and B. Smit. Understanding Molecular Simulation: From Algorithms to Appli- cations. en. Elsevier, July 13, 2023. 679 pp

2023
[33]

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

Y. Gao, R. Kyng, and D. A. Spielman. “Robust and Practical Solution of Laplacian Equations by Approximate Elimination”. In: (2023). arXiv: 2303.00709 [math.NA]. url: https://arxiv.org/abs/2303.00709

2023 arXiv
[34]

Strong rank revealing Cholesky factorization

M. Gu and L. Miranian. “Strong rank revealing Cholesky factorization”. In: Plan. Perspect. 76 (2004), p. 92

2004
[35]

Optimal Column-Based Low-Rank Matrix Reconstruc- tion

V. Guruswami and A. K. Sinop. “Optimal Column-Based Low-Rank Matrix Reconstruc- tion”. In: Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Proceedings. Society for Industrial and Applied Mathematics, Jan. 17, 2012, pp. 1207–1214

2012
[36]

N. J. Higham. Functions of Matrices: Theory and Computation . en. Society for In- dustrial and Applied Mathematics, Jan. 2008. isbn: 9780898716467. doi: 10.1137/1. 9780898717778. url: http://epubs.siam.org/doi/book/10.1137/1.9780898717778

2008 doi
[37]

Optimal dimensionality reduction of multistate kinetic and Markov-state models

G. Hummer and A. Szabo. “Optimal dimensionality reduction of multistate kinetic and Markov-state models”. en. In: J. Phys. Chem. B 119 (29 July 23, 2015), pp. 9029–9037

2015
[38]

Markov State Models: From an Art to a Science

B. E. Husic and V. S. Pande. “Markov State Models: From an Art to a Science”. en. In: J. Am. Chem. Soc. 140 (7 Feb. 21, 2018), pp. 2386–2396

2018
[39]

Jacobsen

M. Jacobsen. Point process theory and applications: Marked point and piecewise determin- istic processes. en. 2006th ed. Probability and Its Applications. Secaucus, NJ: Birkhauser Boston, Dec. 15, 2005. 328 pp

2005
[40]

Markov State Models of Molecular Simulations to Study Protein Folding and Dynamics

V. Junghare et al. “Markov State Models of Molecular Simulations to Study Protein Folding and Dynamics”. In: Protein Folding Dynamics and Stability: Experimental and Computational Methods. Ed. by P. Saudagar and T. Tripathi. Singapore: Springer Nature Singapore, 2023, pp. 147–164

2023
[41]

Rarity and Exponentiality

J. Keilson. “Rarity and Exponentiality”. In: Applied Mathematical Sciences . Applied mathematical sciences. New York, NY: Springer New York, 1979, pp. 130–163

1979
[42]

Correlation functions, mean first passage times, and the Kemeny constant

A. Kells et al. “Correlation functions, mean first passage times, and the Kemeny constant”. en. In: J. Chem. Phys. 152 (10 Mar. 14, 2020), p. 104108

2020
[43]

J. G. Kemeny and J. L. Snell. Markov Chains . Springer-Verlag, New York, 1976

1976
[44]

Approximate Gaussian elimination for Laplacians - fast, sparse, and simple

R. Kyng and S. Sachdeva. “Approximate Gaussian elimination for Laplacians - fast, sparse, and simple”. In: FOCS (May 8, 2016), pp. 573–582

2016
[45]

Leskovec and A

J. Leskovec and A. Krevl. SNAP datasets: Stanford large network dataset collection . 2014. (Visited on 06/24/2025)

2014
[46]

D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times . American Mathematical Society, 2009

2009
[47]

A mathematical theory of optimal milestoning (with a detour via exact milestoning)

L. Lin, J. Lu, and E. Vanden-Eijnden. “A mathematical theory of optimal milestoning (with a detour via exact milestoning)”. en. In: Commun. Pure Appl. Math. 71 (6 June 2018), pp. 1149–1177

2018
[48]

Integrated variational approach to conformational dynamics: a robust strategy for identifying eigenfunctions of dynamical operators

C. Lorpaiboon et al. “Integrated variational approach to conformational dynamics: a robust strategy for identifying eigenfunctions of dynamical operators”. en. In: J. Phys. Chem. B 124 (42 Oct. 22, 2020), pp. 9354–9364

2020
[49]

CUR matrix decompositions for improved data analysis

M. W. Mahoney and P. Drineas. “CUR matrix decompositions for improved data analysis”. en. In: Proc. Natl. Acad. Sci. U. S. A. 106 (3 Jan. 20, 2009), pp. 697–702

2009
[50]

Variational cross-validation of slow dynamical modes in molecular kinetics

R. T. McGibbon and V. S. Pande. “Variational cross-validation of slow dynamical modes in molecular kinetics”. en. In: J. Chem. Phys. 142 (12 Mar. 28, 2015), p. 124105. 36

2015
[51]

Hutch++: Optimal Stochastic Trace Estimation

R. A. Meyer et al. “Hutch++: Optimal Stochastic Trace Estimation”. en. In: Proc SIAM Symp Simplicity Algorithms 2021 (Jan. 2021), pp. 142–155

2021
[52]

Everything you wanted to know about Markov State Models but were afraid to ask

V. S. Pande, K. Beauchamp, and G. R. Bowman. “Everything you wanted to know about Markov State Models but were afraid to ask”. en. In: Methods 52 (1 Sept. 2010), pp. 99–105

2010
[53]

K. I. Park. Fundamentals of probability and stochastic processes with applications to communications. en. 1st ed. Cham, Switzerland: Springer International Publishing, Dec. 4,
[54]

Validation of Markov state models using Shannon’s entropy

S. Park and V. S. Pande. “Validation of Markov state models using Shannon’s entropy”. en. In: J. Chem. Phys. 124 (5 Feb. 7, 2006), p. 054118

2006
[55]

L. C. G. Rogers and D. Williams. Diffusions, Markov processes, and martingales: Volume 1, foundations . Vol. 1. Cambridge university press, 2000

2000
[56]

S. M. Ross. Stochastic processes. Wiley, 1983

1983
[57]

Multi-Scale attributed node embedding

B. Rozemberczki, C. Allen, and R. Sarkar. “Multi-Scale attributed node embedding”. en. In: J. Complex Netw. 9 (2 May 5, 2021), cnab014

2021
[58]

Armadillo: a template-based C++ library for linear algebra

C. Sanderson and R. Curtin. “Armadillo: a template-based C++ library for linear algebra”. In: Journal of Open Source Software 1 (2 2016), p. 26

2016
[59]

Practical Sparse Matrices in C++ with Hybrid Storage and Template-Based Expression Optimisation

C. Sanderson and R. Curtin. “Practical Sparse Matrices in C++ with Hybrid Storage and Template-Based Expression Optimisation”. en. In: Math. Comput. Appl. 24 (3 July 19, 2019), p. 70. (Visited on 06/14/2024)

2019
[60]

On the approximation quality of Markov state models

M. Sarich, F. No´ e, and C. Sch¨ utte. “On the approximation quality of Markov state models”. In: Multiscale Model. Simul. 8 (4 Jan. 2010), pp. 1154–1177

2010
[61]

Stochastic simulation of the kinetics of multiple interacting nucleic acid strands

J. M. Schaeffer, C. Thachuk, and E. Winfree. “Stochastic simulation of the kinetics of multiple interacting nucleic acid strands”. In: International Workshop on DNA-Based Computers. 2015, pp. 194–211

2015
[62]

Uber eine Klasse von Mittelbildungen mit Anwendungen auf die Determinanten- theorie

I. Schur. “Uber eine Klasse von Mittelbildungen mit Anwendungen auf die Determinanten- theorie”. In: Sitzungsberichte der Berliner Mathematischen Gesellschaft 22 (9-20 1923), p. 51

1923
[63]

Markov state models based on milestoning

C. Sch¨ utte et al. “Markov state models based on milestoning”. en. In: J. Chem. Phys. 134 (20 May 28, 2011), p. 204105

2011
[64]

Improvements in Markov State Model Construction Reveal Many Non-Native Interactions in the Folding of NTL9

C. R. Schwantes and V. S. Pande. “Improvements in Markov State Model Construction Reveal Many Non-Native Interactions in the Folding of NTL9”. en. In: J. Chem. Theory Comput. 9 (4 Apr. 9, 2013), pp. 2000–2009

2013
[65]

Column subset selection is NP-complete

Y. Shitov. “Column subset selection is NP-complete”. en. In: Linear Algebra Appl. 610 (Feb. 2021), pp. 52–58

2021
[66]

Markov state models provide insights into dynamic modulation of protein function

D. Shukla et al. “Markov state models provide insights into dynamic modulation of protein function”. en. In: Acc. Chem. Res. 48 (2 Feb. 17, 2015), pp. 414–422

2015
[67]

A family of face products of matrices and its properties

V. I. Slyusar. “A family of face products of matrices and its properties”. In: Cybernetics and systems analysis 35 (3 1999), pp. 379–384

1999
[68]

Randomly Pivoted Partial Cholesky: Random How?

S. Steinerberger. “Randomly Pivoted Partial Cholesky: Random How?” In:arXiv [math.NA] (Apr. 17, 2024)

2024
[69]

Stochastic simulation in systems biology

T. Sz´ ekely Jr and K. Burrage. “Stochastic simulation in systems biology”. en. In: Comput. Struct. Biotechnol. J. 12 (20-21 Nov. 2014), pp. 14–25

2014
[70]

Galerkin approximation of dynamical quantities using trajectory data

E. H. Thiede et al. “Galerkin approximation of dynamical quantities using trajectory data”. en. In: J. Chem. Phys. 150 (24 June 28, 2019), p. 244111

2019
[71]

Simple O(m log n) time Markov chain lumping

A. Valmari and G. Franceschinis. “Simple O(m log n) time Markov chain lumping”. In: Tools and Algorithms for the Construction and Analysis of Systems . Lecture notes in computer science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 38–52. 37

2010
[72]

On the assumptions underlying milestoning

E. Vanden-Eijnden et al. “On the assumptions underlying milestoning”. en. In: J. Chem. Phys. 129 (17 Nov. 7, 2008), p. 174102

2008
[73]

Error bounds for dynamical spectral estimation

R. J. Webber et al. “Error bounds for dynamical spectral estimation”. In: SIAM Journal on Mathematics of Data Science 3 (1 Jan. 1, 2021), pp. 225–252

2021
[74]

Using the Nystr¨ om method to speed up kernel machines

C. K. I. Williams and M. Seeger. “Using the Nystr¨ om method to speed up kernel machines”. In: Adv. Neural Inf. Process. Syst. (2000), pp. 682–688

2000
[75]

Hierarchical Nystr¨ om methods for constructing Markov state models for conformational dynamics

Y. Yao et al. “Hierarchical Nystr¨ om methods for constructing Markov state models for conformational dynamics”. In: The Journal of Chemical Physics 138.17 (May 2013), p. 174106. issn: 0021-9606. doi: 10.1063/1.4802007

2013 doi
[76]

Fast and accurate interpolative decompositions for general, sparse, and structured tensors

Y. Zhang, M. Fornace, and M. Lindsey. “Fast and accurate interpolative decompositions for general, sparse, and structured tensors”. In: arXiv [math.NA] (Mar. 24, 2025). A Proofs for Section 2 A.1 Proof of Theorem 1 In this section we prove Theorem 1. Theorem 1: Error bound for...

2025
[77]

Take the limit δ → 0+ of our contour integral, yielding an exact expression for P (t) − PI(t) as a contour integral over C(T, 0). ( A priori , to apply Cauchy’s integral formula we must avoid 38 touching the origin with our contour due to the essential singularity of e−1/z at ...
[78]

the first return to j after hitting any one of I

Take the limit T → ∞and argue that the contribution of the vertical crossbar segment C2 vanishes. By (104) for C = C(T, δ), we deduce by changing variables that P (t) − PI(t) = 1 2πi I C(T,0) e−1/(z+δ) [Qt(z + δ) − Rt(z + δ)] dz. Note that the integrand Iδ(z) := e−1/(z+δ) [Qt(...
[79]

More precisely, − ˆR−1 i,i = E(τ I \{i} | X0 = i)

The average time for M started at state i ∈ Ito reach any state in I \{i} is − ˆR−1 i,i . More precisely, − ˆR−1 i,i = E(τ I \{i} | X0 = i). (54)
[80]

More precisely, − ˆRi,j/ ˆRi,i = P(Xτ I \{i} = j | X0 = i)

Starting M in i and stopping it once it hits any state j ∈ I \{i}, the probability of stopping in state j is − ˆRi,j/ ˆRi,i. More precisely, − ˆRi,j/ ˆRi,i = P(Xτ I \{i} = j | X0 = i). (55)
[81]

More precisely, ˆπi = P(Xτ I = i)

The probability of reaching state i first of the states in I is ˆπi. More precisely, ˆπi = P(Xτ I = i). (56) Proof. For claim 1, we compute: P(τI \{i} > t| X0 = i) = Ii,: exp RI∪{i},I∪{i}t
[82]

(158) It simplifies the linear algebra to express this quantity as the limit: P(τI \{i} > t| X0 = i) = lim β→0 Ii,: exp (R − β1π⊤)I∪{i},I∪{i}t
[83]

Given this approach, the probability 50 of the chain not having reached I \{i} at time t is: P(τI \{i} > t| X0 = i) = lim β→0 lim α→∞ Ii,: exp (R − β1π⊤ − αI:,I \{i}I⊤ :,I \{i})t

(159) Then by Lemma D.1, we express the expected time via a limit α → ∞of a perturbed probability evolution where the chain is killed instantly on reaching I \{i}. Given this approach, the probability 50 of the chain not having reached I \{i} at time t is: P(τI \{i} > t| X0 = ...
[84]

(160) So, integrating to find the expected lifetime of such a process: E(τI \{i} | X0 = i) = lim β→0 lim α→∞ Z ∞ 0 Ii,: exp (R − β1π⊤ − αI:,I \{i}I⊤ :,I \{i})t 1 dt. (161) Then we compute the right-hand integral for finite β >0 and α >0 to find that: E(τI \{i} | X0 = i) = lim ...
[85]

The rates between marked states ( i, i) → (i′, i′) are inherited from the rates i → i′ in the original chain M

Upper-left block (marked state → marked state). The rates between marked states ( i, i) → (i′, i′) are inherited from the rates i → i′ in the original chain M. Other than transitions to other marked states, a marked state ( i, i) can only transition to an unmarked state ( i, j...
[86]

The rates between unmarked states (i, j) → (i′, j′) are inherited from the rates j → j′ in the original chain M when i = i′, otherwise they are zero

Lower-right block (unmarked state → unmarked state). The rates between unmarked states (i, j) → (i′, j′) are inherited from the rates j → j′ in the original chain M when i = i′, otherwise they are zero. Indeed, II,I ⊗ RI,I is the block-diagonal repetition of RI,I. 54
[87]

Upper-right block (marked state → unmarked state). The only unmarked states to which a marked state (i, i) can transition are those of the form ( i, j), j ∈ I, sharing the same marking, with rates inherited from the rates i → j in the original chain M. The face-splitting produ...
[88]

Any unmarked state ( i, j) is allowed to transition to any marked state ( k, k), with a rate inherited from the rate j → k in the original chain M

Lower-left block (unmarked state → marked state). Any unmarked state ( i, j) is allowed to transition to any marked state ( k, k), with a rate inherited from the rate j → k in the original chain M. Block repetition of the rates RI,I yields 1I ⊗ RI,I. Now we turn to the station...
[89]

diag (π)Rγ is symmetric, following directly from the same fact for diag(π)R, since Rγ = R − γI
[90]

The entrywise formula (diag(˚πγ)Rγ)(i,j),(i′,j′) is the same as (215), upon substitution of ˜Cγ for ˜C (based on the entrywise expression (184) for ˚πγ) and Rγ = R − γI for R (based on the fact that this reproduces the effect of subtracting γI from ˚R in the blockwise formula ...
[91]

killed Laplace equation

The “killed Laplace equation” is satisfied by the killed commitor on I, i.e., [ Rγ ˜Cγ]I,: = 0. We verify this last point below. Then it only remains to show [ Rγ ˜Cγ]I,: = 0. To see this, recall the formula (Definition 2) ˜Cγ = diag−1(h)(Kγ):,I · · ·, where “ · · ·” indicates...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Inequalities for rare events in time-reversible Markov chains I

B. D. Aldous and M. Brown. “Inequalities for rare events in time-reversible Markov chains I”. In: Lecture Notes-Monograph Series (1992)

1992

[2] [2]

Aldous and J

D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs . Berkeley, 1995

1995

[3] [3]

Spectral methods in machine learning and new strategies for very large datasets

M.-A. Belabbas and P. J. Wolfe. “Spectral methods in machine learning and new strategies for very large datasets”. en. In: Proc. Natl. Acad. Sci. U. S. A. 106 (2 Jan. 13, 2009), pp. 369–374

2009

[4] [4]

Committors, first-passage times, fluxes, Markov states, milestones, and all that

A. Berezhkovskii and A. Szab´ o. “Committors, first-passage times, fluxes, Markov states, milestones, and all that”. In: J. Chem. Phys. 150 (5 Feb. 6, 2019), p. 054106

2019

[5] [5]

An Improved Approximation Algorithm for the Column Subset Selection Problem

C. Boutsidis, M. W. Mahoney, and P. Drineas. “An Improved Approximation Algorithm for the Column Subset Selection Problem”. In: Proceedings of the 2009 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA) . Proceedings. Society for Industrial and Applied Mathematics, Jan. 4, 2009, pp. 968–977

2009

[6] [6]

Approximating IMRL distributions by exponential distributions, with appli- cations to first passage times

M. Brown. “Approximating IMRL distributions by exponential distributions, with appli- cations to first passage times”. In: Annals of Probability 11 (2 May 1, 1983), pp. 419– 427

1983

[7] [7]

Uncertainty in a Markov state model with missing states and rates: Application to a room temperature kinetic model obtained using high temperature molecular dynamics

A. Chatterjee and S. Bhattacharya. “Uncertainty in a Markov state model with missing states and rates: Application to a room temperature kinetic model obtained using high temperature molecular dynamics”. en. In: J. Chem. Phys. 143 (11 Sept. 21, 2015), p. 114109

2015

[8] [8]

Nonlinear model reduction via discrete empirical interpolation

S. Chaturantabut and D. C. Sorensen. “Nonlinear model reduction via discrete empirical interpolation”. In: SIAM J. Sci. Comput. 32 (5 Jan. 1, 2010), pp. 2737–2764

2010