pith. sign in

arxiv: 2009.08443 · v3 · submitted 2020-09-17 · 🧮 math.RA · cs.CV· cs.LG

Tropical time series, iterated-sums signatures and quasisymmetric functions

Pith reviewed 2026-05-24 14:22 UTC · model grok-4.3

classification 🧮 math.RA cs.CVcs.LG
keywords time seriesiterated-sums signaturetropical semiringquasisymmetric functionsfeature extractionsemiringschronological features
0
0 comments X

The pith

The iterated-sums signature over the tropical semiring extracts chronological features from real-valued time series unavailable from existing signature objects and computes them in linear time.

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

The paper defines an iterated-sums signature that works over any commutative semiring and singles out the tropical case for time series. This version produces features that track order and accumulation in ways standard signatures miss. Computation stays linear in the length of the series. The authors position quasisymmetric expressions over semirings as the natural algebraic setting for the construction. A reader would care because the method gives a concrete, efficient route to new sequential invariants without leaving the semiring setting.

Core claim

The iterated-sums signature is introduced over arbitrary commutative semirings; when the semiring is tropical, the resulting map on real-valued time series yields chronological features not easily obtained from prior signature-type objects, the map can be evaluated in linear time, and quasisymmetric expressions over semirings supply the correct algebraic framework for the semiring-valued case.

What carries the argument

The iterated-sums signature over the tropical semiring, which accumulates ordered sums under tropical addition and multiplication to produce sequence features.

If this is right

  • Real-valued time series acquire new extractable features tied to chronological order.
  • These features remain computable in time linear in the length of the input series.
  • The same signature construction extends directly to time series taking values in any commutative semiring.
  • Quasisymmetric expressions become the algebraic language for describing such signatures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear-time property may allow the signature to serve as a drop-in feature map inside streaming or online algorithms.
  • Other semirings could be substituted to target different notions of accumulation, such as probabilistic or fuzzy orderings.
  • The connection to quasisymmetric functions suggests possible links to combinatorial enumeration problems that already use those functions.

Load-bearing premise

Quasisymmetric expressions over semirings form the appropriate framework for iterated-sums signatures on semiring-valued time series.

What would settle it

A concrete time series of length n for which the tropical iterated-sums signature either misses a clear chronological ordering present in the data or requires superlinear operations to compute.

Figures

Figures reproduced from arXiv: 2009.08443 by Joscha Diehl, Kurusch Ebrahimi-Fard, Nikolas Tapia.

