Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration

Haoying Fu; Michael K. Ng; Mila Nikolova; Jesse Barlow; Wai Ki Ching

doi:10.1007/11424925_88

Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration

Haoying Fu, Michael K. Ng, Mila Nikolova, Jesse Barlow, Wai Ki Ching

Department of Mathematics

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

3 Citations (Scopus)

Abstract

Image restoration problems are often solved by finding the minimizer of a suitable objective function. Usually this function consists of a data-fitting term and a regularization term. For the least squares solution, both the data-fitting and the regularization terms are in the ℓ2 norm. In this paper, we consider the least absolute deviation (LAD) solution and the least mixed norm (LMN) solution. For the LAD solution, both the data-fitting and the regularization terms are in the ℓ1 norm. For the LMN solution, the regularization term is in the ℓ1 norm but the data-fitting term is in the ℓ2 norm. The LAD and the LMN solutions are formulated as the solutions of a linear and a quadratic programming problems respectively, and solved by interior point methods. At each iteration of the interior point method, a structured linear system must be solved. The preconditioned conjugate gradient method with factorized sparse inverse preconditioners is employed to such structured inner systems. Experimental results are used to demonstrate the effectiveness of our approach. We also show the quality of the restored images using the minimization of ℓ1 norm/mixed ℓ1 and ℓ2 norms is better than that using ℓ2 norm approach.

Original language	English
Title of host publication	Computational Science and Its Applications - ICCSA 2005
Subtitle of host publication	International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV
Publisher	Springer Berlin Heidelberg
Pages	843-851
Number of pages	9
Edition	1st
ISBN (Electronic)	9783540323099
ISBN (Print)	9783540258636
DOIs	https://doi.org/10.1007/11424925_88
Publication status	Published - 27 Apr 2005
Event	International Conference on Computational Science and Its Applications - ICCSA 2005 - , Singapore Duration: 9 May 2005 → 12 May 2005 https://link.springer.com/book/10.1007/b136266 https://link.springer.com/book/10.1007/b136269 https://link.springer.com/book/10.1007/b136271 https://link.springer.com/book/10.1007/b136278

Publication series

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

Name	Theoretical Computer Science and General Issues

Name	ICCSA: International Conference on Computational Science and Its Applications

Conference

Conference	International Conference on Computational Science and Its Applications - ICCSA 2005
Country/Territory	Singapore
Period	9/05/05 → 12/05/05
Internet address	https://link.springer.com/book/10.1007/b136266 https://link.springer.com/book/10.1007/b136269 https://link.springer.com/book/10.1007/b136271 https://link.springer.com/book/10.1007/b136278

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

Image restoration
Interior point method
Least absolute deviation
Least mixed norm

Access to Document

10.1007/11424925_88

Cite this

Fu, H., Ng, M. K., Nikolova, M., Barlow, J., & Ching, W. K. (2005). Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration. In Computational Science and Its Applications - ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV (1st ed., pp. 843-851). (Lecture Notes in Computer Science; Vol. 3483), (Theoretical Computer Science and General Issues), (ICCSA: International Conference on Computational Science and Its Applications). Springer Berlin Heidelberg. https://doi.org/10.1007/11424925_88

Fu, Haoying ; Ng, Michael K. ; Nikolova, Mila et al. / Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration. Computational Science and Its Applications - ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV. 1st. ed. Springer Berlin Heidelberg, 2005. pp. 843-851 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (ICCSA: International Conference on Computational Science and Its Applications).

@inproceedings{6663f9f744624ae289edb9077e45e452,

title = "Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration",

abstract = "Image restoration problems are often solved by finding the minimizer of a suitable objective function. Usually this function consists of a data-fitting term and a regularization term. For the least squares solution, both the data-fitting and the regularization terms are in the ℓ2 norm. In this paper, we consider the least absolute deviation (LAD) solution and the least mixed norm (LMN) solution. For the LAD solution, both the data-fitting and the regularization terms are in the ℓ1 norm. For the LMN solution, the regularization term is in the ℓ1 norm but the data-fitting term is in the ℓ2 norm. The LAD and the LMN solutions are formulated as the solutions of a linear and a quadratic programming problems respectively, and solved by interior point methods. At each iteration of the interior point method, a structured linear system must be solved. The preconditioned conjugate gradient method with factorized sparse inverse preconditioners is employed to such structured inner systems. Experimental results are used to demonstrate the effectiveness of our approach. We also show the quality of the restored images using the minimization of ℓ1 norm/mixed ℓ1 and ℓ2 norms is better than that using ℓ2 norm approach.",

keywords = "Image restoration, Interior point method, Least absolute deviation, Least mixed norm",

author = "Haoying Fu and Ng, {Michael K.} and Mila Nikolova and Jesse Barlow and Ching, {Wai Ki}",

note = "Funding Information: The work has been supported by a grant from the PROCORE – France/Hong Kong Joint Research Scheme sponsored by the Research Grants Council of Hong Kong and the Consulate General of France in Hong Kong F-HK 30/04T, and RGC grant nos. HKU7130/02P, HKU7046/03P, HKU7035/04P, and 10205541. Publisher copyright: {\textcopyright} 2005 Springer-Verlag Berlin Heidelberg; International Conference on Computational Science and Its Applications - ICCSA 2005 ; Conference date: 09-05-2005 Through 12-05-2005",

year = "2005",

month = apr,

day = "27",

doi = "10.1007/11424925_88",

language = "English",

isbn = "9783540258636",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "843--851",

booktitle = "Computational Science and Its Applications - ICCSA 2005",

edition = "1st",

url = "https://link.springer.com/book/10.1007/b136266, https://link.springer.com/book/10.1007/b136269, https://link.springer.com/book/10.1007/b136271, https://link.springer.com/book/10.1007/b136278",

}

