Skip to main content
SpringerLink
Log in

Learning Big (Image) Data via Coresets for Dictionaries

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Signal and image processing have seen an explosion of interest in the last few years in a new form of signal/image characterization via the concept of sparsity with respect to a dictionary. An active field of research is dictionary learning: the representation of a given large set of vectors (e.g. signals or images) as linear combinations of only few vectors (patterns). To further reduce the size of the representation, the combinations are usually required to be sparse, i.e., each signal is a linear combination of only a small number of patterns.

This paper suggests a new computational approach to the problem of dictionary learning, known in computational geometry as coresets. A coreset for dictionary learning is a small smart non-uniform sample from the input signals such that the quality of any given dictionary with respect to the input can be approximated via the coreset. In particular, the optimal dictionary for the input can be approximated by learning the coreset. Since the coreset is small, the learning is faster. Moreover, using merge-and-reduce, the coreset can be constructed for streaming signals that do not fit in memory and can also be computed in parallel.

We apply our coresets for dictionary learning of images using the K-SVD algorithm and bound their size and approximation error analytically. Our simulations demonstrate gain factors of up to 60 in computational time with the same, and even better, performance. We also demonstrate our ability to perform computations on larger patches and high-definition images, where the traditional approach breaks down.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Ackermann, M.R., Märtens, M., Raupach, C., Swierkot, K., Lammersen, C., Sohler, C.: Streamkm++: a clustering algorithm for data streams. ACM J. Exp. Algorithmics 4, 2 (2012)

    Google Scholar 

  2. Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606–635 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  3. Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximations via coresets. Comb. Comput. Geom. 52, 1–30 (2005). MSRI Publications

    MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  6. Aharon, M., Elad, M., Bruckstein, A.M.: K-SVD and its non-negative variant for dictionary design. In: Proceedings of the SPIE conference wavelets, vol. 5914, p. 591411 (2005)

    Google Scholar 

  7. Bentley, J.L., Saxe, J.B.: Decomposable searching problems I. Static-to-dynamic transformation* 1. J. Algorithms 1(4), 301–358 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cesar, R.M., Costa, L.F.: Shape Analysis and Classification. CRC Press, Boca Raton (2001)

    MATH  Google Scholar 

  9. Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: 12th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 642–651 (2001)

    Google Scholar 

  10. Clarkson, K.L.: Subgradient and sampling algorithms for l 1-regression. In: 16th Annu. ACM-SIAM Symp. on Discrete algorithms (SODA), pp. 257–266 (2005)

    Google Scholar 

  11. Dasgupta, A., Drineas, P., Harb, B., Kumar, R., Mahoney, M.W.: Sampling algorithms and coresets for ℓ p -regression. In: Proc. 19th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 932–941 (2008)

    Google Scholar 

  12. Deshpande, A., Vempala, S.: Adaptive sampling and fast low-rank matrix approximation. In: 10th Int. Workshop on Randomization and Computation (RANDOM), pp. 292–303 (2006)

    Google Scholar 

  13. Dryden, I.L., Mardia, K.V.: Statistical Shape Analysis. Wiley, San Diego (1998)

    MATH  Google Scholar 

  14. Elad, M., Aharon, M.: Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Image Process. 15(12), 3736–3745 (2006)

    Article  MathSciNet  Google Scholar 

  15. Feldman, D., Fiat, A., Kaplan, H., Nissim, K.: Private coresets. In: Proc. 41st Annu. ACM Symp. on Theory of Computing (STOC), pp. 361–370 (2009)

    Chapter  Google Scholar 

  16. Feldman, D., Fiat, A., Segev, D., Sharir, M.: Bi-criteria linear-time approximations for generalized k-mean/median/center. In: 23rd ACM Symp. on Computational Geometry (SOCG), pp. 19–26 (2007)

    Google Scholar 

  17. Feldman, D., Fiat, A., Sharir, M.: Coresets for weighted facilities and their applications. In: Proc. 47th IEEE Annu. Symp. on Foundations of Computer Science (FOCS), pp. 315–324 (2006)

    Google Scholar 

  18. Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proc. 41th Ann. ACM Symp. on Theory of Computing (STOC) (2010). Full version in arXiv:1106.1379

    Google Scholar 

  19. Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: 23rd ACM Symp. on Computational Geometry (SoCG), pp. 11–18 (2007)

    Google Scholar 

  20. Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proc. 23rd ACM Symp. on Computational Geometry (SoCG), pp. 11–18 (2007)

    Google Scholar 

  21. Feldman, D., Schulman, L.J.: Data reduction for weighted and outlier-resistant clustering. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1343–1354. SIAM, Philadelphia (2012)

    Google Scholar 

  22. Feldman, D., Faulkner, M., Krause, A.: Scalable training of mixture models via coresets. In: Proc. Neural Information Processing Systems (NIPS) (2011)

    Google Scholar 

  23. Frahling, G., Sohler, C.: A fast k-means implementation using coresets. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pp. 135–143. ACM, New York (2006)

    Chapter  Google Scholar 

  24. Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37(1), 3–19 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  25. Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: 36th Annu. ACM Symp. on Theory of Computing (STOC), pp. 291–300 (2004)

    Google Scholar 

  26. Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proc. 36th Annu. ACM Symp. on Theory of Computing (STOC), pp. 291–300 (2004)

    Google Scholar 

  27. Haussler, D.: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput. 100(1), 78–150 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kreutz-Delgado, K., Murray, J.F., Rao, B.D., Engan, K., Lee, T.W., Sejnowski, T.J.: Dictionary learning algorithms for sparse representation. Neural Comput. 15(2), 349–396 (2003)

    Article  MATH  Google Scholar 

  29. Langberg, M., Schulman, L.J.: Universal ε approximators for integrals. In: proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2010)

    Google Scholar 

  30. Lesage, S., Gribonval, R., Bimbot, F., Benaroya, L.: Learning unions of orthonormal bases with thresholded singular value decomposition. In: Acoustics, Speech, and Signal Processing. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’05), vol. 5. IEEE, New York (2005)

    Google Scholar 

  31. Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the sample complexity of learning. J. Comput. Syst. Sci. 62 (2001)

  32. Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the sample complexity of learning. In: Symp. on Discrete Algorithms, pp. 309–318 (2000)

    Google Scholar 

  33. Mulmuley, K.: Computational Geometry, an Introduction through Randomized Algorithms. Prentice Hall, New York (1993)

    MATH  Google Scholar 

  34. Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Signals, Systems and Computers. 1993 Conference Record of the Twenty-Seventh Asilomar Conference on, pp. 40–44. IEEE, New York (2002)

    Google Scholar 

  35. Rubinstein, R.: Ksvd-box v13. Technical report

  36. Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)

    MATH  Google Scholar 

  37. Shawe-Taylor, J., Bartlett, P.L., Williamson, R.C., Anthony, M.: Structural risk minimization over data-dependent hierarchies. IEEE Trans. Inf. Theory 44(5), 1926–1940 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  38. Shen, B., Hu, W., Zhang, Y., Zhang, Y.J.: Image inpainting via sparse representation. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2009), pp. 697–700. IEEE, New York (2009)

    Chapter  Google Scholar 

  39. Vainsencher, D., Mannor, S., Bruckstein, A.M.: The sample complexity of dictionary learning. Arxiv preprint (2010). arXiv:1011.5395

  40. Varadarajan, K., Xiao, X.: A near-linear algorithm for projective clustering integer points. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’12, pp. 1329–1342. SIAM, Philadelphia (2012)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CSAIL, MIT, Cambridge, MA, USA

    Dan Feldman

  2. Media Lab., MIT, Cambridge, MA, USA

    Micha Feigin

  3. Department of Applied Mathematics, Tel Aviv university, Tel Aviv, Israel

    Nir Sochen

Authors
  1. Dan Feldman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Micha Feigin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nir Sochen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dan Feldman.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Feldman, D., Feigin, M. & Sochen, N. Learning Big (Image) Data via Coresets for Dictionaries. J Math Imaging Vis 46, 276–291 (2013). https://doi.org/10.1007/s10851-013-0431-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-013-0431-x

Keywords

Search

Navigation