BKSVD: Bayesian K-SVD Using Fast Variational Inference
Recent work in signal processing in general and image processing in particular deals with sparse representation related problems. Two such problems are of paramount importance: an overriding need for designing a well-suited overcomplete dictionary containing a redundant set of atoms –i.e., basis signals– and how to find a sparse representation of a given signal with respect to the chosen dictionary. Dictionary learning techniques, among which we find the popular K-Singular Value Decomposition (K-SVD) algorithm, tackle these problems by adapting a dictionary to a set of training data. A common drawback of such techniques is the need for parameter-tuning. In order to overcome this limitation, we propose a fully-automated Bayesian method that takes into account the uncertainty of the estimates and produces a sparse representation of the data without prior information on the number of non-zeros in each representation vector. We follow a Bayesian approach that uses a three-tiered hierarchical prior to enforce sparsity on the representations and develop an efficient variational inference framework that reduces computational complexity. Furthermore, we describe a greedy approach that speeds up the whole process. Finally, we present experimental results that show superior performance on two different applications with real images: denoising and inpainting.
Dictionary Learning & Sparse Representation
In Dictionary Learning we want to find the sparse representation x of a signal y such that y = Dx + n, where n accounts for the noise in the observation. We are interested in finding the best dictionary D (in terms of sparsity) and the sparse representations of each signal. The figures shows how each signal can be represented as a (sparse) linear combination of dictionary elements, named atoms.
Hierarchical Bayesian Model
The figure describes the Bayesian model used in this work. Sparsity is enforced by the hyperprior hierarchy on X.
Denoising results for a corrupted image with Gaussian noise (σ = 20).
(a) Noisy image. (b) BKSVD (c) K-SVD (d) BFPA  (e) SnS 
Inpainting results for a corrupted image with 75% missing pixels in a random pattern.
(a) BKSVD (b) K-SVD (c) BFPA  (d) SnS 
The MATLAB code of the proposed method can be downloaded here.
 M. Zhou, H. Chen, J. Paisley, L. Ren, L. Li, Z. Xing, D. Dunson, G. Sapiro, and L. Carin, “Nonparametric Bayesian dictionary learning for analysis of noisy and incomplete images,“ IEEE Transactions on Image Processing, 2012.
 M. Lázaro-Gredilla and M. K. Titsias, “Spike and slab variational inference for multi-task and multiple kernel learning,” Advances in neural information processing systems, 2011.
The programs are granted free of charge for research and education purposes only. Scientific results produced using the software provided shall acknowledge the use of the BKSVD implementation provided by us. If you plan to use it for non-scientific purposes, don't hesitate to contact us.
Because the programs are licensed free of charge, there is no warranty for the program, to the extent permitted by applicable law except when otherwise stated in writing the copyright holders and/or other parties provide the program "as is" without warranty of any kind, either expressed or implied, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose. The entire risk as to the quality and performance of the program is with you. Should the program prove defective, you assume the cost of all necessary servicing, repair or correction.
In no event unless required by applicable law or agreed to in writing will any copyright holder, or any other party who may modify and/or redistribute the program, be liable to you for damages, including any general, special, incidental or consequential damages arising out of the use or inability to use the program (including but not limited to loss of data or data being rendered inaccurate or losses sustained by you or third parties or a failure of the program to operate with any other programs), even if such holder or other party has been advised of the possibility of such damages.