Incremental singular value decomposition of incomplete data
View Patent ↗A method models data values acquired by measuring a natural phenomena. Samples are acquired of the natural phenomena, each sample is arranged as a vector c of the data values. Some of the data values may be missing. The vectors c are decomposed into five matrices, respectively, a subspace U pxr , singular values s rxl , an encoding V qxr , a subspace rotation U′ rxr , an encoding transform V′ rxr , where p indicates the number of discrete data values in each sample, q is a number of samples, and r is a rank of a decomposition of the data values. The five matrices can then be multiplied according to UU′diag(s)V′ T V T to obtain a best linear approximation of the natural phenomena for any value of r less than both p and q, where T is a matrix transpose operator.
1. A computer implemented method for modeling data values acquired by measuring a real-world phenomenon, comprising the steps of:
measuring a natural phenomenon to acquire a plurality of samples of the natural phenomenon, in which the samples are in a form of an extremely sparse array of consumer-product preference scores;
arranging each sample as a vector c of discrete data values in a matrix M stored in a memory of a computer system;
decomposing the plurality of vectors c of the matrix M into five matrices, respectively, a subspace U pxr , singular values s rxl , an encoding V qxr , a subspace rotation U′ rxr , and an encoding transform V′ rxr , where p indicates the number of the discrete data values in each sample, q is a number of the samples, and r is a rank of a decomposition of the discrete data values;
multiplying the five matrices UU′ diag(s)V′ T V T obtain a best linear approximation of the real-world phenomenon for any value of the rank r less than both p and q, and where T is a matrix transpose operator; and
predicting missing consumer-product preference scores using the best linear approximation in a collaborative filtering application.
2. The method of claim 1 wherein the data samples are incomplete.
3. The method of claim 1 wherein the decomposition is incrementally updated one vector c at the time.
4. The method of claim 1 further comprising:
normalizing a first vector c to obtain the subspace U and a length of the subspace U;
setting the singular values s to a length of the vector C; and
setting the encoding V, the subspace rotation U′, and the encoding transform V′ T all to one to initialize the decomposition.
5. The method of claim 4 , further comprising, for each next vector:
projecting each next vector c onto the subspace U to obtain a location L of the vector c in the subspace U;
unprojecting the location L and subtracting the unprojected location L from the original vector c to obtain a remainder p of the vector outside the subspace, and a length k of the remainder p;
concatenating the location L and the length k of the remainder to the singular values s to obtain interim singular values s i ;
diagonalizing the interim singular values s i to obtain updated singular values matrix s′, and a left rotation s L and a right rotation s R of the updated singular values matrix s′;
multiplying the subspace rotation U′ by the left rotation s L to update the subspace rotation U′ and multiplying the encoding transform V′ by the right rotation s R to update the encoding transform V′ T ;
normalizing the remainder vector p to have unit length;
appending the normalized remainder p to the subspace matrix U;
multiplying a last row of the right rotation s R by a Moore-Penrose pseudo-inverse of the encoding transform V′ to obtain an encoding q of the next vector c; and
appending the encoding q encoding to the encoding matrix V to incrementally update the decomposition.
6. The method of claim 5 further comprising:
truncating all five matrices to force a decomposition of low dimensionality.
7. The method of claim 5 further comprising:
multiplying U by U′ and V by V′ to obtain a singular value decomposition.
8. The method of claim 7 further comprising:
swapping U and V and setting U′ and V′ to identity matrices to transpose the decomposition and enabling updating with data value rows instead of data value columns.
9. The method of claim 8 further comprising:
updating row-wise and column-wise to defer imputations of the missing data values until the imputations are well-constrained.
10. The method of claim 5 wherein the vector c has known data values and missing data values, and further comprising:
multiplying known data values of the vector c by the Moore-Penrose pseudo-inverse of a subset of rows of the subspace U to obtain the location L of the vector c in the subspace U when the vector c is incomplete.
11. The method of claim 10 further comprising:
weighting the pseudo-inverse with the singular values s to maximize a probability of the multiplication.
12. The method of claim 10 , wherein the unprojection of the location L is an imputation of the missing data values.
13. The method of claim 12 , wherein the data values are organized as a table of affinities, and the imputation is used to recommend pairs of items that have a high affinity.
14. The method of claim 1 , wherein the rank r is substantially less than p and q, r<<min(p, q).
15. The method of claim 1 , wherein the matrix M is extremely sparse.
16. The method of claim 1 , wherein the samples include colored noise.
17. The method of claim 1 , wherein the samples are non-stationary.
18. The method of claim 1 , wherein the approximation characterizes the natural phenomenon with a lowest possible rank.
19. The method of claim 1 , in which the samples are of an audio signal, and the approximation characterizes audio features of the audio signal.