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
N1 - Funding Information:
We acknowledge helpful discussions with Sven Leyffer and Todd Munson. This work was supported by funding through the Biological Systems Science Division, Office of Biological and Environmental Research, Office of Science, U.S. Department of Energy, under Contract DE-AC02-06CH11357.
Publisher Copyright:
© 2018 IEEE.
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
AN - SCOPUS:85062910747
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
T2 - 25th IEEE International Conference on Image Processing, ICIP 2018
Y2 - 7 October 2018 through 10 October 2018
ER -