REVIEW 3 major objections 4 minor 1 cited by
An Efficient Algorithm for Path Recovery from Signature Tensors
T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read This paper proves that every third-order signature tensor in the congruence orbit of the axis-path core tensor can be inverted exactly by a sequence of Gauss transformations, with expected O(d^4) arithmetic operations.
desk verdict Genuine algorithmic advance for signature inversion, but the printed Algorithm 4 has a self-comparison typo that breaks the main algorithm on the paper's own example. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the matrix-tensor congruence action A*C with entries (A*C)_{ijk} = Σ C_{αβγ} A_{iα} A_{jβ} A_{kγ}, and the fixed upper-triangular core tensor C_{ijk} equal to 1, 3, or 6 according to whether i=j=k, i=j<k or i<j=k, or i<j<k. The mechanism that carries the argument is the Gauss-transform ladder: upper transforms U(s,x) (transposes of lower ones) are used to impose symmetry conditions on the tensor, lower transforms L(s,y) and diagonal scalings D(s,h) then eliminate the newly symmetric entries, reducing the problem to a smaller congruence orbit. The load-bearing identity is Lemma 5.5, which expresses the effect of an upper transform on the difference H_{ijs} - H_{jis} as a
What would settle it
Exhibit a tensor G = A*C for which the matrix M from Algorithm 2 becomes rank-deficient for every random coordinate change W, forcing the recursion to loop without terminating; or exhibit a non-identity A with A*C = C, contradicting the trivial-stabilizer theorem.
Extended reading notes
Core claim
The central claim is Theorem 1.1: for every d×d×d tensor G in the orbit GL_d * C of the core tensor C (the third-level signature of the canonical axis path), Algorithm 1 computes an invertible matrix A with G = A*C, using O(d^4) elementary operations in expectation. The proof works by iterating s = 1,...,d-1: at each step an upper Gauss transform (computed from a linear system Mx = B built from entries of G) puts the tensor into a normal form satisfying the four conditions of Theorem 3.2; lower and diagonal transforms then move the tensor into the smaller orbit (I_s ⊕ GL_{d-s}) * C. The recursion terminates at the core tensor, and uniqueness of the solution (the trivial stabilizer of C) turn
Load-bearing premise
The algorithm's correctness depends on a random coordinate change landing on a generic tensor where the linear system Mx = B has full rank; if degenerate tensors occurred with positive probability — or if the core tensor had a nontrivial stabilizer — the recursive reduction could either loop forever or recover the wrong matrix.
Editorial extensions
If this is right
- The third-order signature inversion problem in dimension d is solvable exactly in expected O(d^4) operations, replacing the previous Gröbner-basis approach whose cost grows far faster.
- Every tensor in the congruence orbit of the core tensor C can be normalized to C by congruence Gauss transformations, giving a constructive normal form for this third-order tensor congruence action.
- The recovery is exact and unique: the returned matrix A satisfies G = A*C, and no other matrix does, because the stabilizer of C is trivial.
- The algorithm's randomization ensures a 100% success rate in expectation: degenerate cases are escaped by random coordinate changes rather than by solving hard polynomial systems.
- The method extends the trivial-stabilizer theorem to partial orbits: if a tensor agrees with C on a certain index pattern, it already lies in (I_s ⊕ GL_{d-s})*C, enabling the recursive step.
Reading between the lines
- If the O(d^4) bound holds in practice, signature inversion becomes feasible in dimensions of order tens to hundreds, opening the door to using third-level signatures as a practical data representation in machine learning pipelines, where current methods stop near d=10.
- The same Gauss-normal-form strategy might apply to higher-order signature tensors or to other congruence orbits of tensors with a trivial stabilizer, though the low-dimensional exceptional cases (d=2,3) suggest that each order may need its own special handling.
- Because the reduction is rational (the core tensor is rational and the transformations are rational), the algorithm constructs the path matrix over the rationals; this means it could be used to certify exact recovery in symbolic computation, not just floating point.
- The linear-system formulation suggests that the computational bottleneck is a structured (d-s)^2 × (d-s) linear solve at each step, so highly optimized solvers could push the practical dimension higher than the reported table.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents an algorithm for the exact recovery of an invertible matrix A from a third-order signature tensor G = A*C, where C is the fixed signature tensor of the axis path in dimension d. The method uses upper, lower, and diagonal Gauss transformations under the congruence action to bring G into the orbit of the core tensor C, then recovers A via the known trivial-stabilizer result. The main theorem (Theorem 1.1) claims that Algorithm 1 always returns A and runs in expected O(d^4) operations. The paper includes an OSCAR implementation, benchmarks against Gröbner-basis methods, and formal verification of several rational-function identities in low-dimensional cases.
Significance. If correct, this is a substantial contribution: it replaces the previous Gröbner-basis approach to third-order signature inversion with a polynomial-time expected algorithm in arbitrary dimension, and it comes with a reproducible implementation and machine-checked algebraic verifications. The core mathematical strategy — iterative reduction via generalized normal forms — is natural and, aside from the issues below, the proof structure is coherent. Credit is due for the explicit use of an independent uniqueness theorem (PSS19), the closed-form core tensor (AFS19), and for shipping code and timing comparisons. The main reservation is that the printed Algorithm 4 contains a concrete indexing error that makes the central algorithm fail on generic inputs as written, so the manuscript requires correction before the claims are executable.
major comments (3)
- [Section 4, Algorithm 4 (up3)] The third upper transformation is not executable as printed. The guard 'if G_{d-2,d-1,d-1} ≠ G_{d-2,d-1,d-1}' is tautologically false, and the denominator in the same line is zero. Example 4.3 explicitly needs Q3, and Algorithm 1 invokes up3 at s=d-2 for every d≥3. The correct condition and denominator are G_{d-2,d-1,d-1} ≠ G_{d-1,d-2,d-1} and G_{d-2,d-1,d-1} - G_{d-1,d-2,d-1}, as used in the example's Q3. This is a load-bearing bug: as printed, Algorithm 1 does not terminate correctly on inputs requiring the third transformation. The mathematical construction appears sound, but the algorithm must be corrected.
- [Definition 5.6] The index ranges in Definition 5.6 are inconsistent with the claimed matrix size. The text says 'for 1≤a,b < s and 1< γ≤d−s−1', but M is a (d−s)^2 × (d−s) matrix and the accompanying Example 3.5 uses a,b running up to d−s. As written, M and B are undefined for most indices, so Algorithm 2 cannot be executed from this definition. The intended range is presumably 1≤a,b≤d−s and 1≤γ≤d−s, with the symmetry reduction explained in Remark 5.7. This needs correction in the revision.
- [Theorem 3.2, proof case (2c)] The proof claims 'H_ijs = 0 with i>s≥j' for j=s, but in H∈(I_{s-1}⊕GL_{d-s+1})*C, the entry H_{i,s,s} is not generally zero (it can equal A_{i,s}(A_{s,s})^2). The desired vanishing J_{i,s,s}=0 follows from condition (ii) after applying the lower transformation: J_{i,s,s}=H_{i,s,s}-H_{s,i,s}=0. The written justification is therefore incorrect as stated, though the theorem is recoverable. The proof should be rewritten to avoid this false assertion.
minor comments (4)
- [Section 3, Algorithm 2 / Proposition 5.9] The randomized retry step is not fully formalized. Over the reals, Okada's lemma gives measure-zero bad sets, but the algorithm is described over exact rational arithmetic, and the phrase 'random W' does not specify a distribution. A short remark on how randomness is implemented in exact arithmetic and why the success probability is 1 would remove ambiguity.
- [Corollary 5.11] The sentence 'This follows, for example, with the adjugate matrix of B and [Oka73, Lemma 1]' is very terse. Expanding this one or two lines would help the reader verify the generic solvability claim.
- [Theorem 2.3] The index conditions in part (i), 'i=j=k≤s or k≤min(s,i−1,j) or j≤min(s,i−1,k)', are hard to parse. A short explanation or a diagram indicating the corresponding tensor positions would improve readability.
- [Section 5, opening line] There is a typo: 'we provide all omitted proves' should read 'we provide all omitted proofs'. Also, the full-text title reads 'An Efficient Algorithm for Tensor Learning' while the arXiv title is 'An Efficient Algorithm for Path Recovery from Signature Tensors'; the consistency should be checked.
Circularity Check
No significant circularity: the central derivation is self-contained and its main external inputs are prior work by non-overlapping authors. The most notable defect is a non-circular correctness typo in Algorithm 4.
full rationale
The recovery chain is: fix the axis-path core tensor C from [AFS19]; use the congruence action G = A * C; invoke the trivial-stabilizer/uniqueness result [PSS19, Theorem 6.2 and Corollary 6.3] to know A is unique; then construct A by explicit Gauß transformations whose upper steps are computed by solving linear systems and whose lower/diagonal steps are read directly from the tensor. None of these steps defines the sought A in terms of G, and no fitted parameter is renamed as a prediction. The generic-rank arguments in Proposition 5.9 and Corollary 5.11 rest on non-vanishing of polynomial minors, which is independent evidence rather than a circular input. The low-dimensional Algorithms 3 and 4 are supported by OSCAR verification on rational function fields, not by assuming the answer. The only self-citation to the present author, [AS25], is used for a normalized core-tensor convention and for a matrix identity in Lemma 5.8; it is not load-bearing for Theorem 1.1. The main external load-bearing citations, [PSS19] and [AFS19], have no author overlap with this paper. One manuscript passage worth flagging is Algorithm 4's third transformation: 'if G_{d−2,d−1,d−1} ≠ G_{d−2,d−1,d−1} then Q3 ← I_d + (G_{d−1,d−2,d−2}−G_{d−2,d−1,d−2})/(G_{d−2,d−1,d−1}−G_{d−2,d−1,d−1}) E_{d−2,d−1}'. The guard and denominator are tautological, so the printed algorithm does not execute the Q3 transformation that Example 4.3 and Proposition 4.4 require; this is a concrete correctness bug, not circular reasoning. Similarly, the omitted proof of Lemma 5.3 and the unusual index ranges in Definition 5.6 are correctness/readability concerns rather than circularity. Therefore the circularity score is at the bottom of the normal range.
Assumptions & free parameters
assumptions (4)
- domain assumption Trivial stabilizer theorem: if A*C = C for A ∈ GL_d, then A = I_d, and uniqueness of A for G ∈ GL_d*C.
- domain assumption The core tensor C defined by the axis path has the closed-form entries C_iii=1, C_ijj=C_iij=3 for i<j, C_ijk=6 for i<j<k, and 0 otherwise.
- standard math Shuffle relations for signatures, used in Lemma 5.1 to relate diagonal entries to row sums of A.
- standard math Okamoto's lemma: a nonzero polynomial vanishes on a Lebesgue-null set, used to show that M has full rank with probability one.
Cite this review
Pith. "Pith review of An Efficient Algorithm for Path Recovery from Signature Tensors." pith.science (2026). https://pith.science/paper/BG32LHTL
@misc{pith2026251214218,
author = {Pith},
title = {Pith review of: An Efficient Algorithm for Path Recovery from Signature Tensors},
year = {2026},
howpublished = {\url{https://pith.science/paper/BG32LHTL}},
note = {Machine review of arXiv:2512.14218}
}
read the original abstract
We present a new algorithm for recovering paths from their third-order signature tensors, an inverse problem in rough analysis. Our algorithm provides the exact solution to this recovery problem and improves upon current approaches by an order of magnitude. It relies on generalized normal forms and stabilizers of group actions via matrix-tensor congruence. We apply randomized transformation techniques that avoid the task of solving nonlinear polynomial systems associated to degenerate paths, and accompany our methods with an efficient implementation in the computer algebra system OSCAR.
Forward citations
Cited by 1 Pith paper
-
SignatureTensors.jl: A Package for Signature Tensors in Julia
SignatureTensors.jl is a new Julia package that computes signature tensors of paths, supporting both exact symbolic and numerical computations via compatibility with the OSCAR computer algebra system.
Reference graph
Works this paper leans on
-
[1973]
[PSS19] Max Pfeffer, Anna Seigal, and Bernd Sturmfels
[OSC25] OSCAR – Open Source Computer Algebra Research system, 2025.https://www.oscar-system.org. [PSS19] Max Pfeffer, Anna Seigal, and Bernd Sturmfels. Learning Paths from Signature Tensors.SIAM Journal on Matrix Analysis and Applications,
2025
-
[2019]
Learning barycenters from signature matrices.arXiv preprint arXiv:2509.07815,
[AS25] Carlos Am´ endola and Leonard Schmitz. Learning barycenters from signature matrices.arXiv preprint arXiv:2509.07815,
-
[2025]
Msolve: A library for solving polynomial systems
[BESED21] J´ er´ emy Berthomieu, Christian Eder, and Mohab Safey El Din. Msolve: A library for solving polynomial systems. InProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, pages 51–58,
2021
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.