Single-Pass K-SVD for Efficient Dictionary Learning | Circuits, Systems, and Signal Processing Skip to main content
Springer Nature Link
Log in

Single-Pass K-SVD for Efficient Dictionary Learning

  • Short Paper
  • Published:
Circuits, Systems, and Signal Processing Aims and scope Submit manuscript

Abstract

Sparse representation has been widely used in machine learning, signal processing and communications. K-SVD, which generalizes k-means clustering, is one of the most famous algorithms for sparse representation and dictionary learning. K-SVD is an iterative method that alternates between encoding the data sparsely by using the current dictionary and updating the dictionary based on the sparsely represented data. In this paper, we introduce a single-pass K-SVD method. In this method, the previous input data are first summarized as a condensed representation of weighted samples. Then, we developed a weighted K-SVD algorithm to learn a dictionary from the union of this representation and the newly input data. Experimental results show that our approach can approximate K-SVD’s performance well by consuming considerably less storage resource.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. The K-SVD Matlab software available at: http://www.cs.technion.ac.il/~elad/software/

  2. V. Abolghasemi, S. Ferdowsi, S. Sanei, Sparse multichannel source separation using incoherent K-SVD method, in Statistical Signal Processing Workshop (2011)

    Google Scholar 

  3. M. Aharon, M. Elad, A. Bruckstein, K-SVD and its non-negative variant for dictionary design, in Proceedings of the SPIE Conference Wavelets (2005)

    Google Scholar 

  4. M. Aharon, M. Elad, A. Bruckstein, K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54(11), 4311–4322 (2006)

    Article  Google Scholar 

  5. D. Arthur, S. Vassilvitskii, k-Means++: the advantages of careful seeding, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007)

    Google Scholar 

  6. C. Bishop, Pattern Recognition and Machine Learning (2006)

    MATH  Google Scholar 

  7. P.S. Bradley, U. Fayyad, C. Reina, Scaling clustering algorithms to large databases, in Knowledge Discovery and Data Mining (1998), pp. 9–15

    Google Scholar 

  8. A. Bruckstein, D. Donoho, M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1), 34 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  9. E. Candes, T. Tao, Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  10. S. Chen, D. Donoho, M. Saunders, Atomic decomposition by basis pursuit, in Society for Industrial and Applied Mathematics Review (2001), pp. 129–159

    Google Scholar 

  11. W. Dai, T. Xu, W. Wang, Dictionary learning and update based on simultaneous codeword optimization (SIMCO), in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (2012)

    Google Scholar 

  12. F. Farnstrom, J. Lewis, C. Elkan, Scalability for clustering algorithms revisited. ACM SIGKDD Explor. Newsl. 2(1), 51–57 (2000)

    Article  Google Scholar 

  13. X. He, R. Song, W. Zhu, Optimal pilot pattern design for compressed sensing-based sparse channel estimation in OFDM systems, in Circuits, Systems, and Signal Processing (2012), pp. 1–17

    Google Scholar 

  14. P. Hore, L.O. Hall, D.B. Goldgof, Single pass fuzzy C means, in IEEE International Conference on Fuzzy Systems (2007)

    Google Scholar 

  15. M. Hyder, K. Mahata, An improved smoothed approximation algorithm for sparse representation. IEEE Trans. Signal Process. 58(4), 2194–2205 (2010)

    Article  MathSciNet  Google Scholar 

  16. Z. Jiang, Z. Lin, L. Davis, Learning a discriminative dictionary for sparse coding via label consistent K-SVD, in IEEE Conference on Computer Vision and Pattern Recognition (2011)

    Google Scholar 

  17. S. Lloyd, Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  18. J. Mairal, F. Bach, J. Ponce, G. Sapiro, Online dictionary learning for sparse coding, in Proceedings of the 26th Annual International Conference on Machine Learning (2009)

    Google Scholar 

  19. J. Mairal, F. Bach, J. Ponce, G. Sapiro, Online learning for matrix factorization and sparse coding. J. Mach. Learn. Res. 11, 19–60 (2010)

    MATH  MathSciNet  Google Scholar 

  20. J. Mairal, M. Elad, G. Sapiro, Sparse learned representations for image restoration, in The 4th World Conference of the IASC and 6th Conference of the Asian Regional Section of the IASC on Computational Statistics and Data Analysis (2008)

    Google Scholar 

  21. V. Patel, Y. Shi, P. Thompson, A. Toga, K-SVD for HARDI denoising, in IEEE International Symposium on Biomedical Imaging: From Nano to Macro (2011)

    Google Scholar 

  22. Y. Pati, R. Rezaiifar, P. Krishnaprasad, Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, in Asilomar Conference on Signals, Systems and Computers (1993)

    Google Scholar 

  23. R. Rubinstein, M. Zibulevsky, M. Elad, Double sparsity: learning sparse dictionaries for sparse signal approximation. IEEE Trans. Signal Process. 58(3), 1553–1564 (2010)

    Article  MathSciNet  Google Scholar 

  24. Q. Zhang, B. Li, Discriminative K-SVD for dictionary learning in face recognition, in IEEE Conference on Computer Vision and Pattern Recognition (2010)

    Google Scholar 

  25. Y. Zhao, X. Zhuang, H. Wang, Z. Dai, Model-based multichannel compressive sampling with ultra-low sampling rate, in Circuits, Systems, and Signal Processing (2012), pp. 1–12

    Google Scholar 

Download references

Acknowledgements

This work was supported in part by the National Science Council, Taiwan, under the grants NSC101-2221-E-001-011.

Author information

Authors and Affiliations

  1. Institute of Information Science, Academia Sinica, Taipei, Taiwan

    Kuang-Yu Chang, Chu-Song Chen & Yi-Ping Hung

  2. Department of Computer Science & Information Engineering, National Taiwan University, Taipei, Taiwan

    Kuang-Yu Chang & Yi-Ping Hung

  3. Research Center for Information Technology Innovation, Academia Sinica, Taipei, Taiwan

    Cheng-Fu Lin & Chu-Song Chen

Authors
  1. Kuang-Yu Chang
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Cheng-Fu Lin
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Chu-Song Chen
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Yi-Ping Hung
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Chu-Song Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chang, KY., Lin, CF., Chen, CS. et al. Single-Pass K-SVD for Efficient Dictionary Learning. Circuits Syst Signal Process 33, 309–320 (2014). https://doi.org/10.1007/s00034-013-9630-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00034-013-9630-3

Keywords