Rank-Metric in Coding Theory and Machine Learning (RaMComp)

Rang-Metrik in der Codierungstheorie und im Maschinellen Lernen

• Professor Dr.-Ing. Martin Bossert
  Universität Ulm
  Fakultät Ingenieurwissenschaften, Informatik und Psychologie
  Institut für Nachrichtentechnik
  
  
• Professor Dr. David Gross
  Albert-Ludwigs-Universität Freiburg
  Fakultät für Mathematik und Physik
  Physikalisches Institut
  
  

Summary

Two different communities - information theory and machine learning - have recently started to investigate the mathematical problem of finding the matrix of minimal rank in an affine space. They have done so for completely different reasons and have proposed very different approaches. In machine learning, rank has been identified as an extremely useful regularization parameter for otherwise ill-posed inverse problems. In the past four years, dozens of applications of the low-rank recovery problem have been identified. They range from image processing, over robust recovery of signals from quadratic measurements, to the prediction of user preferences in online shops from incomplete data. Independently, researchers working on coding theory have realized that errors that naturally occur in certain network coding scenarios are of low rank when represented as suitable matrices. The decoding problem is formally equivalent to the low-rank recovery one of machine learning. (This is analogous to the relation between compressed sensing and Hamming-metric decoding, that has been fruitfully exploited in the past). Despite the close resemblance between the two tasks, almost no transfer of concepts and methods between the two communities has taken place so far. This project - uniting two groups with expertise in, respectively, coding and low-rank recovery - aims to amend this situation.

Preprints

1. Sven Puchinger and Antonia Wachter-Zeh, Fast Operations on Linearized Polynomials and their Applications in Coding Theory, December 2015

2. Sven Müelich, Sven Puchinger, and Martin Bossert, Low-Rank Matrix Recovery using Gabidulin Codes in Characteristic Zero, April 2016

Publications

1. Sven Müelich, Sven Puchinger, and Martin Bossert, Low-Rank Matrix Recovery using Gabidulin Codes in Characteristic Zero, 15th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Albena, Bulgaria, June 2016.

2. Sven Müelich, Sven Puchinger, David Mödinger and Martin Bossert, An Alternative Decoding Method for Gabidulin Codes in Characteristic Zero, IEEE International Symposium on Information Theory, Barcelona, Spain, July 2016.

3. Sven Puchinger and Antonia Wachter-Zeh, Sub-Quadratic Decoding of Gabidulin Codes, IEEE International Symposium on Information Theory, Barcelona, Spain, July 2016.