Abstract

In this paper, we generalize the techniques of reverse-mode algorithmic differentiation to include elementary operations on multidimensional arrays of complex numbers. We explore the application of the algorithmic differentiation to phase retrieval error metrics and show that reverse-mode algorithmic differentiation provides a framework for straightforward calculation of gradients of complicated error metrics without resorting to finite differences or laborious symbolic differentiation.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. S. J. Wright and J. Nocedal, “Quasi-Newton methods,” in Numerical Optimization (Springer, 1999), Sect. 8.1.
  2. J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758–2769 (1982).
    [CrossRef]
  3. J. R. Fienup, “Phase-retrieval algorithms for a complicated optical system,” Appl. Opt. 32, 1737–1746 (1993).
    [CrossRef]
  4. A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. (SIAM, 2008).
  5. J. R. Fienup, “Phase retrieval for undersampled broadband images,” J. Opt. Soc. Am. A 16, 1831–1837 (1999).
    [CrossRef]
  6. R. G. Paxman, T. J. Schulz, and J. R. Fienup, “Joint estimation of object and aberrations by using phase diversity,” J. Opt. Soc. Am. A 9, 1072–1085 (1992).
    [CrossRef]
  7. K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical Methods for Physics and Engineering (Cambridge University, 2006).
  8. L. Hascoet and V. Pascual, “The tapenade automatic differentiation tool: principles, model, and specification,” ACM Trans. Math. Softw. 39, 1–43 (2013).
    [CrossRef]
  9. A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
    [CrossRef]
  10. B. Bell, “CppAD: a package for C++ algorithmic differentiation,” in Computational Infrastructure for Operations Research (2012), http://www.coin-or.org/CppAD/ .
  11. “Selected AD tools,” http://www.autodiff.org .
  12. A. Lee, “ad 1.2.2,” https://pypi.python.org/pypi/ad .
  13. N. C. Domingo, “adol-Py,” https://pypi.python.org/pypi/adol-Py/0.1 .
  14. B. M. Bell, “pycppad,” http://www.seanet.com/~bradbell/pycppad/index.xml .
  15. J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).
  16. S. F. Walter and L. Lehmann, “Algorithmic differentiation in Python with AlgoPy,” J. Comput. Sci. 4, 334–344 (2013).
  17. SymPy Development Team, “SymPy: Python library for symbolic mathematics” (2014), http://www.sympy.org .

2013 (2)

L. Hascoet and V. Pascual, “The tapenade automatic differentiation tool: principles, model, and specification,” ACM Trans. Math. Softw. 39, 1–43 (2013).
[CrossRef]

S. F. Walter and L. Lehmann, “Algorithmic differentiation in Python with AlgoPy,” J. Comput. Sci. 4, 334–344 (2013).

1999 (1)

1996 (1)

A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
[CrossRef]

1993 (1)

1992 (1)

1982 (1)

Bastien, F.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Bence, S. J.

K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical Methods for Physics and Engineering (Cambridge University, 2006).

Bengio, Y.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Bergstra, J.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Breuleux, O.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Desjardins, G.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Fienup, J. R.

Griewank, A.

A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
[CrossRef]

A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. (SIAM, 2008).

Hascoet, L.

L. Hascoet and V. Pascual, “The tapenade automatic differentiation tool: principles, model, and specification,” ACM Trans. Math. Softw. 39, 1–43 (2013).
[CrossRef]

Hobson, M. P.

K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical Methods for Physics and Engineering (Cambridge University, 2006).

Juedes, D.

A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
[CrossRef]

Lamblin, P.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Lehmann, L.

S. F. Walter and L. Lehmann, “Algorithmic differentiation in Python with AlgoPy,” J. Comput. Sci. 4, 334–344 (2013).

Nocedal, J.

S. J. Wright and J. Nocedal, “Quasi-Newton methods,” in Numerical Optimization (Springer, 1999), Sect. 8.1.

Pascanu, R.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Pascual, V.

L. Hascoet and V. Pascual, “The tapenade automatic differentiation tool: principles, model, and specification,” ACM Trans. Math. Softw. 39, 1–43 (2013).
[CrossRef]

Paxman, R. G.

Riley, K. F.

K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical Methods for Physics and Engineering (Cambridge University, 2006).

Schulz, T. J.

Turian, J.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Utke, J.

A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
[CrossRef]

Walter, S. F.

