Linear fitting with missing data for structure-from-motion

Several vision problems can be reduced to the problem of fitting a linear s urface of low dimension to data. These include determining affine structure from motion or from intensity images. These methods must deal with missing data; for example, in structure from motion, missing data will occur if so me point features an not visible in the image throughout the motion sequenc e. Once data is missing, linear fitting becomes a nonlinear optimization pr oblem. Techniques such as gradient descent require a good initial estimate of the solution to ensure convergence to the correct answer. We propose a n ovel method for fitting a low rank matrix to a matrix with missing elements . This method produces a good starting point for descent-type algorithms an d can produce an accurate solution without further refinement. We then focu s on applying this method to the problem of structure-from-motion. We show that our method has desirable theoretical properties compared to previously proposed methods, because it can find solutions when there is less data pr esent. We also show experimentally that our method provides good results co mpared to previously proposed methods. (C) 2001 Academic Press.