Fu, H, Ng, MK, Nikolova, M, Barlow, J & Ching, WK 2005, Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration. in Computational Science and Its Applications - ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV. 1st edn, Lecture Notes in Computer Science, vol. 3483, Theoretical Computer Science and General Issues, ICCSA: International Conference on Computational Science and Its Applications, Springer Berlin Heidelberg, pp. 843-851, International Conference on Computational Science and Its Applications - ICCSA 2005, Singapore, 9/05/05. https://doi.org/10.1007/11424925_88

Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration. / Fu, Haoying; Ng, Michael K.; Nikolova, Mila et al.
Computational Science and Its Applications - ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV. 1st. ed. Springer Berlin Heidelberg, 2005. p. 843-851 (Lecture Notes in Computer Science; Vol. 3483), (Theoretical Computer Science and General Issues), (ICCSA: International Conference on Computational Science and Its Applications).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration

AU - Fu, Haoying

AU - Ng, Michael K.

AU - Nikolova, Mila

AU - Barlow, Jesse

AU - Ching, Wai Ki

N1 - Funding Information: The work has been supported by a grant from the PROCORE – France/Hong Kong Joint Research Scheme sponsored by the Research Grants Council of Hong Kong and the Consulate General of France in Hong Kong F-HK 30/04T, and RGC grant nos. HKU7130/02P, HKU7046/03P, HKU7035/04P, and 10205541. Publisher copyright: © 2005 Springer-Verlag Berlin Heidelberg

PY - 2005/4/27

Y1 - 2005/4/27

N2 - Image restoration problems are often solved by finding the minimizer of a suitable objective function. Usually this function consists of a data-fitting term and a regularization term. For the least squares solution, both the data-fitting and the regularization terms are in the ℓ2 norm. In this paper, we consider the least absolute deviation (LAD) solution and the least mixed norm (LMN) solution. For the LAD solution, both the data-fitting and the regularization terms are in the ℓ1 norm. For the LMN solution, the regularization term is in the ℓ1 norm but the data-fitting term is in the ℓ2 norm. The LAD and the LMN solutions are formulated as the solutions of a linear and a quadratic programming problems respectively, and solved by interior point methods. At each iteration of the interior point method, a structured linear system must be solved. The preconditioned conjugate gradient method with factorized sparse inverse preconditioners is employed to such structured inner systems. Experimental results are used to demonstrate the effectiveness of our approach. We also show the quality of the restored images using the minimization of ℓ1 norm/mixed ℓ1 and ℓ2 norms is better than that using ℓ2 norm approach.

AB - Image restoration problems are often solved by finding the minimizer of a suitable objective function. Usually this function consists of a data-fitting term and a regularization term. For the least squares solution, both the data-fitting and the regularization terms are in the ℓ2 norm. In this paper, we consider the least absolute deviation (LAD) solution and the least mixed norm (LMN) solution. For the LAD solution, both the data-fitting and the regularization terms are in the ℓ1 norm. For the LMN solution, the regularization term is in the ℓ1 norm but the data-fitting term is in the ℓ2 norm. The LAD and the LMN solutions are formulated as the solutions of a linear and a quadratic programming problems respectively, and solved by interior point methods. At each iteration of the interior point method, a structured linear system must be solved. The preconditioned conjugate gradient method with factorized sparse inverse preconditioners is employed to such structured inner systems. Experimental results are used to demonstrate the effectiveness of our approach. We also show the quality of the restored images using the minimization of ℓ1 norm/mixed ℓ1 and ℓ2 norms is better than that using ℓ2 norm approach.

KW - Image restoration

KW - Interior point method

KW - Least absolute deviation

KW - Least mixed norm

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

U2 - 10.1007/11424925_88

DO - 10.1007/11424925_88

M3 - Conference proceeding

AN - SCOPUS:24944486480

SN - 9783540258636

T3 - Lecture Notes in Computer Science

SP - 843

EP - 851

BT - Computational Science and Its Applications - ICCSA 2005

PB - Springer Berlin Heidelberg

T2 - International Conference on Computational Science and Its Applications - ICCSA 2005

Y2 - 9 May 2005 through 12 May 2005

ER -

Fu H, Ng MK, Nikolova M, Barlow J, Ching WK. Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration. In Computational Science and Its Applications - ICCSA 2005: International Conference, Singapore, May 9-12, 2005, Proceedings, Part IV. 1st ed. Springer Berlin Heidelberg. 2005. p. 843-851. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (ICCSA: International Conference on Computational Science and Its Applications). doi: 10.1007/11424925_88

Fast Algorithms for l1 Norm/Mixed l1 and l2 Norms for Image Restoration

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this