Structured Overcomplete Sparsifying Transform Learning with Convergence Guarantees and Applications

Bihan Wen

doi:10.1007/s11263-014-0761-1

2014-10-19

120

PRE

Bihan Wen *

Saiprasad Ravishankar

Yoram Bresler

DOI：10.1007/s11263-014-0761-1

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Sparsifying transform learning

Dictionary learning

Convergence guarantees

Overcomplete representation

Clustering

Image representation

Sparse representation

Image denoising

Machine learning