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

Raymond H. CHAN; Hai Xia LIANG

doi:10.1007/978-3-642-54774-4_4

Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing

^*Corresponding author for this work

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

40 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 ℓ₁-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-ℓ₁ 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 language	English
Title of host publication	Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers
Editors	Andrés BRUHN, Thomas POCK, Xue-Cheng TAI
Publisher	Springer Berlin Heidelberg
Pages	78-103
Number of pages	26
ISBN (Electronic)	9783642547744
ISBN (Print)	9783642547737
DOIs	https://doi.org/10.1007/978-3-642-54774-4_4
Publication status	Published - 2014
Externally published	Yes
Event	2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision - Dagstuhl Castle, Germany Duration: 20 Nov 2011 → 25 Nov 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	8293
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision
Country/Territory	Germany
City	Dagstuhl Castle
Period	20/11/11 → 25/11/11

Funding

The research was supported in part by HKRGC Grant CUHK 400510 and CUHK DAG 2060408. The authors would like to thank the financial support of project in Nanyang Technological University.

Keywords

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

Access to Document

10.1007/978-3-642-54774-4_4

Cite this

CHAN, R. H., & LIANG, H. X. (2014). Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. In A. BRUHN, T. POCK, & X.-C. TAI (Eds.), Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers (pp. 78-103). (Lecture Notes in Computer Science; Vol. 8293). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-54774-4_4

CHAN, Raymond H. ; LIANG, Hai Xia. / Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers. editor / Andrés BRUHN ; Thomas POCK ; Xue-Cheng TAI. Springer Berlin Heidelberg, 2014. pp. 78-103 (Lecture Notes in Computer Science).

@inproceedings{2fbc0e05766243368c6ad48f84dd1557,

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

abstract = "In this paper, we consider the ℓp-ℓq minimization problem with 01-norm to ℓp-norm with 0p-ℓ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.",

keywords = "Compressive sensing, Half-quadratic, Impulse noise, Magnetic resonance imaging, Majorize-minimize algorithm",

author = "CHAN, {Raymond H.} and LIANG, {Hai Xia}",

year = "2014",

doi = "10.1007/978-3-642-54774-4_4",

language = "English",

isbn = "9783642547737",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "78--103",

editor = "Andr{\'e}s BRUHN and Thomas POCK and Xue-Cheng TAI",

booktitle = "Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers",

note = "2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision ; Conference date: 20-11-2011 Through 25-11-2011",

}

CHAN, RH & LIANG, HX 2014, Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. in A BRUHN, T POCK & X-C TAI (eds), Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8293, Springer Berlin Heidelberg, pp. 78-103, 2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision, Dagstuhl Castle, Germany, 20/11/11. https://doi.org/10.1007/978-3-642-54774-4_4

Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. / CHAN, Raymond H.; LIANG, Hai Xia.
Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers. ed. / Andrés BRUHN; Thomas POCK; Xue-Cheng TAI. Springer Berlin Heidelberg, 2014. p. 78-103 (Lecture Notes in Computer Science; Vol. 8293).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

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

AU - CHAN, Raymond H.

AU - LIANG, Hai Xia

PY - 2014

Y1 - 2014

N2 - In this paper, we consider the ℓp-ℓq minimization problem with 01-norm to ℓp-norm with 0p-ℓ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.

AB - In this paper, we consider the ℓp-ℓq minimization problem with 01-norm to ℓp-norm with 0p-ℓ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.

KW - Compressive sensing

KW - Half-quadratic

KW - Impulse noise

KW - Magnetic resonance imaging

KW - Majorize-minimize algorithm

UR - http://www.scopus.com/inward/record.url?scp=84958545646&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-54774-4_4

DO - 10.1007/978-3-642-54774-4_4

M3 - Conference paper (refereed)

AN - SCOPUS:84958545646

SN - 9783642547737

T3 - Lecture Notes in Computer Science

SP - 78

EP - 103

BT - Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers

A2 - BRUHN, Andrés

A2 - POCK, Thomas

A2 - TAI, Xue-Cheng

PB - Springer Berlin Heidelberg

T2 - 2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision

Y2 - 20 November 2011 through 25 November 2011

ER -

CHAN RH, LIANG HX. Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. In BRUHN A, POCK T, TAI XC, editors, Efficient Algorithms for Global Optimization Methods in Computer Vision: International Dagstuhl Seminar, Revised Selected Papers. Springer Berlin Heidelberg. 2014. p. 78-103. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-54774-4_4