Efficient Dictionary Learning with Sparseness-Enforcing Projections

详细信息    查看全文

• 作者：Markus Thom ; Matthias Rapp ; Günther Palm
• 关键词：Sparse coding ; Sparse representations ; Dictionary learning ; Explicit sparseness constraints ; Sparseness ; enforcing projections
• 刊名：International Journal of Computer Vision
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：114
• 期：2-3
• 页码：168-194
• 全文大小：2,097 KB
• 参考文献：Aharon, M., Elad, M., & Bruckstein, A. (2006). K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11), 4311-322.CrossRef
  Bauer, F., & Memisevic, R. (2013). Feature grouping from spatially constrained multiplicative interaction. In Proceedings of the International Conference on Learning Representations. arXiv:-301.-391v3 .
  Bell, A. J., & Sejnowski, T. J. (1997). The "independent components" of natural scenes are edge filters. Vision Research, 37(23), 3327-338.CrossRef
  Bertsekas, D. P. (1999). Nonlinear programming (2nd ed.). Belmont: Athena Scientific.MATH
  Bishop, C. M. (1995). Neural networks for pattern recognition. Oxford: Clarendon Press.
  Blackford, L. S., et al. (2002). An updated set of basic linear algebra subprograms (BLAS). ACM Transactions on Mathematical Software, 28(2), 135-51.CrossRef MathSciNet
  Bottou, L., & LeCun, Y. (2004). Large scale online learning. In Advances in Neural Information Processing Systems (Vol. 16, pp. 217-24).
  Bredies, K., & Lorenz, D. A. (2008). Linear convergence of iterative soft-thresholding. Journal of Fourier Analysis and Applications, 14(5-), 813-37.CrossRef MathSciNet MATH
  Coates, A., & Ng, A. Y. (2011). The importance of encoding versus training with sparse coding and vector quantization. In Proceedings of the International Conference on Machine Learning (pp. 921-28).
  Deutsch, F. (2001). Best approximation in inner product spaces. New York: Springer.CrossRef MATH
  Dong, W., Zhang, L., Shi, G., & Wu, X. (2011). Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization. IEEE Transactions on Image Processing, 20(7), 1838-857.CrossRef MathSciNet
  Donoho, D. L. (1995). De-noising by soft-thresholding. IEEE Transactions on Information Theory, 41(3), 613-27.CrossRef MathSciNet MATH
  Donoho, D. L. (2006). For most large underdetermined systems of linear equations the minimal \(\ell _1\) -norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6), 797-29.CrossRef MathSciNet MATH
  Duarte-Carvajalino, J. M., & Sapiro, G. (2009). Learning to sense sparse signals: Simultaneous sensing matrix and sparsifying dictionary optimization. IEEE Transactions on Image Processing, 18(7), 1395-408.CrossRef MathSciNet
  Eckart, C., & Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1(3), 211-18.CrossRef MATH
  Elad, M. (2006). Why simple shrinkage is still relevant for redundant representations? IEEE Transactions on Information Theory, 52(12), 5559-569.CrossRef MathSciNet MATH
  Foucart, S., & Rauhut, H. (2013). Mathematical introduction to compressive sensing. New York: Birkh?user.CrossRef MATH
  Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Alken, P., et al. (2009). GNU scientific library reference manual (3rd ed.). Bristol: Network Theory Ltd.
  Gharavi-Alkhansari, M., & Huang, T. S. (1998). A fast orthogonal matching pursuit algorithm. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (Vol. III, pp. 1389-392).
  Goldberg, D. (1991). What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys, 23(1), 5-48.CrossRef
  Hawe, S., Seibert, M., & Kleinsteuber, M. (2013). Separable dictionary learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 438-45).
  Hoggar, S. G. (2006). Mathematics of digital images: Creation, compression, restoration, recognition. Cambridge: Cambridge University Press.CrossRef
  Horev, I., Bryt, O., & Rubinstein, R. (2012). Adaptive image compression using sparse dictionaries. In Proceedings of the International Conference on Systems, Signals and Image Processing (pp. 592-95).
  Hoyer, P. O. (2004). Non-negative matrix factorization with sparseness constraints. Journal of Machine Learning Research, 5, 1457-1469.MathSciNet MATH
  Hoyer, P. O., & Hyv?rinen, A. (2000). Independent component analysis applied to feature extraction from colour and stereo images. Network: Computation in Neural Systems, 11(3), 191-10.
  Hubel, D. H., & Wiesel, T. N. (1959). Receptive fields of single neurones in the cat’s striate cortex. Journal of Physiology, 148(3), 574-91.CrossRef
  Hurley, N., & Rickard, S. (2009). Comparing measures of sparsity. IEEE Transactions on Information Theory, 55(10), 4723-741.CrossRef MathSciNet
  Hyv?rinen, A. (1999). Sparse code shrinkage: Denoising of nongaussian data by maximum likelihood estimation. Neural Computation, 11(7), 1739-768.CrossRef
  Hyv?rinen, A., & Hoyer, P. O. (2000). Emergence of phase- and shift-invariant features by decomposition of natural images into independent feature subspaces. Neural Computation, 12(7), 1705-720.CrossRef
  Hyv?rinen, A., Hoyer, P. O., & Inki, M. (2001). Topographic independent component
• 作者单位：Markus Thom (1)
  Matthias Rapp (1)
  Günther Palm (2)
  
  1. driveU / Institute of Measurement, Control and Microtechnology, Ulm University, 89081, Ulm, Germany
  2. Institute of Neural Information Processing, Ulm University, 89081, Ulm, Germany
  
• 刊物类别：Computer Science
• 刊物主题：Computer Imaging, Vision, Pattern Recognition and Graphics
  Artificial Intelligence and Robotics
  Image Processing and Computer Vision
  Pattern Recognition
  
• 出版者：Springer Netherlands
• ISSN：1573-1405

文摘

Learning dictionaries suitable for sparse coding instead of using engineered bases has proven effective in a variety of image processing tasks. This paper studies the optimization of dictionaries on image data where the representation is enforced to be explicitly sparse with respect to a smooth, normalized sparseness measure. This involves the computation of Euclidean projections onto level sets of the sparseness measure. While previous algorithms for this optimization problem had at least quasi-linear time complexity, here the first algorithm with linear time complexity and constant space complexity is proposed. The key for this is the mathematically rigorous derivation of a characterization of the projection’s result based on a soft-shrinkage function. This theory is applied in an original algorithm called Easy Dictionary Learning (EZDL), which learns dictionaries with a simple and fast-to-compute Hebbian-like learning rule. The new algorithm is efficient, expressive and particularly simple to implement. It is demonstrated that despite its simplicity, the proposed learning algorithm is able to generate a rich variety of dictionaries, in particular a topographic organization of atoms or separable atoms. Further, the dictionaries are as expressive as those of benchmark learning algorithms in terms of the reproduction quality on entire images, and result in an equivalent denoising performance. EZDL learns approximately 30 % faster than the already very efficient Online Dictionary Learning algorithm, and is therefore eligible for rapid data set analysis and problems with vast quantities of learning samples. Keywords Sparse coding Sparse representations Dictionary learning Explicit sparseness constraints Sparseness-enforcing projections