An interior point method for nonnegative sparse signal reconstruction

Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Strides Cossairt, Aggelos K Katsaggelos, Nicola Ferrier, Mark Hereld

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We present a primal-dual interior point method (IPM) with a novel preconditioner to solve the ℓ 1 -norm regularized least square problem for nonnegative sparse signal reconstruction. IPM is a second-order method that uses both gradient and Hessian information to compute effective search directions and achieve super-linear convergence rates. It therefore requires many fewer iterations than first-order methods such as iterative shrinkage/thresholding algorithms (ISTA) that only achieve sub-linear convergence rates. However, each iteration of IPM is more expensive than in ISTA because it needs to evaluate an inverse of a Hessian matrix to compute the Newton direction. We propose to approximate each Hessian matrix by a diagonal matrix plus a rank-one matrix. This approximation matrix is easily invertible using the Sherman-Morrison formula, and is used as a novel preconditioner in a preconditioned conjugate gradient method to compute a truncated Newton direction. We demonstrate the efficiency of our algorithm in compressive 3D volumetric image reconstruction. Numerical experiments show favorable results of our method in comparison with previous interior point based and iterative shrinkage/thresholding based algorithms.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings
PublisherIEEE Computer Society
Pages1193-1197
Number of pages5
ISBN (Electronic)9781479970612
DOIs
StatePublished - Aug 29 2018
Event25th IEEE International Conference on Image Processing, ICIP 2018 - Athens, Greece
Duration: Oct 7 2018Oct 10 2018

Publication series

NameProceedings - International Conference on Image Processing, ICIP
ISSN (Print)1522-4880

Conference

Conference25th IEEE International Conference on Image Processing, ICIP 2018
CountryGreece
CityAthens
Period10/7/1810/10/18

Fingerprint

Signal reconstruction
Conjugate gradient method
Image reconstruction
Experiments

Keywords

  • 3d volumetric image reconstruction
  • Compressive sensing
  • Nonnegative sparse
  • Norm regularized optimization
  • Primal-dual preconditioned interior point method

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Signal Processing

Cite this

Huang, X., He, K., Yoo, S., Cossairt, O. S., Katsaggelos, A. K., Ferrier, N., & Hereld, M. (2018). An interior point method for nonnegative sparse signal reconstruction. In 2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings (pp. 1193-1197). [8451710] (Proceedings - International Conference on Image Processing, ICIP). IEEE Computer Society. https://doi.org/10.1109/ICIP.2018.8451710
Huang, Xiang ; He, Kuan ; Yoo, Seunghwan ; Cossairt, Oliver Strides ; Katsaggelos, Aggelos K ; Ferrier, Nicola ; Hereld, Mark. / An interior point method for nonnegative sparse signal reconstruction. 2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings. IEEE Computer Society, 2018. pp. 1193-1197 (Proceedings - International Conference on Image Processing, ICIP).
@inproceedings{d86c1bceb10b45a498e306f8fd76aad9,
title = "An interior point method for nonnegative sparse signal reconstruction",
abstract = "We present a primal-dual interior point method (IPM) with a novel preconditioner to solve the ℓ 1 -norm regularized least square problem for nonnegative sparse signal reconstruction. IPM is a second-order method that uses both gradient and Hessian information to compute effective search directions and achieve super-linear convergence rates. It therefore requires many fewer iterations than first-order methods such as iterative shrinkage/thresholding algorithms (ISTA) that only achieve sub-linear convergence rates. However, each iteration of IPM is more expensive than in ISTA because it needs to evaluate an inverse of a Hessian matrix to compute the Newton direction. We propose to approximate each Hessian matrix by a diagonal matrix plus a rank-one matrix. This approximation matrix is easily invertible using the Sherman-Morrison formula, and is used as a novel preconditioner in a preconditioned conjugate gradient method to compute a truncated Newton direction. We demonstrate the efficiency of our algorithm in compressive 3D volumetric image reconstruction. Numerical experiments show favorable results of our method in comparison with previous interior point based and iterative shrinkage/thresholding based algorithms.",
keywords = "3d volumetric image reconstruction, Compressive sensing, Nonnegative sparse, Norm regularized optimization, Primal-dual preconditioned interior point method",
author = "Xiang Huang and Kuan He and Seunghwan Yoo and Cossairt, {Oliver Strides} and Katsaggelos, {Aggelos K} and Nicola Ferrier and Mark Hereld",
year = "2018",
month = "8",
day = "29",
doi = "10.1109/ICIP.2018.8451710",
language = "English (US)",
series = "Proceedings - International Conference on Image Processing, ICIP",
publisher = "IEEE Computer Society",
pages = "1193--1197",
booktitle = "2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings",
address = "United States",

}

