Rank-Metric in Coding Theory and Machine Learning
Final Report Abstract
The main results of the project are as follows: 1. Application of module minimization for decoding Gabidulin codes (defined with skew polynomials instead of linearized polynomials). Before, module minimization was only applied to Reed–Solomon (RS) codes. An extension for interleaved Gabidulin codes was done. Further, also decoding the class of Mahdavifar– Vardy codes is possible. 2. Proof that the low-rank matrix recovery problem can be reduced to the decoding of Gabidulin codes over fields with characteristic zero. 3. A novel decoding method for interleaved Gabidulin codes in characteristic zero using the Alekhnovich algorithm for row reduction of skew polynomial matrices. 4. The first decoder with sub-quadratic complexity for Gabidulin codes was found. This result is based on the fact that several accelerations of operations for linearized polynomials were developed. 5. Reed–Solomon codes as well as their rank metric analogon, Gabidulin codes over fields of characteristic zero causes numerical issues when floating point operations are used. In order to avoid numerical instabilities, exact computations can be used, e.g., over the field of rational numbers. We found bounds for the growths of the numerators and denominators of the considered fractions during encoding and decoding. The usage of rational numbers is only started and several open problems remain. However, it is a promising method since then codes can play an important role in the field of signal processing. Further, it could be extended to complex numbers, where real and imaginary part are rational numbers.
Publications
- Channel Coding Inspired Contributions to Compressed Sensing. PhD thesis, Universität Ulm, 2015
Henning Alexander Zörlein
(See online at https://doi.org/10.18725/OPARU-3247) - Decoding Evaluation Codes and their Interleaving. PhD thesis, Universität Ulm, 2015
Wenhui Li
(See online at https://doi.org/10.18725/OPARU-3250) - Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation. International Workshop on Coding and Cryptography, 2015
Wenhui Li, Johan S. R. Nielsen, Sven Puchinger, and Vladimir Sidorenko
- An Alternative Decoding Method for Gabidulin Codes in Characteristic Zero. IEEE International Symposium on Information Theory (ISIT), pages 2549–2553, 2016
Sven Muelich, Sven Puchinger, David Mödinger, and Martin Bossert
(See online at https://doi.org/10.1109/ISIT.2016.7541759) - Sub-quadratic Decoding of Gabidulin Codes. IEEE International Symposium on Information Theory (ISIT), pages 2554–2558, 2016
Sven Puchinger and Antonia Wachter-Zeh
(See online at https://doi.org/10.1109/ISIT.2016.7541760) - Decoding Interleaved Gabidulin Codes using Alekhnovich’s Algorithm. Electronic Notes in Discrete Mathematics, 57:175–180, 2017
Sven Puchinger, Sven Müelich, David Mödinger, Johan Rosenkilde né Nielsen, and Martin Bossert
(See online at https://doi.org/10.1016/j.endm.2017.02.029) - Low-Rank Matrix Recovery using Gabidulin Codes in Characteristic Zero. Electronic Notes in Discrete Mathematics, 57:161–166, 2017
Sven M¨üelich, Sven Puchinger, and Martin Bossert
(See online at https://doi.org/10.1016/j.endm.2017.02.027) - Popov Form Computation for Matrices of Ore Polynomials. Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 253–260, 2017
Mohamed Khochtali, Johan Rosenkilde né Nielsen, and Arne Storjohann
(See online at https://doi.org/10.1145/3087604.3087650) - Row Reduction Applied to Decoding of Rank-Metric and Subspace Codes. Designs, Codes and Cryptography, 82(1-2):389–409, 2017
Sven Puchinger, Johan Rosenkilde né Nielsen, Wenhui Li, and Vladimir Sidorenko
(See online at https://doi.org/10.1007/s10623-016-0257-9) - Algebraic Decoding over Finite and Complex Fields using Reliability Information. PhD thesis, Universität Ulm, 2018
Mostafa Hosni Mohamed
(See online at https://doi.org/10.18725/OPARU-5289) - Construction and Decoding of Evaluation Codes in Hamming and Rank Metric. PhD thesis, Universität Ulm, 2018
Sven Puchinger
(See online at https://doi.org/10.18725/OPARU-9446) - Fast Operations on Linearized Polynomials and their Applications in Coding Theory. Journal of Symbolic Computation, 89:194–215, 2018
Sven Puchinger and Antonia Wachter-Zeh
(See online at https://doi.org/10.1016/j.jsc.2017.11.012) - Reed–Solomon Codes over Fields of Characteristic Zero. IEEE International Symposium on Information Theory (ISIT), 2019
Carmen Sippel, Cornelia Ott, Sven Puchinger, and Martin Bossert
(See online at https://doi.org/10.1109/ISIT.2019.8849332)
