pith. sign in

arxiv: 2604.16105 · v1 · submitted 2026-04-17 · 💻 cs.IT · math.IT

Decoding Algorithms for Tensor Codes

Eimear Byrne , Alain Couvreur , Lucien Fran\c{c}ois This is my paper

Pith reviewed 2026-05-10 07:28 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords tensor codesdecoding algorithmstensor-rank metricLoidreau-Overbeck decodingslice spacesfibre spacesGabidulin codeserror correction
0
0 comments X

The pith

Tensor codes admit a generalized Loidreau-Overbeck decoder that corrects errors whose slice and fibre spaces obey dimension bounds, and the same methods recover tensor-rank weight errors.

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

The paper develops decoding techniques for tensor codes, subspaces of higher-order tensors equipped with the tensor-rank metric. It first presents a fibre-wise decoder that reduces each fibre of a codeword to a Gabidulin codeword. It then supplies a generalization of the Loidreau-Overbeck algorithm that succeeds when the error's slice spaces and fibre spaces have sufficiently small dimensions. Because every metric considered is bounded above by tensor rank, the algorithms also correct errors measured in the tensor-rank metric.

Core claim

We give a generalisation of Loidreau-Overbeck's decoding method that corrects errors with properties constrained by the dimensions of the slice spaces and fibre spaces. The metrics we consider are bounded from above by the tensor-rank metric, and therefore these algorithms also decode tensor-rank weight errors. We first consider a fibre-wise decoding approach, as each fibre of a codeword corresponds to a Gabidulin codeword.

What carries the argument

Generalized Loidreau-Overbeck decoder that succeeds precisely when error slice spaces and fibre spaces satisfy explicit dimension bounds

If this is right

  • Each fibre of a tensor codeword can be decoded independently as a Gabidulin codeword.
  • Errors whose slice and fibre spaces obey the dimension constraints are correctable by the generalized method.
  • Any metric upper-bounded by tensor rank inherits the same correction capability.
  • The fibre-wise reduction and the generalized method together cover a broader class of errors than tensor-rank decoding alone.

Where Pith is reading between the lines

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

  • Practical implementations could support reliable storage or transmission of multi-way arrays in applications that already use matrix codes.
  • The dimension-constrained error model may extend naturally to other algebraic constructions that possess a natural fibre or slice decomposition.
  • Efficient computation of the required slice and fibre spaces would determine whether the new algorithms outperform direct tensor-rank decoders in practice.

Load-bearing premise

The error pattern must have slice and fibre spaces whose dimensions fall within the bounds required by the generalized decoder.

What would settle it

An explicit error tensor whose slice and fibre spaces obey the stated dimension bounds yet causes the generalized decoder to output the wrong codeword.

Figures

Figures reproduced from arXiv: 2604.16105 by Alain Couvreur, Eimear Byrne, Lucien Fran\c{c}ois.

