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

Raymond H. Chan^*, Hai Xia Liang

^*Corresponding author for this work

Department of Foundational Mathematics

Chinese University of Hong Kong

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › 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
Publisher	Springer Verlag
Pages	78-103
Number of pages	26
ISBN (Print)	9783642547737
DOIs	https://doi.org/10.1007/978-3-642-54774-4_4
Publication status	Published - 2014
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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8293 LNCS
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

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 Efficient Algorithms for Global Optimization Methods in Computer Vision - International Dagstuhl Seminar, Revised Selected Papers (pp. 78-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8293 LNCS). Springer Verlag. 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. Springer Verlag, 2014. pp. 78-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4f5252837ab445c184375ddd0a93a3e9,

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}",

note = "Funding Information: The research was supported in part by HKRGC Grant CUHK 400510 and CUHK DAG 2060408. Funding Information: The authors would like to thank the financial support of project in Nanyang Technological University.; 2011 International Dagstuhl Seminar 11471 on Efficient Algorithms for Global Optimization Methods in Computer Vision ; Conference date: 20-11-2011 Through 25-11-2011",

year = "2014",

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

language = "English",

isbn = "9783642547737",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "78--103",

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

}

Chan, RH & Liang, HX 2014, Half-quadratic algorithm for ℓ_p-ℓ_q problems with applications to TV-ℓ₁ image restoration and compressive sensing. in Efficient Algorithms for Global Optimization Methods in Computer Vision - International Dagstuhl Seminar, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8293 LNCS, Springer Verlag, 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. Springer Verlag, 2014. p. 78-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8293 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › 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

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

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 Proceeding

AN - SCOPUS:84958545646

SN - 9783642547737

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 103

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

PB - Springer Verlag

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 Efficient Algorithms for Global Optimization Methods in Computer Vision - International Dagstuhl Seminar, Revised Selected Papers. Springer Verlag. 2014. p. 78-103. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-54774-4_4