Rank Minimization Over Finite Fields
The problem of matrix completion has been well studied in recent years. Essentially, one is given a (small) subset of entries of a low-rank matrix and one is required to estimate all the the remaining entries. In this paper, the authors establish information-theoretic limits in estimating a finite field low-rank matrix given random linear measurements of it. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp. The reliability function associated to the minimum-rank decoder is also derived. Their bounds hold even in the case where the sensing matrices are sparse. Connections to rank-metric codes are discussed.