Spectrally optimal factorization of incomplete matrices

From the recovery of structure from motion to the separation of style and content, many problems in computer vision have been successfully approached by using bilinear models. The reason for the success of these models is that a globally optimal decomposition is easily obtained from the singular value decomposition (SVD) of the observation matrix. However, in practice, the observation matrix is often incomplete, the SVD can not be used, and only suboptimal solutions are available. The majority of these solutions are based on iterative local refinements of a given cost function, and lack any guarantee of convergence to the global optimum. In this paper, we propose a globally optimal solution, for particular patterns of missing entries. To achieve this goal, we re-formulate the problem as the minimization of the spectral norm of the matrix of residuals, i.e., we seek the completion of the observation matrix such that the largest singular value of its difference to a low rank matrix is the smallest possible. The class of patterns of missing entries we deal with is known as the Young diagram, which includes, as particular cases, many relevant situations, such as the missing of an entire submatrix. We describe experiments that illustrate how our globally optimal solution has impact in practice.

1. Introduction

Various large-scale nonlinear problems in computer vision have been addressed by exploiting bilinear models. Examples include the recovery of rigid structure from motion [18], [16], inference of non-rigid models [4], estimation of image motion [12], modeling images obtained with different lighting [3], photometric stereo [2], object recognition [19], and the separation of style and content in images [7]. Usually, a matrix that collects the observations is expressed as the product of two matrices collecting (functions of) the parameters to estimate. This bilinear relation codes a constraint on the rank of the observation matrix. The advantage of this formulation is that the bulk of the effort needed to compute the solution of the large-scale nonlinear estimation problem is done by computing the rank constrained matrix that best matches the observation matrix (thus, its optimal bilinear decomposition), which is easily obtained from its Singular Value Decomposition (SVD).