Large-scale matrix factorization with missing data under additional constraints

Matrix factorization in the presence of missing data is at the core of many com-puter vision problems such as structure from motion (SfM), non-rigid SfM and
photometric stereo. We formulate the problem of matrix factorization with miss-
ing data as a low-rank semidefinite program (LRSDP) with the advantage that:
1) an efficient quasi-Newton implementation of the LRSDP enables us to solve
large-scale factorization problems, and 2) additional constraints such as ortho-
normality, required in orthographic SfM, can be directly incorporated in the new
formulation. Our empirical evaluations suggest that, under the conditions of ma-
trix completion theory, the proposed algorithm finds the optimal solution, and also
requires fewer observations compared to the current state-of-the-art algorithms.
We further demonstrate the effectiveness of the proposed algorithm in solving the
affine SfM problem, non-rigid SfM and photometric stereo problems.