Abstract

Image reconstruction gives rise to some challenging large-scale constrained optimization problems. We consider a convex minimization problem with nonnegativity constraints that arises in astronomical imaging. To solve this problem, we use an efficient hybrid gradient projection–reduced Newton (active-set) method. By “reduced Newton,” we mean that we take Newton steps only in the inactive variables. Owing to the large size of our problem, we compute approximate reduced Newton steps by using the conjugate gradient (CG) iteration. We introduce a limited-memory, quasi-Newton preconditioner that speeds up CG convergence. A numerical comparison is presented that demonstrates the effectiveness of this preconditioner.

© 2004 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. L. Snyder, A. M. Hammoud, R. L. White, “Image recovery from data acquired with a charge-coupled-device camera,” J. Opt. Soc. Am. A 10, 1014–1023 (1993).
    [CrossRef] [PubMed]
  2. L. B. Lucy, “An iterative technique for the rectification of observed distributions,” Astron. J. 79, 745–754 (1974).
    [CrossRef]
  3. W. H. Richardson, “Bayesian-based iterative method of image restoration,” J. Opt. Soc. Am. 62, 55–59 (1972).
    [CrossRef]
  4. J. Nagy, Z. Strakos, “Enforcing nonnegativity in image reconstruction algorithms,” in Mathematical Modeling, Estimation, and Imaging, D. C. Wilson, H. D. Tagare, F. L. Bookstein, F. J. Preteux, E. R. Dougherty, eds., Proc. SPIE4121, 182–190 (2000).
    [CrossRef]
  5. J. M. Bardsley, C. R. Vogel, “A nonnnegatively constrained convex programming method for image reconstruction,” SIAM J. Sci. Comput. (USA) 25(4), (2003).
  6. J. J. Moré, G. Toraldo, “On the solution of large quadratic programming problems with bound constraints,” SIAM J. Optim. 1, 93–113 (1991).
    [CrossRef]
  7. D. P. Bertsekas, “On the Goldstein–Levitin–Poljak gradient projection method,” IEEE Trans. Autom. Control 21, 174–184 (1976).
    [CrossRef]
  8. C. T. Kelley, Iterative Methods for Optimization (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1999).
  9. J. Nocedal, S. J. Wright, Numerical Optimization (Springer-Verlag, New York, 1999).
  10. J. L. Barlow, G. Toraldo, “The effect of diagonal scaling on projected gradient methods for bound constrained quadratic programming problems,” Optim. Methods Software 5, 235–245 (1995).
    [CrossRef]
  11. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, New York, 1996).
  12. J. W. Goodman, Statistical Optics (Wiley, New York, 1985).
  13. C. R. Vogel, Computational Methods for Inverse Problems (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2002).
  14. W. Feller, An Introduction to Probability Theory and Its Applications (Wiley, New York, 1971).
  15. J. Nocedal, J. L. Morales, “Automatic preconditioning by limited memory quasi-Newton updating,” SIAM J. Optim. 10, 1079–1096 (2000).
    [CrossRef]
  16. D. P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,” SIAM J. Control Optim. 20, 221–246 (1982).
    [CrossRef]
  17. R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
    [CrossRef]
  18. C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
    [CrossRef]

2003 (1)

J. M. Bardsley, C. R. Vogel, “A nonnnegatively constrained convex programming method for image reconstruction,” SIAM J. Sci. Comput. (USA) 25(4), (2003).

2000 (1)

J. Nocedal, J. L. Morales, “Automatic preconditioning by limited memory quasi-Newton updating,” SIAM J. Optim. 10, 1079–1096 (2000).
[CrossRef]

1997 (1)

C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
[CrossRef]

1995 (2)

J. L. Barlow, G. Toraldo, “The effect of diagonal scaling on projected gradient methods for bound constrained quadratic programming problems,” Optim. Methods Software 5, 235–245 (1995).
[CrossRef]

R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
[CrossRef]

1993 (1)

1991 (1)

J. J. Moré, G. Toraldo, “On the solution of large quadratic programming problems with bound constraints,” SIAM J. Optim. 1, 93–113 (1991).
[CrossRef]

1982 (1)

D. P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,” SIAM J. Control Optim. 20, 221–246 (1982).
[CrossRef]

1976 (1)

D. P. Bertsekas, “On the Goldstein–Levitin–Poljak gradient projection method,” IEEE Trans. Autom. Control 21, 174–184 (1976).
[CrossRef]

