Pith. sign in

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

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

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)
  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)
  1. [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.
  2. [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.
  3. [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.
  4. [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 1
Figure 1. Illustration of our limiting contour in the complex plane. Eigenvalues of [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
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
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. Figure 4: Performance of nuclear maximization as a function of [PITH_FULL_IMAGE:figures/full_fig_p031_4.png]
Figure 5
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. Figure 6: (Top) Comparison of the reduced dynamics using projective compression: [PITH_FULL_IMAGE:figures/full_fig_p033_6.png]
Figure 7
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

  1. 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. [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

Show all 91 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [20]

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

    1984

  13. [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

  14. [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

  15. [23]

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

  16. [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

  17. [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

  18. [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

  19. [27]

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

    2024

  20. [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

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [34]

    Strong rank revealing Cholesky factorization

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

    2004

  27. [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

  28. [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

  29. [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

  30. [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

  31. [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

  32. [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

  33. [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

  34. [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

  35. [43]

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

    1976

  36. [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

  37. [45]

    Leskovec and A

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

    2014

  38. [46]

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

    2009

  39. [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

  40. [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

  41. [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

  42. [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

  43. [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

  44. [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

  45. [53]

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

  46. [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

  47. [55]

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

    2000

  48. [56]

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

    1983

  49. [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

  50. [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

  51. [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

  52. [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

  53. [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

  54. [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

  55. [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

  56. [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

  57. [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

  58. [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

  59. [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

  60. [68]

    Randomly Pivoted Partial Cholesky: Random How?

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

    2024

  61. [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

  62. [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

  63. [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

  64. [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

  65. [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

  66. [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

  67. [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

  68. [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

  69. [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 ...

  70. [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(...

  71. [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)

  72. [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)

  73. [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

  74. [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

  75. [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 = ...

  76. [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 ...

  77. [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...

  78. [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

  79. [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...

  80. [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...

  81. [89]

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

  82. [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 ...

  83. [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.