Abstract
A matrix completion problem starts with a partially specified matrix, where some entries are known and some are not. The goal is to find the unknown entries (“complete the matrix”) in such a way that the full matrix satisfies certain properties. We will mostly be interested in completing a partially specified symmetric matrix to a full positive semidefinite matrix, and we will also consider controlling the rank of the completion. I will explain how this is naturally a sum of squares problem, discuss some generalizations and present new results with applications in optimization (exactness of low level sum of squares relaxations) and Gaussian graphical models (existence of maximum likelihood estimates from few observations).