Deterministic Completion of Rectangular Matrices Using Ramanujan Bigraphs -- I: Error Bounds and Exact Recovery

  • 2019-10-08 16:56:17
  • Shantanu Prasad Burnwal, Mathukumalli Vidyasagar
  • 0

Abstract

In this paper we study the matrix completion problem: Suppose $X \in {\mathbbR}^{n_r \times n_c}$ is unknown except for an upper bound $r$ on its rank. Bymeasuring a small number $m \ll n_r n_c$ of the elements of $X$, is it possibleto recover $X$ exactly, or at least, to construct a reasonable approximation of$X$? At present there are two approaches to choosing the sample set, namelyprobabilistic and deterministic. Probabilistic methods can guarantee the exactrecovery of the unknown matrix, but only with high probability. At presentthere are very few deterministic methods, and they mostly apply only to squarematrices. The focus in the present paper is on deterministic methods that workfor rectangular as well as square matrices, and where possible, can guaranteeexact recovery of the unknown matrix. We achieve this by choosing the elementsto be sampled as the edge set of an asymmetric Ramanujan graph or Ramanujanbigraph. For such a measurement matrix, we (i) derive bounds on the errorbetween a scaled version of the sampled matrix and unknown matrix; (ii) derivebounds on the recovery error when max norm minimization is used, and (iii)present suitable conditions under which the unknown matrix can be recoveredexactly via nuclear norm minimization. In the process we streamline someexisting proofs and improve upon them, and also make the results applicable torectangular matrices. This raises two questions: (i) How can Ramanujan bigraphsbe constructed? (ii) How close are the sufficient conditions derived in thispaper to being necessary? Both questions are studied in a companion paper.

 

Quick Read (beta)

loading the full paper ...