S. F. Walter and L. Lehmann, “Algorithmic differentiation in Python with AlgoPy,” J. Comput. Sci. 4, 334–344 (2013).

Walther, A.

A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. (SIAM, 2008).

Warde-Farley, D.

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

Wright, S. J.

S. J. Wright and J. Nocedal, “Quasi-Newton methods,” in Numerical Optimization (Springer, 1999), Sect. 8.1.

ACM Trans. Math. Softw. (2)

L. Hascoet and V. Pascual, “The tapenade automatic differentiation tool: principles, model, and specification,” ACM Trans. Math. Softw. 39, 1–43 (2013).
[CrossRef]

A. Griewank, D. Juedes, and J. Utke, “Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++,” ACM Trans. Math. Softw. 22, 131–167 (1996).
[CrossRef]

Appl. Opt. (2)

J. Comput. Sci. (1)

S. F. Walter and L. Lehmann, “Algorithmic differentiation in Python with AlgoPy,” J. Comput. Sci. 4, 334–344 (2013).

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

Other (10)

K. F. Riley, M. P. Hobson, and S. J. Bence, Mathematical Methods for Physics and Engineering (Cambridge University, 2006).

SymPy Development Team, “SymPy: Python library for symbolic mathematics” (2014), http://www.sympy.org .

S. J. Wright and J. Nocedal, “Quasi-Newton methods,” in Numerical Optimization (Springer, 1999), Sect. 8.1.

A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. (SIAM, 2008).

B. Bell, “CppAD: a package for C++ algorithmic differentiation,” in Computational Infrastructure for Operations Research (2012), http://www.coin-or.org/CppAD/ .

“Selected AD tools,” http://www.autodiff.org .

A. Lee, “ad 1.2.2,” https://pypi.python.org/pypi/ad .

N. C. Domingo, “adol-Py,” https://pypi.python.org/pypi/adol-Py/0.1 .

B. M. Bell, “pycppad,” http://www.seanet.com/~bradbell/pycppad/index.xml .

J. Bergstra, O. Breuleux, F. Bastien, P. Lamblin, R. Pascanu, G. Desjardins, J. Turian, D. Warde-Farley, and Y. Bengio, “Theano: a CPU and GPU math expression compiler,” in Proceedings of the Python for Scientific Computing Conference (SciPy) (2010).

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.


Tables (1)

Tables Icon

Table 1. Gradient Rules

Equations (86)

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

