%0 Conference Paper %1 brand2002incremental %A Brand, Matthew %B Computer Vision --- ECCV 2002 %C Berlin %D 2002 %E Heyden, Anders %E Sparr, Gunnar %E Nielsen, Mads %E Johansen, Peter %I Springer %K 15a18-eigenvalues-singular-values-and-eigenvectors 65f15-numerical-eigenvalues-eigenvectors 68t45-machine-vision-scene-understanding 68u99-computing-methodologies-and-applications %P 707--720 %R 10.1007/3-540-47969-4_47 %T Incremental Singular Value Decomposition of Uncertain Data with Missing Values %U https://link.springer.com/chapter/10.1007%2F3-540-47969-4_47 %V 2350 %X 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 × 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. %@ 978-3-540-47969-7

@inproceedings{brand2002incremental, abstract = {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 {\texttimes} 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.}, added-at = {2021-07-12T07:45:24.000+0200}, address = {Berlin}, author = {Brand, Matthew}, biburl = {https://www.bibsonomy.org/bibtex/2912e088924a24dd48dac39f416ab336e/gdmcbain}, booktitle = {Computer Vision --- ECCV 2002}, doi = {10.1007/3-540-47969-4_47}, editor = {Heyden, Anders and Sparr, Gunnar and Nielsen, Mads and Johansen, Peter}, eventdate = {Computer vision - ECCV 2002. 7th European conference, Copenhagen, DenmarkMay 28–31}, eventtitle = {Computer vision - ECCV 2002. 7th European conference}, interhash = {725188396eb67f7db3edda04032d460a}, intrahash = {912e088924a24dd48dac39f416ab336e}, isbn = {978-3-540-47969-7}, keywords = {15a18-eigenvalues-singular-values-and-eigenvectors 65f15-numerical-eigenvalues-eigenvectors 68t45-machine-vision-scene-understanding 68u99-computing-methodologies-and-applications}, pages = {707--720}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2021-07-12T07:48:07.000+0200}, title = {Incremental Singular Value Decomposition of Uncertain Data with Missing Values}, url = {https://link.springer.com/chapter/10.1007%2F3-540-47969-4_47}, venue = {Copenhagen, Denmark}, volume = 2350, year = 2002 }