Structured Overcomplete Sparsifying Transform Learning with Convergence Guarantees and Applications

Bihan Wen, Saiprasad Ravishankar, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


In recent years, sparse signal modeling, especially using the synthesis model has been popular. Sparse coding in the synthesis model is however, NP-hard. Recently, interest has turned to the sparsifying transform model, for which sparse coding is cheap. However, natural images typically contain diverse textures that cannot be sparsified well by a single transform. Hence, in this work, we propose a union of sparsifying transforms model. Sparse coding in this model reduces to a form of clustering. The proposed model is also equivalent to a structured overcomplete sparsifying transform model with block cosparsity, dubbed OCTOBOS. The alternating algorithm introduced for learning such transforms involves simple closed-form solutions. A theoretical analysis provides a convergence guarantee for this algorithm. It is shown to be globally convergent to the set of partial minimizers of the non-convex learning problem. We also show that under certain conditions, the algorithm converges to the set of stationary points of the overall objective. When applied to images, the algorithm learns a collection of well-conditioned square transforms, and a good clustering of patches or textures. The resulting sparse representations for the images are much better than those obtained with a single learned transform, or with analytical transforms. We show the promising performance of the proposed approach in image denoising, which compares quite favorably with approaches involving a single learned square transform or an overcomplete synthesis dictionary, or gaussian mixture models. The proposed denoising method is also faster than the synthesis dictionary based approach.

Original languageEnglish (US)
Pages (from-to)137-167
Number of pages31
JournalInternational Journal of Computer Vision
Issue number2-3
StatePublished - Sep 22 2015


  • Clustering
  • Convergence guarantees
  • Dictionary learning
  • Image denoising
  • Image representation
  • Machine learning
  • Overcomplete representation
  • Sparse representation
  • Sparsifying transform learning

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Structured Overcomplete Sparsifying Transform Learning with Convergence Guarantees and Applications'. Together they form a unique fingerprint.

Cite this