1974 (1)

L. B. Lucy, “An iterative technique for the rectification of observed distributions,” Astron. J. 79, 745–754 (1974).
[CrossRef]

1972 (1)

Bardsley, J. M.

J. M. Bardsley, C. R. Vogel, “A nonnnegatively constrained convex programming method for image reconstruction,” SIAM J. Sci. Comput. (USA) 25(4), (2003).

Barlow, J. L.

J. L. Barlow, G. Toraldo, “The effect of diagonal scaling on projected gradient methods for bound constrained quadratic programming problems,” Optim. Methods Software 5, 235–245 (1995).
[CrossRef]

Bertsekas, D. P.

D. P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,” SIAM J. Control Optim. 20, 221–246 (1982).
[CrossRef]

D. P. Bertsekas, “On the Goldstein–Levitin–Poljak gradient projection method,” IEEE Trans. Autom. Control 21, 174–184 (1976).
[CrossRef]

Byrd, R. H.

C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
[CrossRef]

R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
[CrossRef]

Feller, W.

W. Feller, An Introduction to Probability Theory and Its Applications (Wiley, New York, 1971).

Goodman, J. W.

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, New York, 1996).

J. W. Goodman, Statistical Optics (Wiley, New York, 1985).

Hammoud, A. M.

Kelley, C. T.

C. T. Kelley, Iterative Methods for Optimization (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1999).

Lu, P.

R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
[CrossRef]

Lucy, L. B.

L. B. Lucy, “An iterative technique for the rectification of observed distributions,” Astron. J. 79, 745–754 (1974).
[CrossRef]

Morales, J. L.

J. Nocedal, J. L. Morales, “Automatic preconditioning by limited memory quasi-Newton updating,” SIAM J. Optim. 10, 1079–1096 (2000).
[CrossRef]

Moré, J. J.

J. J. Moré, G. Toraldo, “On the solution of large quadratic programming problems with bound constraints,” SIAM J. Optim. 1, 93–113 (1991).
[CrossRef]

Nagy, J.

J. Nagy, Z. Strakos, “Enforcing nonnegativity in image reconstruction algorithms,” in Mathematical Modeling, Estimation, and Imaging, D. C. Wilson, H. D. Tagare, F. L. Bookstein, F. J. Preteux, E. R. Dougherty, eds., Proc. SPIE4121, 182–190 (2000).
[CrossRef]

Nocedal, J.

J. Nocedal, J. L. Morales, “Automatic preconditioning by limited memory quasi-Newton updating,” SIAM J. Optim. 10, 1079–1096 (2000).
[CrossRef]

C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
[CrossRef]

R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
[CrossRef]

J. Nocedal, S. J. Wright, Numerical Optimization (Springer-Verlag, New York, 1999).

Richardson, W. H.

Snyder, D. L.

Strakos, Z.

J. Nagy, Z. Strakos, “Enforcing nonnegativity in image reconstruction algorithms,” in Mathematical Modeling, Estimation, and Imaging, D. C. Wilson, H. D. Tagare, F. L. Bookstein, F. J. Preteux, E. R. Dougherty, eds., Proc. SPIE4121, 182–190 (2000).
[CrossRef]

Toraldo, G.

J. L. Barlow, G. Toraldo, “The effect of diagonal scaling on projected gradient methods for bound constrained quadratic programming problems,” Optim. Methods Software 5, 235–245 (1995).
[CrossRef]

J. J. Moré, G. Toraldo, “On the solution of large quadratic programming problems with bound constraints,” SIAM J. Optim. 1, 93–113 (1991).
[CrossRef]

Vogel, C. R.

J. M. Bardsley, C. R. Vogel, “A nonnnegatively constrained convex programming method for image reconstruction,” SIAM J. Sci. Comput. (USA) 25(4), (2003).

C. R. Vogel, Computational Methods for Inverse Problems (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2002).

White, R. L.

Wright, S. J.

J. Nocedal, S. J. Wright, Numerical Optimization (Springer-Verlag, New York, 1999).

Zhu, C.

C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
[CrossRef]

ACM Trans. Math. Softw. (1)

C. Zhu, R. H. Byrd, J. Nocedal, “L-BFGS-B: FORTRAN subroutines for large scale bound constrained optimization,” ACM Trans. Math. Softw. 23, 550–560 (1997).
[CrossRef]

Astron. J. (1)