Figure 1
Figure 1. Figure 1: Epoch test accuracy for the architecture FCN (left) and ISS (right) for different values of σ. (N = 100, training size: 1000, test size: 100, 100 epochs). where K : R k → R, pool: R( N k ) → R. Now, in this generality, such features are computationally intractable, even for modest values of N and k, since K has to be evaluated N k  times. The iterated￾sums signature presented in this work represents a spe… view at source ↗
Figure 2
Figure 2. Figure 2: Example of data points (in magenta) attaining the minima in eq. (4). calculate ISSRmin+ over large intervals, it suffices to calculate it over small intervals: Example 1.3. For 0 ≤ s < t < u, D ISSRmin+ s,u (z), 74E = M min+ s<j1<j2≤u z min+[1 7 ] j1 min+ z min+[1 4 ] j2 = min s<j1<j2≤u {7zj1 + 4zj2 } = min n min s<j1<j2≤t {7zj1 + 4zj2 }, min t<j1<j2≤u {7zj1 + 4zj2 }, min s<i≤t {7zi} + min t<j≤u {4zj} o = … view at source ↗
Figure 3
Figure 3. Figure 3: Example of the coarsest dyadic partition of (3, 15] Example 5.2. Consider the time horizon T = 16 = 24 and s = 3, t = 15. There is a (unique) coarsest partition of the interval (3, 15] using only dyadic intervals (j · 2 n ,(j + 1) · 2 n ], namely (3, 15] = (3, 4]∪˙ (4, 8]∪˙ (8, 12]∪˙ (12, 14]∪˙ (14, 15], see also [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗
read the original abstract

Aiming for a systematic feature-extraction from time series, we introduce the iterated-sums signature over arbitrary commutative semirings. The case of the tropical semiring is a central, and our motivating example. It leads to features of (real-valued) time series that are not easily available using existing signature-type objects. We demonstrate how the signature extracts chronological aspects of a time series, and that its calculation is possible in linear time. We identify quasisymmetric expressions over semirings as the appropriate framework for iterated-sums signatures over semiring-valued time series.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces the iterated-sums signature over arbitrary commutative semirings, taking the tropical semiring as its central motivating case. It asserts that the resulting features capture chronological aspects of real-valued time series unavailable from prior signature constructions, that the signature is computable in linear time, and that quasisymmetric expressions over semirings supply the correct algebraic framework for the semiring-valued setting.

Significance. If the definitional framework and the linear-time claim are made fully explicit with supporting algorithms and comparisons, the work would supply a new semiring-compatible extension of signature methods with potential utility in algebraic combinatorics and time-series feature extraction. The explicit link to quasisymmetric functions could unify existing approaches, provided concrete examples demonstrate features not recoverable from classical signatures.

major comments (2)
  1. [Abstract and §1] Abstract and §1: the linear-time computability claim is central to the practical contribution yet no explicit algorithm, recurrence, or complexity argument is supplied in the visible sections; without this the assertion remains unverified.
  2. [§3 or §4] §3 or §4 (whichever contains the comparison): the claim that tropical iterated-sums features are 'not easily available using existing signature-type objects' requires at least one concrete, side-by-side numerical example on a short real time series showing a chronological invariant absent from the classical signature; the current framing is purely definitional.
minor comments (2)
  1. Notation for the semiring operations and the iterated-sums product should be introduced once and used uniformly; several passages mix tropical and classical notation without explicit transition.
  2. [Abstract] The final sentence of the abstract identifies quasisymmetric expressions as 'the appropriate framework'; this identification should be justified by a short theorem or proposition rather than left as a concluding remark.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and constructive suggestions. We address each major comment below and will incorporate revisions accordingly.

read point-by-point responses
  1. Referee: [Abstract and §1] Abstract and §1: the linear-time computability claim is central to the practical contribution yet no explicit algorithm, recurrence, or complexity argument is supplied in the visible sections; without this the assertion remains unverified.

    Authors: We agree that providing an explicit algorithm and complexity argument will strengthen the manuscript. Although the linear-time claim is stated, the details of the recurrence are not fully expanded in the current version. In the revision, we will add an explicit description of the algorithm, including the recurrence relation and a proof of O(n) complexity for a time series of length n. revision: yes

  2. Referee: [§3 or §4] §3 or §4 (whichever contains the comparison): the claim that tropical iterated-sums features are 'not easily available using existing signature-type objects' requires at least one concrete, side-by-side numerical example on a short real time series showing a chronological invariant absent from the classical signature; the current framing is purely definitional.

    Authors: The manuscript aims to demonstrate the extraction of chronological aspects, but we recognize that a concrete numerical example would make the distinction clearer. We will include a short real-valued time series example with side-by-side computation of the tropical iterated-sums signature and the classical signature to show a specific chronological feature that is captured only by the former. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces iterated-sums signatures as a new algebraic object over commutative semirings, with the tropical case as a motivating example. All central claims (feature extraction properties, linear-time computation, and identification of quasisymmetric expressions as the framework) are presented as definitional contributions rather than reductions of fitted parameters or prior results. No equations, self-citations, or ansatzes appear in the abstract that would reduce the claimed outputs to the inputs by construction. The work is self-contained as an algebraic definition and does not rely on load-bearing self-citations or uniqueness theorems imported from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the domain assumption that semirings are a natural setting for signatures and that quasisymmetric functions extend appropriately; no free parameters or new physical entities are introduced.

axioms (2)
  • domain assumption Commutative semirings form a suitable algebraic base for defining iterated-sums signatures of time series.
    Invoked to extend the classical signature construction beyond the reals.
  • domain assumption Quasisymmetric expressions over semirings supply the correct bookkeeping for these signatures.
    Stated in the final sentence of the abstract as the appropriate framework.

pith-pipeline@v0.9.0 · 5629 in / 1266 out tokens · 22702 ms · 2026-05-24T14:22:09.682112+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

71 extracted references · 71 canonical work pages · 2 internal anchors

  1. [1]

    Akian, R

    M. Akian, R. Bapat, and S. Gaubert,Max-plus algebra, Handbook of linear algebra 39 (2006)

  2. [2]

    Akian, S

    M. Akian, S. Gaubert, and A. Guterman,Linear independence over tropical semir- ings and beyond, Tropical and idempotent mathematics, Contemp. Math., vol. 495, Amer. Math. Soc., Providence, RI, 2009, pp. 1–38

  3. [3]

    J. F. Allen,Maintaining knowledge about temporal intervals, Communications of the ACM 26 (1983), no. 11, 832–843

  4. [4]

    Amendola, P

    C. Amendola, P. Friz, and B. Sturmfels,Varieties of signature tensors, Forum of Mathematics, Sigma, vol. 7, Cambridge University Press, 2019. 38

  5. [5]

    Anderson and M

    D. Anderson and M. Roitman,A characterization of cancellation ideals, Proceedings of the American Mathematical Society125 (1997), no. 10, 2853–2854

  6. [6]

    Antoine, F

    R. Antoine, F. Perera, and H. Thiel,Tensor products and regularity properties of Cuntz semigroups, Mem. Amer. Math. Soc.251 (2018), no. 1199, viii+191

  7. [7]

    F. L. Baccelli, G. J. Olsder, J.-P. Quadrat, and G. Cohen,Synchronization and linearity. an algebra for discrete event systems, Chichester: Wiley, 1992

  8. [8]

    S. Bai, J. Z. Kolter, and V. Koltun,An empirical evaluation of generic convolutional and recurrent networks for sequence modeling, arXiv preprint arXiv:1803.01271 (2018)

  9. [9]

    Baldwin and P

    E. Baldwin and P. Klemperer,Tropical geometry to analyse demand, Unpublished paper.[281] (2013)

  10. [10]

    S. L. Bloom and Z. Ésik, Iteration theories, Iteration Theories, Springer, 1993, pp. 159–213

  11. [11]

    Tensor categorical foundations of algebraic geometry

    M. Brandenburg, Tensor categorical foundations of algebraic geometry , 2014, arXiv:1410.1716

  12. [12]

    Brandenburg,Einführung in die Kategorientheorie: Mit ausführlichen Erklärun- gen und zahlreichen Beispielen, Springer-Verlag, 2016

    M. Brandenburg,Einführung in die Kategorientheorie: Mit ausführlichen Erklärun- gen und zahlreichen Beispielen, Springer-Verlag, 2016

  13. [13]

    P.Butkovič, Max-linear systems: theory and algorithms, SpringerScience&Business Media, 2010

  14. [14]

    Carlsson and S

    G. Carlsson and S. Kališnik Verovšek,Symmetric andr-symmetric tropical polyno- mials and rational functions, J. Pure Appl. Algebra220 (2016), no. 11, 3610–3627

  15. [15]

    C. G. Cassandras and S. Lafortune,Introduction to discrete event systems, second ed., Springer, New York, 2008

  16. [16]

    Chen, Integration of paths, geometric invariants and a generalized Baker- Hausdorff formula, Ann

    K.-T. Chen, Integration of paths, geometric invariants and a generalized Baker- Hausdorff formula, Ann. of Math. (2)65 (1957), 163–178

  17. [17]

    Cohen, S

    G. Cohen, S. Gaubert, and J. P. Quadrat,Algebraic system analysis of timed petri nets, Idempotency (J. Gunawardena, ed.), Collection of the Isaac Newton Institute, Cambridge University Press, 1998

  18. [18]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,Parameterized algorithms, Springer, 2015

  19. [19]

    Diehl, K

    J. Diehl, K. Ebrahimi-Fard, and N. Tapia,Iterated-sums signature, quasisymmetric functions and time series analysis, Sém. Lothar. Combin.84B.86 (2020), 12 pp

  20. [20]

    , Time-warping invariants of multidimensional time series, Acta Appl. Math. 170 (2020), 265–290. 39

  21. [21]

    Droste and W

    M. Droste and W. Kuich,Chapter 1: Semirings and formal power series, Handbook ofweightedautomata, Monogr.Theoret.Comput.Sci.EATCSSer., Springer, Berlin, 2009, pp. 3–28

  22. [22]

    L. A. Duffaut Espinosa, W. S. Gray, and K. Ebrahimi-Fard,A combinatorial Hopf algebra for nonlinear output feedback control systems, J. Algebra453 (2016), 609– 643

  23. [23]

    ,Discrete-time approximations of Fliess operators, Numer.Math.137(2017), 35–62

  24. [24]

    Ebrahimi-Fard, F

    K. Ebrahimi-Fard, F. Fauvet, and D. Manchon,A comodule-bialgebra structure for word-series substitution and mould composition, J. Algebra489 (2017), 552–581

  25. [25]

    Ebrahimi-Fard, S

    K. Ebrahimi-Fard, S. J. Malham, F. Patras, and A. Wiese,Flows and stochastic Taylor series in Itô calculus, Journal of Physics A: Mathematical and Theoretical 48 (2015), no. 49, 495202

  26. [26]

    J. Eisner, Parameter estimation for probabilistic finite-state transducers, Proceed- ings of the 40th Annual Meeting of the Association for Computational Linguistics (Philadelphia, Pennsylvania, USA), Association for Computational Linguistics, July 2002, pp. 1–8

  27. [27]

    H. I. Fawaz, G. Forestier, J. Weber, L. Idoumghar, and P.-A. Muller,Deep learning for time series classification: a review, Data Min. Knowl. Discov.33 (2019), no. 4, 917–963

  28. [28]

    J. G. Fletcher,A more general algorithm for computing closed semiring costs between vertices of a directed graph, Communications of the ACM23 (1980), no. 6, 350–351

  29. [29]

    Fliess,Fonctionnelles causales non linéaires et indéterminées non commutatives, Bulletin de la société mathématique de France109 (1981), 3–40

    M. Fliess,Fonctionnelles causales non linéaires et indéterminées non commutatives, Bulletin de la société mathématique de France109 (1981), 3–40

  30. [30]

    Flint, B

    G. Flint, B. Hambly, and T. J. Lyons,Discretely sampled signals and the rough Hoff process, Stochastic Process. Appl.126 (2016), no. 9, 2593–2614

  31. [31]

    P. K. Friz and N. B. Victoir,Multidimensional stochastic processes as rough paths, Cambridge Studies in Advanced Mathematics, no. 120, Cambridge University Press, 2010

  32. [32]

    J. G. Gaines, The algebra of iterated stochastic integrals, Stochastics Stochastics Rep. 49 (1994), no. 3-4, 169–179

  33. [33]

    I. M. Gessel,MultipartiteP-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289–317

  34. [34]

    Gilmer,Multiplicative ideal theory, Queen’s Papers in Pure and Appl

    R. Gilmer,Multiplicative ideal theory, Queen’s Papers in Pure and Appl. Math.90 (1992). 40

  35. [35]

    Gimpel and N

    K. Gimpel and N. A. Smith,Cube summing, approximate inference with non-local features, and dynamic programming without semirings, Proceedings of the 12th Con- ference of the European Chapter of the Association for Computational Linguistics (USA), EACL ’09, Association for Computational Linguistics, 2009, pp. 318–326

  36. [36]

    J. S. Golan,Semirings and affine equations over them: theory and applications, vol. 556, Springer Science & Business Media, 2013

  37. [37]

    Gondran and M

    M. Gondran and M. Minoux,Graphs, dioids and semirings: new models and algo- rithms, vol. 41, Springer Science & Business Media, 2008

  38. [38]

    Goodman,Semiring parsing, Comput

    J. Goodman,Semiring parsing, Comput. Linguist.25 (1999), no. 4, 573–605

  39. [39]

    W. S. Gray, G. Venkatesh, and L. A. D. Espinosa,Nonlinear system identification for multivariable control via discrete-time Chen–Fliess series, Automatica119 (2020), 109085

  40. [40]

    Hambly and T

    B. Hambly and T. J. Lyons, Uniqueness for the signature of a path of bounded variation and the reduced path group, Ann. Math.171 (2010), no. 1, 109–167

  41. [41]

    Heidergott, G

    B. Heidergott, G. J. Olsder, and J. Van Der Woude,Max plus at work: modeling and analysis of synchronized systems: a course on max-plus algebra and its applications, vol. 48, Princeton University Press, 2014

  42. [42]

    Kališnik and D

    S. Kališnik and D. Lešnik,Symmetric polynomials in upper-bound semirings, Journal of Symbolic Computation (2020)

  43. [43]

    Kališnik and D

    S. Kališnik and D. Lešnik,Symmetric polynomials in tropical algebra semirings, J. Symbolic Comput.93 (2019), 100–119

  44. [44]

    Kidger, P

    P. Kidger, P. Bonnier, I. Perez Arribas, C. Salvi, and T. Lyons,Deep signature transforms, Advances in Neural Information Processing Systems 32 (H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, eds.), Curran Associates, Inc., 2019, pp. 3105–3115

  45. [45]

    F. J. Király and H. Oberhauser, Kernels for sequentially ordered data, J. Mach. Learn. Res.20 (2019), Paper No. 31, 45

  46. [46]

    Kohlas and N

    J. Kohlas and N. Wilson,Semiring induced valuation algebras: exact and approxi- mate local computation algorithms, Artificial Intelligence172 (2008), no. 11, 1360– 1399

  47. [47]

    Komenda, S

    J. Komenda, S. Lahaye, J.-L. Boimond, and T. van den Boom,Max-plus algebra in the history of discrete event systemsr, Annual Reviews in Control 45 (2018), 240–249

  48. [48]

    Krizhevsky, I

    A. Krizhevsky, I. Sutskever, and G. E. Hinton,Imagenet classification with deep convolutional neural networks, Advances in neural information processing systems, 2012, pp. 1097–1105. 41

  49. [49]

    Kuich and A

    W. Kuich and A. Salomaa,Semirings, automata, languages, EATCS Monographs on Theoretical Computer Science, vol. 5, Springer-Verlag, Berlin, 1986

  50. [50]

    S. Liao, T. Lyons, W. Yang, and H. Ni,Learning stochastic differential equations using rnn with log signature features, 2019, arXiv:1908.08286

  51. [51]

    Luoto, S

    K. Luoto, S. Mykytiuk, and S. Van Willigenburg,An introduction to quasisymmetric schur functions: Hopf algebras, quasisymmetric functions, and Young composition tableaux, Springer Science & Business Media, 2013

  52. [52]

    T. J. Lyons,Differential equations driven by rough signals., Rev. Mat. Iberoam.14 (1998), no. 2, 215–310

  53. [53]

    Maclagan and B

    D. Maclagan and B. Strumfels,Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015

  54. [54]

    MacLane,Categories for the working mathematician, Springer-Verlag, New York- Berlin, 1971, Graduate Texts in Mathematics, Vol

    S. MacLane,Categories for the working mathematician, Springer-Verlag, New York- Berlin, 1971, Graduate Texts in Mathematics, Vol. 5

  55. [55]

    Malvenuto and C

    C. Malvenuto and C. Reutenauer,Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra177 (1995), no. 3, 967–982

  56. [56]

    Marty,Des immersions ouvertes et des morphismes lisses en géométrie relative, Ph.D

    F. Marty,Des immersions ouvertes et des morphismes lisses en géométrie relative, Ph.D. thesis, Université Toulouse III - Laboratoire Emile Picard, 2009

  57. [57]

    Mohri, Semiring frameworks and algorithms for shortest-distance problems, J

    M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb.7 (2002), no. 3, 321–350

  58. [58]

    Myneni,The pricing of the american option, The Annals of Applied Probability (1992), 1–23

    R. Myneni,The pricing of the american option, The Annals of Applied Probability (1992), 1–23

  59. [59]

    Norton and S

    J. Norton and S. Spiroff,The tropical semiring in higher dimensions, Involve 11 (2018), no. 3, 477–488

  60. [60]

    Pachter and B

    L. Pachter and B. Sturmfels,Tropical geometry of statistical models, Proceedings of the National Academy of Sciences101 (2004), no. 46, 16132–16137

  61. [61]

    13, Cambridge university press, 2005

    , Algebraic statistics for computational biology, vol. 13, Cambridge university press, 2005

  62. [62]

    Pnueli,The temporal logic of programs, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), IEEE, 1977, pp

    A. Pnueli,The temporal logic of programs, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), IEEE, 1977, pp. 46–57

  63. [63]

    Ree,Lie elements and an algebra associated with shuffles, Ann

    R. Ree,Lie elements and an algebra associated with shuffles, Ann. of Math. (2)68 (1958), 210–220

  64. [64]

    Reutenauer, Free Lie algebras, Handbook of algebra, Vol

    C. Reutenauer, Free Lie algebras, Handbook of algebra, Vol. 3, Handb. Algebr., vol. 3, Elsevier/North-Holland, Amsterdam, 2003, pp. 887–903. 42

  65. [65]

    Riehl,Category theory in context., Mineola, NY: Dover Publications, 2016

    E. Riehl,Category theory in context., Mineola, NY: Dover Publications, 2016

  66. [66]

    Saers and D

    M. Saers and D. Wu,Handling ties correctly and efficiently in Viterbi training us- ing the Viterbi semiring, Language and automata theory and applications, Lecture Notes in Comput. Sci., vol. 10792, Springer, Cham, 2018, pp. 284–295

  67. [67]

    Sakarovitch,Elements of automata theory, Cambridge University Press, 2009

    J. Sakarovitch,Elements of automata theory, Cambridge University Press, 2009

  68. [68]

    Schultz, D

    P. Schultz, D. I. Spivak, and C. Vasilakopoulou,Dynamical systems and sheaves, Applied Categorical Structures28 (2020), no. 1, 1–57

  69. [69]

    D. I. Spivak,Poly: An abundant categorical setting for mode-dependent dynamics, arXiv preprint arXiv:2005.01894 (2020)

  70. [70]

    C. Toth, P. Bonnier, and H. Oberhauser,Seq2tens: An efficient representation of sequences by low-rank tensor projections, arXiv preprint arXiv:2006.07027 (2020)

  71. [71]

    Worthington, A bialgebraic approach to automata and formal language theory, Logical foundations of computer science, Lecture Notes in Comput

    J. Worthington, A bialgebraic approach to automata and formal language theory, Logical foundations of computer science, Lecture Notes in Comput. Sci., vol. 5407, Springer, Berlin, 2009, pp. 451–467. 43