ABSTRACT
In a special situation, when the matrix is of low rank, it is possible to estimate the entire matrix, provided “enough” samples are available. Researchers in machine learning and signal processing have been interested in non-deterministic polynomial hard problem in the past few years for a variety of problems. What they did was to solve the tightest convex surrogate of rank minimization. Mathematicians are taking a closer look at the matrix completion problem and its relation with nuclear norm minimization. They are interested in finding the bounds on the number of entries required to estimate the complete matrix and the conditions necessary to be imposed on the nature of the matrix and the mask. This chapter briefly discusses these theoretical results. It also discusses the problem of matrix completion of a low-rank matrix; this has been generalized. Instead of using a masking operator, one can use any linear measurement operator.