L. B. Lucy, “An iterative technique for the rectification of observed distributions,” Astron. J. 79, 745–754 (1974).
[CrossRef]

IEEE Trans. Autom. Control (1)

D. P. Bertsekas, “On the Goldstein–Levitin–Poljak gradient projection method,” IEEE Trans. Autom. Control 21, 174–184 (1976).
[CrossRef]

J. Opt. Soc. Am. (1)

J. Opt. Soc. Am. A (1)

Optim. Methods Software (1)

J. L. Barlow, G. Toraldo, “The effect of diagonal scaling on projected gradient methods for bound constrained quadratic programming problems,” Optim. Methods Software 5, 235–245 (1995).
[CrossRef]

SIAM J. Control Optim. (1)

D. P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,” SIAM J. Control Optim. 20, 221–246 (1982).
[CrossRef]

SIAM J. Optim. (2)

J. J. Moré, G. Toraldo, “On the solution of large quadratic programming problems with bound constraints,” SIAM J. Optim. 1, 93–113 (1991).
[CrossRef]

J. Nocedal, J. L. Morales, “Automatic preconditioning by limited memory quasi-Newton updating,” SIAM J. Optim. 10, 1079–1096 (2000).
[CrossRef]

SIAM J. Sci. Comput. (USA) (2)

R. H. Byrd, P. Lu, J. Nocedal, “A limited memory algorithm for bound constrained optimization,” SIAM J. Sci. Comput. (USA) 16, 1190–1208 (1995).
[CrossRef]

J. M. Bardsley, C. R. Vogel, “A nonnnegatively constrained convex programming method for image reconstruction,” SIAM J. Sci. Comput. (USA) 25(4), (2003).

Other (7)

J. Nagy, Z. Strakos, “Enforcing nonnegativity in image reconstruction algorithms,” in Mathematical Modeling, Estimation, and Imaging, D. C. Wilson, H. D. Tagare, F. L. Bookstein, F. J. Preteux, E. R. Dougherty, eds., Proc. SPIE4121, 182–190 (2000).
[CrossRef]

J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, New York, 1996).

J. W. Goodman, Statistical Optics (Wiley, New York, 1985).

C. R. Vogel, Computational Methods for Inverse Problems (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2002).

W. Feller, An Introduction to Probability Theory and Its Applications (Wiley, New York, 1971).

C. T. Kelley, Iterative Methods for Optimization (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1999).

J. Nocedal, S. J. Wright, Numerical Optimization (Springer-Verlag, New York, 1999).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1
Fig. 1

Mesh plots of the upper-left 64 × 64 pixels of the binary star and satellite true images.

Fig. 2
Fig. 2

Mesh plots of the upper-left 64 × 64 pixels of the binary star and satellite data with 1% noise.

Fig. 3
Fig. 3

Reconstructions. Top, mesh plot of the upper-left 64 × 64 pixels of the reconstruction corresponding to the binary star data with 1% noise; bottom, mesh plot of the upper-left 64 × 64 pixels of the reconstruction corresponding to the satellite data with 1% noise.

Fig. 4
Fig. 4

Relative solution error versus FFTs for binary star data. Horizontal axis, cumulative FFTs; vertical axis, relative solution error on a logarithmic scale. Top plot, convergence results for 1% noise; bottom plot, convergence results for 10% noise. Solid curve, GPRNCG with preconditioning; dashed–dotted curve, GPRNCG without preconditioning; dashed curve, LBFGS-B.

Fig. 5
Fig. 5

Relative solution error versus FFTs for satellite data. Horizontal axis, cumulative FFTs; vertical axis, relative solution error on a logarithmic scale. Top plot, convergence results for 1% noise; bottom plot, convergence results for 10% noise. Solid curve, GPRNCG with preconditioning; dashed–dotted curve, GPRNCG without preconditioning; dashed curve, LBFGS-B.

Equations (52)

Equations on this page are rendered with MathJax. Learn more.

