Design of MDP Convolutional Codes and Maximally Recoverable Codes Through the Lens of Matrix Completion

Sakshi Dang, Julia Lieb, Pedro Soto, Alex Sprintson · 2026

Read Design of MDP Convolutional Codes and Maximally Recoverable Codes Through the Lens of Matrix Completion by Sakshi Dang, Julia Lieb, Pedro Soto, Alex Sprintson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21544.txt.

Introduction

Sakshi Dang and three colleagues view locally recoverable codes with maximal recoverability and maximum distance profile convolutional codes through matrix completion. They present techniques general enough to construct both code types. A shared feature of their constructions is sparse generator matrices, many of whose entries lie in a small subfield of a larger extension field.

Catalog record

CREATORSakshi Dang, Julia Lieb, Pedro Soto, Alex Sprintson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40255
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2604.21544

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Design of MDP Convolutional Codes and Maximally Recoverable Codes Through the Lens of Matrix Completion Thanks: [email protected] Thanks: [email protected] Thanks: [email protected] Thanks: [email protected] Sakshi Dang, Julia Lieb, Pedro Soto, Alex Sprintson Abstract The matrix completion problem provides a unifying lens through which many fundamental problems in coding theory can be viewed. In this paper, we investigate Locally Recoverable Codes (LRCs) with Maximal Recoverability (MR) and Maximum Distance Profile (MDP) convolutional codes in the framework of matrix completion. In particular, we present techniques that are general enough to provide constructions for both types of codes. A common feature of our code constructions is the sparsity of their generator matrices and the property that a large number of the entries of the generator matrices are elements of a small subfield of a larger extension field. Key Words : Matrix Completion, Convolutional codes, Maximally recoverable codes. 1 Introduction The matrix completion problem provides a powerful and unifying perspective for understanding a broad class of fundamental problems in coding theory and related areas. In particular, many code design problems, including the construction of convolutional codes, distributed storage codes, and codes for wireless communication, can be naturally formulated as variants of the matrix completion problem. In its most general formulation, the problem considers a partially specified matrix subject to structural constraints, such as column dependencies, and block-structure requirements, together with unconstrained (free) entries. These constraints can be captured algebraically by specifying a set of polynomial equations over the matrix entries and fixing selected entries to given values. The goal of the matrix completion problem is to assign values to the free entries to satisfy specified algebraic objectives, such as ensuring the non-vanishing of specified full-size minors, while minimizing the required finite field size. The overarching challenge is to develop principled matrix completion frameworks that apply uniformly across a wide range of constraint patterns. One class of matrix completion problems concerns the construction of a generator matrix of an MDS code that has a prescribed zero pattern (support constraint). The related GM-MDS 1 1 1 GM-MDS conjecture stands for Generator Matrix - Maximum Distance Separable conjecture. conjecture, introduced by Dau, Song, and Yuen in [ DSY14 ] , posits that the natural combinatorial feasibility criterion often called the MDS condition is not only necessary, but also sufficient to guarantee the existence of an MDS generator matrix over any field of size linear in the length of the code. The conjecture was subsequently resolved in full in [ Lov21 , YH19 ] . Also the design of Maximum Distance Profile (MDP) convolutional codes (commonly referred to as MDP codes) can be viewed as a variation of the matrix completion problem [ DLM+25 ] . Convolutional codes are important for low-delay encoding and decoding of a stream of data and MDP codes are the class of convolutional codes that allows for best possible error-correction in this setting [ TRS12 ] . The sliding generator matrix of a convolutional code takes a specific form in which multiple copies of blocks are arranged in a repeating sliding pattern and some entries are fixed to zero. While this structural constraint does not allow every full-size minor to be non-zero, sliding generator matrices of MDP codes have the property that each full size minor that can be nonzero, given the prescribed structural requirement, is nonzero, [ GLRS06 ] . There exist several constructions for MDP codes, however mostly requiring large finite fields; see e.g., [ ANNR24 , Che23 , Che26 , LCEL23 , ANP13 ] . Another problem that can be viewed through the lens of Matrix Completion is the design of Locally Recoverable Codes (LRCs) that are Maximally Recoverable (MR). The local recoverability property implies the existence of a collection of repair groups such that each group enables local recovery of its symbols; that is, symbol(s) in a repair group can be recovered using only the symbols within that group. MR-LRCs provide recoverability from the largest possible set of erasure patterns (see [ BHH13 , GHJY14 , GG22 , CMST22 , MP22 ] and references therein) among linear block codes fulfilling certain locality constraints. In this paper, we focus on a class of MR-LRCs with unequal locality, i.e., codes in which the subcodes that correspond to different repair groups might have different sizes and dimensions, in addition to a set of global parity symbols which are not included in the repair groups. We present a matrix-completion technique that is broad enough to encompass the construction of both code families. A unifying aspect of these constructions is a sparse generator matrix with elegant structural properties including that certain submatrices of the generator matrix are constructed using a small subfield of a larger extension field. Such a structure facilitates efficient encoding and decoding procedures. In Section 2, we provide preliminaries on matrix completion, MR-LRCs and MDP codes. In Section 3, we present a construction for MR-LRCs with unequal localities for certain parameters. In Section 4, we present constructions for MDP codes with certain parameters. In Section 5, we explain commonalities of these constructions and mention some related matrix completion problems to be considered for future research. 2 Preliminaries We start with giving the matrix completion problem in a general form before considering specific instances of it, i.e. the construction of certain MR-LRCs and MDP codes. Definition 1 . Let M be a K\times N matrix whose entries m_{i,j} for i=1,\ldots,K , j=1,\ldots,N are considered as variables. Define \mathbb{F}_{q}[M]:=\mathbb{F}_{q}[m_{1,1},\ldots,m_{K,N}] and consider a set of polynomials f_{\ell}(M)\in\mathbb{F}_{q}[M] for \ell=1,\ldots,s . We say that a solution to the matrix completion problem corresponding to f_{1},\ldots,f_{s} is a set of values for the m_{i,j}\in\mathbb{F}_{q} that satisfies the following conditions: 1. f_{\ell}(M)=0 for \ell=1,\ldots,s (these equations are called constraints of the matrix completion problem); 2. all non-trivial full-size minors , i.e., the K\times K minors of M that are not nilpotent in the ring \mathbb{F}_{q}[M]/\left\langle f_{1}(M),\ldots,f_{s}(M)\right\rangle , are non-zero at the values chosen for m_{i,j} ( f is nilpotent if there exists a positive integer n such that f^{n}=0 ). 2.1 Maximally Recoverable Locally Recoverable Codes with Unequal Locality (MR-LRCs with UL) In this paper, we focus on Locally Recoverable Codes with Unequal Locality (LRCs with UL) [ KS16 , ZY16 ] , defined as follows. Definition 2 . Let \mathcal{C} be a non-degenerate linear block code of length L . We say that a codeword symbol c_{j} for j\in\{1,\ldots,L\} has locality k_{j} if there exists a repair group R_{j}\subset\{1,\ldots,L\} such that j\in R_{j} and \mathcal{C}|_{R_{j}} forms a [|R_{j}|,k_{j},\delta_{j}] -code; if \delta_{j}>1 for all j , then we call it a Locally Recoverable Code with Unequal Locality . There exists a modified Singleton bound on the minimum distance of LRCs with UL [ KS16 , ZY16 ] . We extend LRCs with UL to MR-LRCs with UL by requiring maximum recoverability, i.e. all erasure patterns that can be recovered under the given locality constraints should be recovered. This property is considerably stronger than reaching the modified Singleton bound and captures the code’s full erasure-correction potential. Definition 3 . For \ell,h,n_{i},k_{i}\in\mathbb{N} with n_{i}\geq k_{i} for i=0,\ldots,\ell-1 , let \mathcal{C}\subseteq\mathbb{F}_{q}^{N} be an \mathbb{F}_{q} -linear code of length N=n_{0}+\cdots+n_{\ell-1}+h and dimension K=k_{0}+\cdots+k_{\ell-1} . Set \mathcal{G}_{i}:=\{1+\sum_{t=0}^{i-1}n_{t},\ldots,\sum_{t=0}^{i}n_{t}\} for i=0,\ldots,\ell-1 . Note that these sets

Read the complete text