A fast patch-dictionary method for whole image recovery

Yangyang Xu, Wotao Yin

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Many dictionary based methods in image processing use dictionary to represent all the patches of an image. We address the open issue of modeling an image by its overlapping patches: due to overlapping, there are a large number of patches, and to recover these patches, one must determine an excessive number of their dictionary coefficients. With very few exceptions, this issue has limited the applications of image-patch methods to the ``local'' tasks such as denoising, inpainting, cartoon-texture decomposition, super-resolution, and image deblurring, where one can process a few patches at a time. Our focus is the global imaging tasks such as compressive sensing and medical image recovery, where the whole image is encoded together in each measurement, making it either impossible or very ineffective to update a few patches at a time. Our strategy is to divide the sparse recovery into multiple subproblems, each of which handles a subset of non-overlapping patches, and then the results of the subproblems are averaged to yield the final recovery. This simple strategy is surprisingly effective in terms of both quality and speed. In addition, we accelerate computation of the learned dictionary by applying a recent block proximal-gradient method, which not only has a lower per-iteration complexity but also takes fewer iterations to converge, compared to the current state-of-the-art. We also establish that our algorithm globally converges to a stationary point. Numerical results on synthetic data demonstrate that our algorithm can recover a more faithful dictionary than two state-of-the-art methods. Combining our image-recovery and dictionary-learning methods, we numerically simulate image inpainting, compressive sensing recovery, and deblurring. Our recovery is more faithful than those by a total variation method and a method based on overlapping patches. Our Matlab code is competitive in terms of both speed and quality.

Original languageEnglish (US)
Pages (from-to)563-583
Number of pages21
JournalInverse Problems and Imaging
Issue number2
StatePublished - May 2016

Bibliographical note

Funding Information:
Y. Xu is supported by NSF grant ECCS-1028790. W. Yin is partially supported by NSF grants DMS-0748839 and DMS-1317602, and ARO/ARL MURI grant FA9550-10-1-0567.

Publisher Copyright:
© 2016 American Institute of Mathematical Sciences.


  • Dictionary learning
  • Non-convex optimization
  • Non-overlapping patches
  • Sparse representation
  • Whole-image recovery


Dive into the research topics of 'A fast patch-dictionary method for whole image recovery'. Together they form a unique fingerprint.

Cite this