Semi-Soft GoDec: >4 times faster, auto-determined k

Here is a good news of GoDec (pertaining to our ICML 2011 paper):

Semi-Soft GoDec is released. Different from the ordinary GoDec which imposes hard threshholding to both the singular values of the low-rank part L and the entries of the sparse part S, Semi-Soft GoDec adopts soft thresholding to the entries of S. This change brings two key advantages:

1) the parameter k in constraint “card(S)<=k” is now can be automatically determined by the soft-threshold \tau, thus avoids the situation when k is chosen too large and some part of noise G is leaked into S.

This is some kind of solution to the question from some readers of GoDec, i.e., how to determine r and k? We prefer the hard constraint to the rank of L because a controllable rank can significantly reduce the time cost, in addition, the upper bound of the rank r is not hard to determine in most applications. The rest problem is how to choose a good k. If k is selected in a safe range then it will not affect the result, but a k far from the correct value is possible to induce leaks between S and G, which is annoying sometimes. We found soft threholding is a good and natural solution to this problem. While the error is not increased, the time cost is reduced.

2) the time cost is substantially smaller than the ordinary GoDec, for example, the background modeling experiments can be accomplished with a speed 4 times faster then ordinary GoDec, which means almost all the videos shown in our ICML paper can be processed in less than 10 seconds, while the error is kept the same or even smaller.

This GoDec variant will be included in our journal version, the MatLab code of Semi-Soft GoDec is now available on GoDec website for download. Enjoy it!

About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in Tianyi's work and tagged , , , , , , , . Bookmark the permalink.

2 Responses to Semi-Soft GoDec: >4 times faster, auto-determined k

  1. Gunnar says:

    Thanks for having your code available online, however for the semi-soft godec code the function wthresh is undefined.
    Just wanted to let you know…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s