Half-quadratic algorithm for ℓp-ℓq problems with applications to TV-ℓ1 image restoration and compressive sensing

Raymond H. Chan*, Hai Xia Liang

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

38 Citations (Scopus)

Abstract

In this paper, we consider the ℓp-ℓq minimization problem with 0<p,q≤2. The problem has been studied extensively in image restoration and compressive sensing. In the paper, we first extend the half-quadratic algorithm from ℓ1-norm to ℓp-norm with 0<p<2. Based on this, we develop a half-quadratic algorithm to solve the ℓp-ℓq problem. We prove that our algorithm is indeed a majorize-minimize approach. From that we derive some convergence results of our algorithm, e.g. the objective function value is monotonically decreasing and convergent. We apply the proposed approach to TV-ℓ1 image restoration and compressive sensing in magnetic resonance (MR) imaging applications. The numerical results show that our algorithm is fast and efficient in restoring blurred images that are corrupted by impulse noise, and also in reconstructing MR images from very few k-space data.

Original languageEnglish
Title of host publicationEfficient Algorithms for Global Optimization Methods in Computer Vision - International Dagstuhl Seminar, Revised Selected Papers
PublisherSpringer Verlag
Pages78-103
Number of pages26
ISBN (Print)9783642547737
DOIs
Publication statusPublished - 2014
Event2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision - Dagstuhl Castle, Germany
Duration: 20 Nov 201125 Nov 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8293 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision
Country/TerritoryGermany
CityDagstuhl Castle
Period20/11/1125/11/11

Keywords

  • Compressive sensing
  • Half-quadratic
  • Impulse noise
  • Magnetic resonance imaging
  • Majorize-minimize algorithm

Cite this