y=f(x)yn=f(xn).
[x2]n=xn2.
W=nanZn,
g=Aexp(i2πλW),
G=FFT{g}.
I=|G|2.
E=mwm(ImDm)2,
a^=argminaE.
W¯=2πλI{IFFT[4w(ID)G*]g*},Ean=p(W¯Zn)p,
W¯p=EWp,
f=f(x1,x2,,xn),
xi=xi(u1,u2,,um),
fuj=i=1nfxixiuj.
v1=f1(x),v2=f2(v1),E=f3(v2),
Ev2=f3(v2),
(Ev2)kEv2,k,
Ev2v2E.
(Ev1)w=kEv2,kv2,kv1,w.
(Ex)r=wEv1,wv1,wxr.
vk=fk(vk1).
Evk1,w=qEvk,qvk,qvk1,w.
x¯Ex
x¯kExk
x¯=xE.
y=f(x),
fmn(x)=ymxn,
x¯nExn,y¯mEym.
Exn=mEymymxn,x¯n=my¯mfmn(x).
x¯n=[f¯(x,y¯)]n=my¯mfmn(x)
x¯f¯(x,y¯).
f¯(x,y¯)=y¯*f(x)
E=G(x0).
x1=f1(x0),x2=f2(x1),xn=fn(xn1),E=xn.
E¯=1,x¯n=E¯,x¯n1=f¯n(xn1,x¯n)x¯0=f¯1(x0,x¯1).
y=f(x),
x¯=f¯(x,y¯)
yyR+iyI,xxR+ixI,yRfR(xR,xI),yIfI(xR,xI).
x¯R,n=ExR,n,x¯I,n=ExI,n,y¯R,n=EyR,n,y¯I,n=EyI,n.
x¯R,n=mEyR,myR,mxR,n+mEyI,myI,mxR,n=my¯R,mfR,m(xR,xI)xR,n+my¯I,mfI,m(xR,xI)xR,nf¯R,n(xR,xI;y¯R,y¯I),x¯I,n=mEyR,myR,mxI,n+mEyI,myI,mxI,n=my¯R,mfR,m(xR,xI)xI,n+my¯I,mfI,m(xR,xI)xI,nf¯I,n(xR,xI;y¯R,y¯I).
y¯y¯R+iy¯I,x¯x¯R+ix¯I,
f¯(x,y¯)f¯R(xR,xI;y¯R,y¯I)+if¯I(xR,xI;y¯R,y¯I).
y1=f1(x),y2=f2(x),
x¯=f¯1(x,y¯1)+f¯2(x,y¯2).
y=f(x),
x¯x¯+f¯(x,y¯),
x¯x¯+f¯2(x,y¯2),x¯x¯+f¯1(x,y¯1),
x¯[α]x¯[α]+y¯
z=x+iy
x¯=z¯,y¯=iz¯,
x=xC,y=yC,z=x+iy,
R{x}=x,I{x}=0.
x=xC,x¯=R{x¯}.
x¯=R{z¯},y¯=R{iz¯}.
ym=nAmnxn,y=A*x.
x¯=AT**y¯.
ExR,l=mEyR,myR,mxR,l+mEyI,myI,mxR,l=my¯R,mxR,lR{nAmnxn}+my¯I,mxR,lI{nAmnxn}=my¯R,mxR,ln(AR,mnxR,nAI,mnxI,n)+my¯I,mxR,ln(AR,mnxI,n+AI,mnxR,n)=my¯R,mAR,ml+my¯I,mAI,ml.
ExI,l=mEyR,myR,mxI,l+mEyI,myI,mxI,l=my¯R,mxI,ln(AR,mnxR,nAI,mnxI,n)+my¯I,mxI,ln(AR,mnxI,n+AI,mnxR,n)=my¯R,mAI,ml+my¯I,mAR,ml.
x¯l=ExR,l+iExI,l=my¯R,mAR,ml+my¯I,mAI,mlimy¯R,mAI,ml+imy¯I,mAR,ml=m(y¯R,m+iy¯I,m)(AR,mliAI,ml)=my¯mAml*=m(AT*)lmy¯m
x¯=AT**y¯,
y=DFT{x},ym=an=0N1xnexp(i2πnmN),
Amn=aexp(i2πnmN),
x¯n=m=0N1(AT*)nmy¯m=am=0N1exp(i2πnmN)y¯m.
IDFT{x}m=bn=0N1xnexp(i2πnmN),
x¯=abIDFT{y¯}.
Forward DFTy=DFT{x}x¯=abIDFT{y¯}x,yCN
Inverse DFTy=IDFT{x}x¯=baDFT{y¯}x,yCN
a=[a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a33a40a41a42a43a50a51a52a53].
b=[b00b10b01b11]=bin3×2(a)=[n=02m=01anmn=02m=23anmn=35m=01anmn=35m=23anm].
b00=a00+a01+a10+a11+a20+a21,
a¯00=Ea00=nmEbnmbnma00=Eb00=b¯00,
a¯=tile3×2(b¯)=[b¯00b¯00b¯01b¯01b¯00b¯00b¯01b¯01b¯00b¯00b¯01b¯01b¯10b¯10b¯11b¯11b¯10b¯10b¯11b¯11b¯10b¯10b¯11b¯11].
(binp×q(a))rs=n=rp(r+1)pm=sq(s+1)qanm,
(tilep×q(b))nm=bn/p,m/q,
Pixel binningy=binp×q(x)x¯=tilep×q(y¯)xRN×MyRpN×qM
Pixel tilingy=tilep×q(x)x¯=binp×q(y¯)xRpN×qMyRN×M
binp×q[tilep×q(x)]=pqx,
tilep×q[binp×q(x)]pqx.
I¯=2w(ID)
G¯=2I¯G
g¯=IFFT(G¯)
W¯=2πλI[g¯g*]
a¯n=pW¯pZn,p
D=aII+bI+c+n,
W=nanZn,θ=2πλW,g=Aexp(iθ),G=FFT{g},I=|G|2=GG*,M=aII+bI+c,E=n[w(MD)2]n,
M¯=2w(MD),I¯=2aIM¯+bM¯=M¯(2aI+b),G¯=2GI¯,g¯=IFFT{G¯},θ¯=I{g*g¯},W¯=2πλθ¯,a¯n=m(W¯Zn)m,
a¯=mM¯mIm2,b¯=mM¯mIm,c¯=mM¯m.

Metrics