Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations

DOI10.1109/TIT.2011.2178017MaRDI QIDQ5271992zbMATH OpenOpenAlexFDO

Authors Vincent Y. F. Tan, Laura Balzano, Stark C. Draper

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.4302

Mathematics Subject Classification ID

Finite fields (field-theoretic aspects) (12E20) Vector spaces, linear dependence, rank, lineability (15A03) Coding theorems (Shannon theory) (94A24)

Abstract: This paper establishes information-theoretic limits in estimating a finite field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the low-rank matrix with random sensing matrices. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp and the minimum-rank decoder is asymptotically optimal. The reliability function of this decoder is also derived by appealing to de Caen's lower bound on the probability of a union. The sufficient condition also holds when the sensing matrices are sparse - a scenario that may be amenable to efficient decoding. More precisely, it is shown that if the n imes n-sensing matrices contain, on average, Omega(nlog n) entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the above results and rank-metric codes in the coding theory literature. In fact, we are also strongly motivated by understanding when minimum rank distance decoding of random rank-metric codes succeeds. To this end, we derive distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one. Finally, we provide a non-exhaustive procedure to search for the unknown low-rank matrix.

Cited in

(8)

• The minimal measurement number for low-rank matrix recovery
• Almost everywhere injectivity conditions for the matrix recovery problem
• Improvements of algebraic attacks for solving the rank decoding and MinRank problems
• The minimum rank problem over finite fields
• Uniqueness conditions for low-rank matrix recovery
• On the equivalence between low-rank matrix completion and tensor rank
• Revisiting algebraic attacks on MinRank and on the rank decoding problem
• The minimum rank problem over the finite field of order 2: Minimum rank 3

This page was built for publication: Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5271992)