Huang, X, He, K, Yoo, S, Cossairt, OS, Katsaggelos, AK, Ferrier, N & Hereld, M 2018, An interior point method for nonnegative sparse signal reconstruction. in 2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings., 8451710, Proceedings - International Conference on Image Processing, ICIP, IEEE Computer Society, pp. 1193-1197, 25th IEEE International Conference on Image Processing, ICIP 2018, Athens, Greece, 10/7/18. https://doi.org/10.1109/ICIP.2018.8451710

An interior point method for nonnegative sparse signal reconstruction. / Huang, Xiang; He, Kuan; Yoo, Seunghwan; Cossairt, Oliver Strides; Katsaggelos, Aggelos K; Ferrier, Nicola; Hereld, Mark.

2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings. IEEE Computer Society, 2018. p. 1193-1197 8451710 (Proceedings - International Conference on Image Processing, ICIP).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An interior point method for nonnegative sparse signal reconstruction

AU - Huang, Xiang

AU - He, Kuan

AU - Yoo, Seunghwan

AU - Cossairt, Oliver Strides

AU - Katsaggelos, Aggelos K

AU - Ferrier, Nicola

AU - Hereld, Mark

PY - 2018/8/29

Y1 - 2018/8/29

N2 - We present a primal-dual interior point method (IPM) with a novel preconditioner to solve the ℓ 1 -norm regularized least square problem for nonnegative sparse signal reconstruction. IPM is a second-order method that uses both gradient and Hessian information to compute effective search directions and achieve super-linear convergence rates. It therefore requires many fewer iterations than first-order methods such as iterative shrinkage/thresholding algorithms (ISTA) that only achieve sub-linear convergence rates. However, each iteration of IPM is more expensive than in ISTA because it needs to evaluate an inverse of a Hessian matrix to compute the Newton direction. We propose to approximate each Hessian matrix by a diagonal matrix plus a rank-one matrix. This approximation matrix is easily invertible using the Sherman-Morrison formula, and is used as a novel preconditioner in a preconditioned conjugate gradient method to compute a truncated Newton direction. We demonstrate the efficiency of our algorithm in compressive 3D volumetric image reconstruction. Numerical experiments show favorable results of our method in comparison with previous interior point based and iterative shrinkage/thresholding based algorithms.

AB - We present a primal-dual interior point method (IPM) with a novel preconditioner to solve the ℓ 1 -norm regularized least square problem for nonnegative sparse signal reconstruction. IPM is a second-order method that uses both gradient and Hessian information to compute effective search directions and achieve super-linear convergence rates. It therefore requires many fewer iterations than first-order methods such as iterative shrinkage/thresholding algorithms (ISTA) that only achieve sub-linear convergence rates. However, each iteration of IPM is more expensive than in ISTA because it needs to evaluate an inverse of a Hessian matrix to compute the Newton direction. We propose to approximate each Hessian matrix by a diagonal matrix plus a rank-one matrix. This approximation matrix is easily invertible using the Sherman-Morrison formula, and is used as a novel preconditioner in a preconditioned conjugate gradient method to compute a truncated Newton direction. We demonstrate the efficiency of our algorithm in compressive 3D volumetric image reconstruction. Numerical experiments show favorable results of our method in comparison with previous interior point based and iterative shrinkage/thresholding based algorithms.

KW - 3d volumetric image reconstruction

KW - Compressive sensing

KW - Nonnegative sparse

KW - Norm regularized optimization

KW - Primal-dual preconditioned interior point method

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

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

U2 - 10.1109/ICIP.2018.8451710

DO - 10.1109/ICIP.2018.8451710

M3 - Conference contribution

T3 - Proceedings - International Conference on Image Processing, ICIP

SP - 1193

EP - 1197

BT - 2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings

PB - IEEE Computer Society

ER -

Huang X, He K, Yoo S, Cossairt OS, Katsaggelos AK, Ferrier N et al. An interior point method for nonnegative sparse signal reconstruction. In 2018 IEEE International Conference on Image Processing, ICIP 2018 - Proceedings. IEEE Computer Society. 2018. p. 1193-1197. 8451710. (Proceedings - International Conference on Image Processing, ICIP). https://doi.org/10.1109/ICIP.2018.8451710