calculate svd in sliding windows

Hi,

I have a large matrix and I need to calculate the svd of a sliding window inside the matrix. That is: at every position, a svd is applied for the portion of the matrix included in the sliding window. There are a lot of overlap between the window's positions.

Currently, I am calculating this in a loop and treat each svd independently. This gives the right answer but need a lot of time. My gut feeling is since there are a lot of overlap between one window position to another, there are a lot of redundancy in the computation.

Any suggestions on how to speedup such a program? Any suggestions will be appreciated.

Bo

[John D'Errico]

Sorry. But not much chance of doing this efficiently based on any kind of update. There is no rank 1 update scheme that I know of for the SVD.

[Bo]

Thanks.

Any maybe approximation? if accuracy can be slightly compromised...

[John D'Errico]

I see no approximation that would make sense here. Though, I suppose one could do a QR, then use the QRUPDATE tools to slide that around the array. Finally, then compute the SVD of just R on each of those QR factorizations. The SVD on just an upper triangular matrix MIGHT be somewhat faster than the overall SVD. Since I have no idea what size the sliding arrays are, I can't really do much of a test.

In the end, I sincerely doubt it would be of much gain, and I would bet that in the end it will take more time overall given all of these steps.

Another option is to use the parallel computing toolbox to compute these SVDs. You will get a speedup based on how many cores you can throw at the problem. This is far more likely to result in a significant gain.

[Joshua Carmichael]

I had an similar question, and found this paper:

https://hal.inria.fr/hal-00945196/document

I think it provides an algorithm in which a sliding rectangular window (or mask) truncates an NxP multichannel data stream to the upper MxP rows, where M << N (for example). I think Bo is interested in computing, at each index that moves this mask "down" a successive row, the SVD of the masked matrix that is MxP rows in dimension. I have not coded up this algorithm, but it does not appear difficult from the documention in a table that is within the paper. Dave Harris also implemented an efficient computation of a subspace detector that uses the SVD in a 2008 paper here:

https://core.ac.uk/download/pdf/208094185.pdf

This digital signal detector performs SVD decomposition in a moving window over a seismic data stream.