Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

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.

up
0 users have voted:

Paper Details

Authors:
Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld
Submitted On:
7 October 2018 - 5:05pm
Short Link:
Type:
Poster
Event:
Presenter's Name:
Xiang Huang
Paper Code:
ICIP18001
Document Year:
2018
Cite

Document Files

2018_Huang_IPAlgorithm_ICIP_Poster.pdf

(28 downloads)

Subscribe

[1] Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld, "An Interior Point Method for Nonnegative Sparse Signal Reconstruction", IEEE SigPort, 2018. [Online]. Available: http://sigport.org/3603. Accessed: Dec. 12, 2018.
@article{3603-18,
url = {http://sigport.org/3603},
author = {Xiang Huang; Kuan He; Seunghwan Yoo; Oliver Cossairt; Aggelos Katsaggelos; Nicola Ferrier; and Mark Hereld },
publisher = {IEEE SigPort},
title = {An Interior Point Method for Nonnegative Sparse Signal Reconstruction},
year = {2018} }
TY - EJOUR
T1 - An Interior Point Method for Nonnegative Sparse Signal Reconstruction
AU - Xiang Huang; Kuan He; Seunghwan Yoo; Oliver Cossairt; Aggelos Katsaggelos; Nicola Ferrier; and Mark Hereld
PY - 2018
PB - IEEE SigPort
UR - http://sigport.org/3603
ER -
Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld. (2018). An Interior Point Method for Nonnegative Sparse Signal Reconstruction. IEEE SigPort. http://sigport.org/3603
Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld, 2018. An Interior Point Method for Nonnegative Sparse Signal Reconstruction. Available at: http://sigport.org/3603.
Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld. (2018). "An Interior Point Method for Nonnegative Sparse Signal Reconstruction." Web.
1. Xiang Huang, Kuan He, Seunghwan Yoo, Oliver Cossairt, Aggelos Katsaggelos, Nicola Ferrier, and Mark Hereld. An Interior Point Method for Nonnegative Sparse Signal Reconstruction [Internet]. IEEE SigPort; 2018. Available from : http://sigport.org/3603