Online dictionary learning for sparse coding

Online dictionary learning for sparse coding

Summary:
Sparse coding是利用一組從dictionary中找出的basis去組成目標之向量，而這篇paper的重點在於如何有效率的去建構出這個dictionary。作者提出了一個給dictionary training用的online optimization algorithm，這個建立在stochastic approximation上的方法，可以在有幾個billion個training sample的dataset中也達到不錯的效果。

作者有提到這篇paper的contribution如下:
1. 將dictionary learning problem轉成一個optimization of a smooth nonconvex objective function over a convex set的問題。
2. 提出了一個iterative online algorithm去有效率地解決問題。利用的是在每個step去極小化surrogate function。
3. 證明了其演算法相較於傳統的方式快上許多，特別式也在一個1200萬畫素的圖片上去作處理，達到很好的效果。

作者還提出了一些方法去對他提出的演算法作optimization的動作，如下:
1. 針對已經處理過的部分去作捨棄，因為在文中的algorithm1中有提到A、B兩個矩陣都會帶有著過往的資訊alpha，但是如果今天在一個很大的dataset中，有一個x是之前已經處理過的，又再出現一次的時候，就可以把他之前算過的alpha給相減掉。
2. 利用一次處理多組的sample，而不是一次只對一組sample的alpha值去對A和B兩個矩陣作更新，也可以達到加速的效果。
3. 當dictionary中出現不常使用的element時，就在optimization的過程之中將其刪除，也可以達到更好的performance。

作者也在文中提出了一些前提假設來去證明這個方法的收斂性，有興趣的朋友們可以去細看那些推導的過程(我個人是覺得有點難通透…)。

最後作者還作了一些實驗來證明其方法的效果，可以看出在速度上比batch的方式快上許多。

Comment:
之前在另外一門課(數位視訊技術)的期末project中，曾經利用sparse coding去實作image super-resolution，那時候在dictionary training的時候就花了很多時間去跑，而實際上在跑後面的sparse coding也是很花時間，雖然說這是一個較新的領域，但是實際上在應用的時候，可能還是會卡在computation量太大的困擾上，導致比較不實用的情形。