×

zbMATH — the first resource for mathematics

Incremental singular value decomposition of uncertain data with missing values. (English) Zbl 1034.68580
Heyden, Anders (ed.) et al., Computer vision - ECCV 2002. 7th European conference, Copenhagen, Denmark, May 28–31, 2002. Proceedings. Part 1. Berlin: Springer (ISBN 3-540-43745-2). Lect. Notes Comput. Sci. 2350, 707-720 (2002).
Summary: We introduce an incremental singular value decomposition (SVD) of incomplete data. The SVD is developed as data arrives, and can handle arbitrary missing/untrusted values, correlated uncertainty across rows or columns of the measurement matrix, and user priors. Since incomplete data does not uniquely specify an SVD, the procedure selects one having minimal rank. For a dense \(p\times q\) matrix of low rank \(r\), the incremental method has time complexity \(O(pqr)\) and space complexity \(O((p+q)r)\) – better than highly optimized batch algorithms such as MATLAB’s svd(). In cases of missing data, it produces factorings of lower rank and residual than batch SVD algorithms applied to standard missing-data imputations. We show applications in computer vision and audio feature extraction. In computer vision, we use the incremental SVD to develop an efficient and unusually robust subspace-estimating flow-based tracker, and to handle occlusions/missing points in structure-from-motion factorizations.
For the entire collection see [Zbl 0992.68526].

MSC:
68U99 Computing methodologies and applications
68T45 Machine vision and scene understanding
Software:
impute; Matlab; svdpack
PDF BibTeX XML Cite
Full Text: Link