Incremental SVD of Incomplete and Uncertain Data
The incremental incomplete singular value decomposition makes it possible to produce useful inferences from data even when most the data is missing. For example, we have used it to accurately predict consumer preferences (what movies one would like) from a table of movie ratings that is 97% empty.
Background & Objective: The singular value decomposition (SVD) forms the core of thousands of algorithms in signal processing. Computing an SVD becomes difficult or even impossible if some of the data is missing, if the dataset is too large, or if the data is contaminated with non-white noise. We set out to develop algorithm for the SVD that can be computed online as the data comes in and can handle varying noise conditions, including datapoints that are entirely missing.
Technical Discussion: The incremental incomplete SVD combines and improves recently developed methods for updating an SVD with new data, imputing missing values, and finding most probable least-squares solutions when noise is anisotropic and inhomogeneous. Remarkably, the resulting algorithm has better time and space complexity than batch SVD algorithms and computes solutions of comparable accuracy. To date, the algorithm has been used to predict consumer preferences, to extract 3D shape information from video, and compute compression bases for audio and video datasets having tens of millions of datapoints.
Contact: Matthew Brand
Technology Area: Artificial Intelligence
Modification Date: July 23, 2003