d = S f true + η ,
min f 0   J ( f ) ,
d i , j = s ( x i - x ,   y j - y ) f true ( x ,   y ) d x d y + η i , j ,
d i , j = i j s i - i , j - j [ f true ] i , j + η i , j ,
1 i n x , 1 j n y .
S f 0 ,
f 0 .
J ( f ) =l ( S f ;   d ) + α 2 f T f .
l ( S f ,   d ) = 1 2 S f - d 2 .
d i = n obj ( i ) + n 0 ( i ) + g ( i ) , i = 1 , , N .
l ( S f ,   d ) = i = 1 N ( [ S f ] i + β + σ 2 ) - i = 1 N ( d i + σ 2 ) log ( [ S f ] i + β + σ 2 ) .
grad   J ( f ) = S T ( ( S f + β - d ) . / ( S f + β + σ 2 ) ) + α f ,
Hess   J ( f ) = S T W ( f ) S + α I ,
w i = d i + σ 2 ( [ S f ] i + β + σ 2 ) 2 .
Ω = { f R N | f 0 } .
A ( f ) = { i | f i = 0 } .
[ grad R   J ( f ) ] i = J ( f ) f i , i I ( f ) 0 , i A ( f )
[ Hess R   J ( f ) ] ij = 2 J ( f ) f i f j , if i I ( f ) or j I ( f ) δ ij , otherwise .
[ D I ( f ) ] ii = 1 , i I ( f ) 0 , i A ( f ) .
grad R   J ( f ) = D I ( f ) grad   J ( f ) ,
Hess R   J ( f ) = D I ( f ) Hess   J ( f ) D I ( f ) + D A ( f ) ,
Hess R   J ( f k GP ) p = - grad R   J ( f k GP ) .
j = GP max
J ( f k , j - 1 GP ) - J ( f k , j GP ) γ GP max { J ( f k , i - 1 GP ) - J ( f k , i GP ) | i = 1 , , j - 1 } ,
j = CG max
q k ( p j - 1 ) - q k ( p j ) γ CG max { q k ( p i - 1 ) - q k ( p i ) | i = 1 , , j - 1 } ,
q k ( p ) = J ( f k GP ) + grad R   J ( f k GP ) ,   p + 1 2 Hess R   J ( f k GP ) p ,   p .
Hess   J ( f k GP ) p = grad   J ( f k GP )
s k , j GP f k , j + 1 GP - f k , j GP , j = 0 , , N k ,
y k , j GP grad   J ( f k , j + 1 GP ) - grad   J ( f k , j GP ) ,
j = 0 , , N k .
s k CG f k + 1 - f k GP ,
y k CG grad   J ( f k + 1 ) - grad   J ( f k GP ) .
{ s l } l = 0 N total = { s 0 , 0 GP , , s 0 , N 0 GP ,   s 0 CG ,   s 1 , 0 GP , , s k , N k GP } ,
H l + 1 = V l T H l V l + ρ l s l s l T ,
ρ l = 1 y l T s l , V l = 1 - ρ l y l s l T .
H l + 1 = ( V l T V l - m + 1 T ) H l + 1 0 ( V l - m + 1 V l ) + ρ l - m + 1 ( V l T V l - m + 2 T ) s l - m + 1 s l - m + 1 T × ( V l - m + 2 V l ) + ρ l - m + 2 ( V l T V l - m + 3 T ) s l - m + 2 s l - m + 2 T × ( V l - m + 3 V l ) + + ρ l s l s l T .
α i = ρ i s i T p ;
p = p - α i y i ;
β i = ρ i y i T r ;
r = r + ( α i - β i ) s i ;
s l ,   y l = s l ,   grad   J ( f l ) - grad   J ( f l ) = s l ,   Hess   J ( f l + t s l ) s l > 0 .
D I ( f k GP ) M k D I ( f k GP ) + D A ( f k GP )
D I ( f k GP ) M k - 1 D I ( f k GP ) + D A ( f k GP )
{ s ^ l ,   y ^ l } , l = N total - m + 1 , , N total ,
s ^ l = D I ( f k GP ) s l , y ^ l = D I ( f k GP ) y l .
s ^ l ,   y ^ l > 0
s ^ l ,   y ^ l = D I ( f l + 1 ) s l ,   D I ( f l + 1 ) Hess   J ( f l + 1 + t s l ) s l ,
= D I ( f l + 1 ) s l ,   D I ( f l + 1 ) Hess   J ( f l + 1 + t s l ) × D I ( f l + 1 ) s l + D I ( f l + 1 ) s l ,   D I ( f l + 1 ) Hess   J ( f l + 1 + τ s l ) D A ( f l + 1 ) s l .
D I ( f l + 1 ) s l ,   D I ( f l + 1 ) Hess   J ( f l + 1 + t s l ) D I ( f l + 1 ) s l > 0 .
η S f true = . 01 ,
f k - f α f α

Metrics