Figure 1
Figure 1. Figure 1: Illustration of sω for n = 3. and if i1 ∈ J1, nK, then M[i1, :] = (Mi1,i2 ) i2∈J1,nK is the i th 1 row of the matrix M, and if T ∈ (F n q ) ⊗3 is a 3-tensor, then T[i1, :, :] = (T[i1, i2, i3])(i2,i3)∈J1,nK 2 is the n 2 -tuple/matrix of size n × n whose entry at (i2, i3) is T[i1, i2, i3]. Slices and fibres For each j ∈ {1, 2, 3}, we consider the j-slices of a tensor in (F n q ) ⊗3 to be the matrices obtaine… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of tensor-rank one, two, and three elements in [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Like in Subsection 3.4, we can show that for any T ∈ F n×n qn , the weights wssj (T), j ∈ J1, mK and wfsm+1 (T) are bounded from above by trankFq (T), and that wΣss(T) ≤ 2 trankFq (T). In particular, we are in the same configuration as for the case m = 2 and we obtain the following corollary. Corollary 6.8. The Fq-tensor code Cα(J0, µK m) of dimension n(µ + 1)m over Fq endowed with the tensor￾rank metric i… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the uncorrectable errors for [PITH_FULL_IMAGE:figures/full_fig_p035_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Improvement rate between the correctable errors of the two fibre-wise technique. [PITH_FULL_IMAGE:figures/full_fig_p037_4.png] view at source ↗
read the original abstract

Tensor codes are a generalisation of matrix codes. Such codes are defined as subspaces of order-r tensors for which the ambient space is endowed with the tensor-rank as a metric. A class of these codes was introduced by Roth, who also outlined a decoding algorithm for low tensor-rank errors that can be generalised to an algorithm with exponential complexity in the decoding radius. They may be viewed as a generalisation of the well-known Delsarte-Gabidulin-Roth maximum rank distance codes. We study a generalised class of these codes. We investigate their properties and outline decoding techniques for different metrics that leverage their tensor structure. We first consider a fibre-wise decoding approach, as each fibre of a codeword corresponds to a Gabidulin codeword. We then give a generalisation of Loidreau-Overbeck's decoding method that corrects errors with properties constrained by the dimensions of the slice spaces and fibre spaces. The metrics we consider are bounded from above by the tensor-rank metric, and therefore these algorithms also decode tensor-rank weight errors.

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

1 major / 3 minor

Summary. The paper generalizes tensor codes as subspaces of order-r tensors over finite fields equipped with the tensor-rank metric, extending Roth's matrix codes and Delsarte-Gabidulin-Roth MRD codes. It investigates code properties and proposes two decoding methods: a fibre-wise decoder that reduces each fibre to a Gabidulin codeword, and a generalization of the Loidreau-Overbeck algorithm that corrects errors whose slice-space and fibre-space dimensions satisfy explicit constraints. The considered metrics are proven to satisfy d_new(e) ≤ d_tensor(e) for all error tensors e, so the new decoders also correct tensor-rank errors.

Significance. If the algorithmic claims and metric inequalities hold with explicit bounds, the work meaningfully extends rank-metric coding theory to higher-order tensors and supplies concrete decoders that exploit the tensor structure. This could support applications in multi-dimensional network coding or distributed storage where tensor errors arise. The reduction to known Gabidulin and Loidreau-Overbeck decoders is a strength, provided the dimension constraints and complexity are fully characterized.

major comments (1)
  1. [Description of the generalized decoder and metric comparison] The abstract and outline state that the generalized Loidreau-Overbeck decoder succeeds on errors constrained by slice/fibre-space dimensions and that the new metrics are bounded above by tensor rank, but the manuscript must supply the explicit dimension bounds, the precise statement of the correction radius, and a self-contained correctness proof (or reduction to the cited Loidreau-Overbeck result) rather than a sketch; without these the central claim that the algorithms decode the claimed balls remains unverifiable.
minor comments (3)
  1. Define the tensor-rank metric and the new bounded metrics formally at the first appearance, including how the slice and fibre spaces are extracted from an order-r tensor.
  2. Add a small concrete example (e.g., r=3, small field and dimensions) illustrating both the fibre-wise decoder and the generalized method, including the computed slice/fibre dimensions and the decoded codeword.
  3. Clarify the complexity of the generalized decoder as a function of the decoding radius and the tensor order; the abstract mentions an exponential-complexity generalization of Roth's algorithm but does not compare it with the new methods.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We agree that the presentation of the generalized Loidreau-Overbeck decoder requires expansion for verifiability and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Description of the generalized decoder and metric comparison] The abstract and outline state that the generalized Loidreau-Overbeck decoder succeeds on errors constrained by slice/fibre-space dimensions and that the new metrics are bounded above by tensor rank, but the manuscript must supply the explicit dimension bounds, the precise statement of the correction radius, and a self-contained correctness proof (or reduction to the cited Loidreau-Overbeck result) rather than a sketch; without these the central claim that the algorithms decode the claimed balls remains unverifiable.

    Authors: We agree that the current manuscript presents the generalized Loidreau-Overbeck decoder primarily as an outline with a proof sketch, and that explicit dimension bounds and a precise correction radius are not fully stated in the main text. In the revision we will add: the explicit constraints on slice-space and fibre-space dimensions under which the decoder succeeds; the precise correction radius expressed in terms of these dimensions; and a self-contained correctness proof obtained by a direct reduction to the cited Loidreau-Overbeck algorithm, including all necessary intermediate lemmas and steps. We will also state the metric inequalities d_new(e) ≤ d_tensor(e) with explicit proofs. These changes will render the claims verifiable while preserving the reduction to known decoders. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper generalizes Roth's tensor codes and Loidreau-Overbeck decoding via explicit dimension constraints on slice/fibre spaces and proves new metrics satisfy d_new(e) ≤ d_tensor(e) by direct comparison of weight definitions. All steps rely on standard linear-algebraic arguments and cited external results (Roth, Gabidulin, Loidreau-Overbeck) whose proofs are independent of the present work. No parameter is fitted then relabeled as prediction, no self-citation supplies a uniqueness theorem, and no ansatz is smuggled; the logical chain from code definition to decoder correctness is externally verifiable and does not reduce to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard properties of Gabidulin codes and tensor rank being a metric, with no new free parameters or invented entities introduced in the abstract.

axioms (2)
  • domain assumption Gabidulin codes admit efficient decoding for rank errors up to a certain radius.
    Invoked when treating fibres as Gabidulin codewords.
  • standard math Tensor rank defines a metric on the ambient tensor space.
    Stated as the distance measure for the codes.

pith-pipeline@v0.9.0 · 5475 in / 1254 out tokens · 50255 ms · 2026-05-10T07:28:32.627969+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

34 extracted references · 34 canonical work pages

  1. [1]

    Decoding algorithms for tensor codes,

    L. François, E. Byrne, and A. Couvreur, “Decoding algorithms for tensor codes,” in2025 IEEE Inter- national Symposium on Information Theory (ISIT), 2025, pp. 1–6

    work page 2025

  2. [2]

    Generalized twisted Gabidulin codes,

    G. Lunardon, R. Trombetti, and Y. Zhou, “Generalized twisted Gabidulin codes,”Journal of Combina- torial Theory, Series A, vol. 159, pp. 79–106, 2018

    work page 2018

  3. [3]

    A new family of linear maximum rank distance codes,

    J. Sheekey, “A new family of linear maximum rank distance codes,”Adv. Math. Commun., vol. 10, 2016

    work page 2016

  4. [4]

    Maximum-rank array codes and their application to crisscross error correction,

    R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction,”IEEE Trans. Inf. Theor., vol. 37, no. 2, p. 328–336, sep 2006

    work page 2006

  5. [5]

    Tensor codes for the rank metric,

    R. Roth, “Tensor codes for the rank metric,”IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 2146–2157, 1996

    work page 1996

  6. [6]

    Error correction for algebraic block codes,

    L. R. Welch and E. R. Berlekamp, “Error correction for algebraic block codes,” Dec. 30 1986, US Patent 4,633,470

    work page 1986

  7. [7]

    Decoding of cyclic codes and codes on curves,

    R. E. Blahut, “Decoding of cyclic codes and codes on curves,” inHandbook of Coding Theory, Vol. II, V. S. Pless and W. C. Huffman, Eds. Elsevier, 1998, pp. 1569–1633

    work page 1998

  8. [8]

    A Welch-Berlekamp like algorithm for decoding Gabidulin codes,

    P. Loidreau, “A Welch-Berlekamp like algorithm for decoding Gabidulin codes,” inCoding and Cryp- tography, Ø. Ytrehus, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 36–45

    work page 2006

  9. [9]

    Lidl and H

    R. Lidl and H. Niederreiter,Introduction to Finite Fields and Their Applications, ser. Encyclopedia of Mathematics. Cambridge University Press, 1994

    work page 1994

  10. [10]

    Theory of codes with maximum rank distance (translation),

    E. Gabidulin, “Theory of codes with maximum rank distance (translation),”Problems of Information Transmission, vol. 21, pp. 1–12, 01 1985

    work page 1985

  11. [11]

    Bürgisser, M

    P. Bürgisser, M. Clausen, and M. A. Shokrollahi,Multiplicative and bilinear complexity. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997, pp. 351–374. [Online]. Available: https: //doi.org/10.1007/978-3-662-03338-8_14

    work page doi:10.1007/978-3-662-03338-8_14 1997

  12. [12]

    Cooperstein,Advanced Linear Algebra

    B. Cooperstein,Advanced Linear Algebra. CRC Press, 2010

    work page 2010

  13. [13]

    The tensor product,

    S. Lang, “The tensor product,” inAlgebra, ser. Graduate Texts in Mathematics. New York: Springer New York, 2002, vol. 211, pp. 601–640

    work page 2002

  14. [14]

    Rank-metric codes,

    E. Gorla, “Rank-metric codes,” inConcise Encyclopedia of Coding Theory. Chapman and Hall/CRC Press, 2021. 33

    work page 2021

  15. [15]

    Rank-metric codes and their duality theory,

    A. Ravagnani, “Rank-metric codes and their duality theory,”Designs, codes, and cryptography, vol. 80, no. 1, pp. 197–216, 2016

    work page 2016

  16. [16]

    Tensor representation of rank-metric codes,

    E. Byrne, A. Neri, A. Ravagnani, and J. Sheekey, “Tensor representation of rank-metric codes,”SIAM Journal on Applied Algebra and Geometry, vol. 3, no. 4, pp. 614–643, 2019. [Online]. Available: https://doi.org/10.1137/19M1253964

    work page doi:10.1137/19m1253964 2019

  17. [17]

    10 Alexander Grigoriev and Hans L Bodlaender

    J. Håstad, “Tensor rank is NP-complete,”Journal of Algorithms, vol. 11, no. 4, pp. 644–654, 1990. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0196677490900146

    work page arXiv 1990

  18. [18]

    Constructions of perfect bases for classes of 3-tensors,

    E. Byrne and G. Cotardo, “Constructions of perfect bases for classes of 3-tensors,”Linear Algebra and its Applications, vol. 683, pp. 1–30, 2024. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0024379523004391

    work page 2024

  19. [19]

    On a special class of polynomials,

    O. Ore, “On a special class of polynomials,”Transactions of the American Mathematical Society, vol. 35, no. 3, pp. 559–584, 1933. [Online]. Available: http://www.jstor.org/stable/1989849

    work page arXiv 1933

  20. [20]

    Theory of non-commutative polynomials,

    ——, “Theory of non-commutative polynomials,”Annals of Mathematics, vol. 34, no. 3, pp. 480–508,

    work page

  21. [21]

    Available: http://www.jstor.org/stable/1968173

    [Online]. Available: http://www.jstor.org/stable/1968173

    work page arXiv

  22. [22]

    Decoding rank errors beyond the error-correcting capability,

    P. Loidreau and R. Overbeck, “Decoding rank errors beyond the error-correcting capability,” inTenth international workshop on Algebraic and Combinatorial Coding Theory, Sep 2006, Zvenigorod, Russia, 2010

    work page 2006

  23. [23]

    Decoding supercodes of Gabidulin codes and applications to cryptanaly- sis,

    M. Bombar and A. Couvreur, “Decoding supercodes of Gabidulin codes and applications to cryptanaly- sis,” inPost-Quantum Cryptography - 12th International Conference, ser. LNCS, J. H. Cheon and J.-P. Tillich, Eds., vol. 12841. Springer, Jul. 2021, pp. 3–22

    work page 2021

  24. [24]

    On interleaved rank metric codes,

    V. Sidorenko, W. Li, and G. Kramer, “On interleaved rank metric codes,” in2020 Algebraic and Com- binatorial Coding Theory (ACCT), 2020, pp. 128–134

    work page 2020

  25. [25]

    Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes,

    V. Sidorenko, L. Jiang, and M. Bossert, “Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes,”IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 621–632, 2011

    work page 2011

  26. [26]

    J. H. Van Lint and R. M. Wilson,A Course in Combinatorics. Cambridge: Cambridge University Press, 1992

    work page 1992

  27. [27]

    Fast decoding of Gabidulin codes,

    A. Wachter-Zeh, V. Afanassiev, and V. Sidorenko, “Fast decoding of Gabidulin codes,”Designs, Codes and Cryptography, vol. 66, no. 1, pp. 57–73, Jan 2013

    work page 2013

  28. [28]

    Golub and C

    G. Golub and C. Van Loan,Matrix Computations, ser. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2013

    work page 2013

  29. [29]

    Reading, Massachusetts: Addison-Wesley, 1997

    D.E.Knuth,The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rded. Reading, Massachusetts: Addison-Wesley, 1997. 34 A Figures 1 2 3 1 0· · ·0 0 0· · ·0 ... ... ... ... 0 0· · ·0 0 0· · ·0 0 1· · ·0 ... ... ... ... 0 0· · ·0 0 0· · ·0 0 0· · ·0 ... ... ... ... 0 0· · ·1 (a) Illustration of ˜E1 α1 · · ·α 1 ... ... ... αa · · ·α a 0· · ·0 .....

    work page 1997

  30. [30]

    The number of tensorsΓ∈F m×n×k q that have Vas first slice-space is the number of (ordered) generating families ofVof lengthk, in other words, the number of ranktmatrices inF k×t q

    LetVbe atdimensional subspace ofF m×n q , witht≤k. The number of tensorsΓ∈F m×n×k q that have Vas first slice-space is the number of (ordered) generating families ofVof lengthk, in other words, the number of ranktmatrices inF k×t q . This number is given in [25, Theorem 25.2]

    work page

  31. [31]

    Thus, the number of spaces spanned by such matrices is m 2 q n 2 q q(q2 −1) = q(q m −1)(q m−1 −1)(q n −1)(q n−1 −1) (q−1) 2(q2 −1)

    There are exactly m 2 q n 2 q q(q−1)(q 2 −1) = q(q m−1)(qm−1−1)(qn−1)(qn−1−1) (q−1)(q 2−1) matrices of rank exactly two inF m×n q (see [25, Theorem 25.2]). Thus, the number of spaces spanned by such matrices is m 2 q n 2 q q(q2 −1) = q(q m −1)(q m−1 −1)(q n −1)(q n−1 −1) (q−1) 2(q2 −1) . 38 Algorithm 8Factoring on the left Input:nan integer,qa prime power...

    work page

  32. [32]

    There are exactly q2 2 m 1 q n 1 q m−1 1 q n−1 1 q subspacesVofF m×n q such that : •Vis generated by two rank one matrices, •the row space ofVis two-dimensional, •and the column space ofVis two-dimensional, where we define the row space and the column space ofVto be respectively the sum of the row spaces and column spaces of the elements inV. Indeed, to e...

    work page

  33. [33]

    Similarly, to enumerate all possible spacesV, it suffices to fix(u1Fq, u2Fq)a pair of subspaces ofF m q andvF q a subspace ofF n q

    There are exactly 1 q+1 m 1 q n 1 q m−1 1 q subspacesVofF m×n q such that : •Vis generated by two rank one matrices, •the row space ofVis one-dimensional, 39 •and the column space ofVis two-dimensional. Similarly, to enumerate all possible spacesV, it suffices to fix(u1Fq, u2Fq)a pair of subspaces ofF m q andvF q a subspace ofF n q. For any such choice, o...

    work page

  34. [34]

    To conclude, with the point 1

    Symmetrically, there are exactly 1 q+1 m 1 q n 1 q n−1 1 q subspacesVofF m×n q such that : •Vis generated by two rank one matrices, •the row space ofVis two-dimensional, •and the column space ofVis one-dimensional. To conclude, with the point 1. and the point 2., we know that the number of tensors of tensor-rank two with one dimensional first slice-space ...

    work page