Admissible Measurements and Robust Algorithms for Ptychography
Tóm tắt
We study an approach to solving the phase retrieval problem as it arises in a phase-less imaging modality known as ptychography. In ptychography, small overlapping sections of an unknown sample (or signal, say
$$x_0\in \mathbb {C}^{d}$$
) are illuminated one at a time, often with a physical mask between the sample and light source. The corresponding measurements are the noisy magnitudes of the Fourier transform coefficients resulting from the pointwise product of the mask and the sample. The goal is to recover the original signal from such measurements. The algorithmic framework we study herein relies on first inverting a linear system of equations to recover a fraction of the entries in
$$x_0 x_0^*$$
and then using non-linear techniques to recover the magnitudes and phases of the entries of
$$x_0$$
. Thus, this paper’s contributions are three-fold. First, focusing on the linear part, it expands the theory studying which measurement schemes (i.e., masks, shifts of the sample) yield invertible linear systems, including an analysis of the conditioning of the resulting systems. Second, it analyzes a class of improved magnitude recovery algorithms and, third, it proposes and analyzes algorithms for phase recovery in the ptychographic setting where large shifts—up to
$$50\%$$
the size of the mask—are permitted.
Tài liệu tham khảo
Alexeev, B., Bandeira, A.S., Fickus, M., Mixon, D.G.: Phase retrieval with polarization. SIAM J. Imaging Sci. 7(1), 35–66 (2014)
Allen, J.: Short term spectral analysis, synthesis, and modification by discrete fourier transform. IEEE Trans. Acoust. Speech Signal Process. 25(3), 235–238 (1977). ISSN 0096-3518. 10.1109/TASSP.1977.1162950
Balan, R.: On signal reconstruction from its spectrogram. In: 2010 44th Annual Conference on Information Sciences and Systems (CISS), pp. 1–4. IEEE (2010)
Balan, R., Casazza, P., Edidin, D.: On signal reconstruction without phase. Appl. Comput. Harmon. Anal. 20(3), 345–356 (2006)
Balan, R., Bodmann, B.G., Casazza, P.G., Edidin, D.: Painless reconstruction from magnitudes of frame coefficients. J. Fourier Anal. Appl. 15(4), 488–501 (2009)
Bauschke, H., Combettes, P., Luke, D.: Hybrid projection-reflection method for phase retrieval. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 20(6), 1025–1034 (2003)
Bauschke, H.H., Combettes, P.L., Luke, D.R.: Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 19(7), 1334–1345 (2002)
Bendory, T., Eldar, Y.C.: Phase retrieval from STFT measurements via non-convex optimization. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4770–4774 (2017). https://doi.org/10.1109/ICASSP.2017.7953062
Bendory, T., Sidorenko, P., Eldar, Y.C.: On the uniqueness of frog methods. IEEE Signal Process. Lett. 24(5), 722–726 (2017). ISSN 1070-9908. https://doi.org/10.1109/LSP.2017.2690358
Bendory, T., Eldar, Y.C., Boumal, N.: Non-convex phase retrieval from STFT measurements. IEEE Trans. Inf. Theory 64(1), 467–484 (2018). ISSN 0018-9448. https://doi.org/10.1109/TIT.2017.2745623
Bodmann, B.G., Hammen, N.: Stable phase retrieval with low-redundancy frames. Adv. Comput. Math. 41(2), 317–331 (2015)
Bodmann, B.G., Hammen, N.: Algorithms and error bounds for noisy phase retrieval with low-redundancy frames. Appl. Comput. Harmon. Anal. 43(3), 482–503 (2017). ISSN 1063-5203. https://doi.org/10.1016/j.acha.2016.03.005
Bostan, E., Soltanolkotabi, M., Ren, D., Waller, L.: Accelerated wirtinger flow for multiplexed fourier ptychographic microscopy. In 2018 25th IEEE International Conference on Image Processing (ICIP), pp. 3823–3827 (2018). https://doi.org/10.1109/ICIP.2018.8451437
Bragg, W.H., Bragg, L.: X-rays and Crystal Structure. G. Bell and Sons, Ltd, London (1915)
Candés, E.J., Strohmer, T., Voroninski, V.: Phaselift: exact and stable signal recovery from magnitude measurements via convex programming. Commun. Pure Appl. Math. 66(8), 1241–1274 (2013)
Candés, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval from coded diffraction patterns. Appl. Comput. Harmon. Anal. 39(2), 277–299 (2015a)
Candés, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via wirtinger flow: theory and algorithms. IEEE Trans. Inf. Theory 61(4), 1985–2007 (2015b). ISSN 0018-9448. https://doi.org/10.1109/TIT.2015.2399924
Chang, H., Enfedaque, P., Lou, Y., Marchesini, S.: Partially coherent ptychography by gradient decomposition of the probe. Acta Crystallogr. Sect. A 74(3), 157–169 (2018). https://doi.org/10.1107/S2053273318001924
Dainty, J.C., Fienup, J.: Phase retrieval and image reconstruction for astronomy. Image Recovery: Theory Appl. 13, 01 (1987)
Dierolf, M., Bunk, O., Kynde, S., Thibault, P., Johnson, I., Menzel, A., Jefimovs, K., David, C., Marti, O., Pfeiffer, F.: Ptychography & lensless X-ray imaging. Europhys. News 39(1), 22–24 (2008)
Eldar, Y., Sidorenko, P., Mixon, D., Barel, S., Cohen, O.: Sparse phase retrieval from short-time Fourier measurements. IEEE Signal Proc. Lett. 22(5), 638–642 (2015)
Elser, V.: Phase retrieval by iterated projections. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 20(1), 40–55 (2003)
Fienup, J.R.: Reconstruction of an object from the modulus of its Fourier transform. Opt. Lett. 3(1), 27–29 (1978)
Gerchberg, R., Saxton, W.: A practical algorithm for the determination of the phase from image and diffraction plane pictures. Optik 35, 237–246 (1972)
Goodman, J.W.: Introduction to Fourier Optics. Roberts and Company Publishers, Englewood (2005)
Gray, R.M.: Toeplitz and circulant matrices: a review. Found. Trends Commun. Inf. Theory 2(3), 155–239 (2006). ISSN 1567-2190. https://doi.org/10.1561/0100000006
Gross, D., Krahmer, F., Kueng, R.: Improved recovery guarantees for phase retrieval from coded diffraction patterns. Appl. Comput. Harmon. Anal. 42, 37–64 (2015)
Guo, Y., Wang, A., Wang, W.: Multi-source phase retrieval from multi-channel phaseless STFT measurements. Signal Process. 144, 36–40 (2018). ISSN 0165-1684. https://doi.org/10.1016/j.sigpro.2017.09.026
Haham, G.I., Sidorenko, P., Cohen, O.: Reconstruction of an isolated burst of (non-repetitive) pulses from a single frog trace. In Conference on Lasers and Electro-Optics, p. STu3I.3. Optical Society of America, 2017. https://doi.org/10.1364/CLEO_SI.2017.STu3I.3. http://www.osapublishing.org/abstract.cfm?URI=CLEO_SI-2017-STu3I.3
Hauptman, H., Karle, J., Association, A.C.: Solution of the Phase Problem. American Crystallographic Association, New York (1953)
Iwen, M., Viswanathan, A., Wang, Y.: Fast phase retrieval from local correlation measurements. SIAM J. Imaging Sci. 9(4), 1655–1688 (2016)
Iwen, M., Viswanathan, A., Wang, Y.: Robust sparse phase retrieval made easy. Appl. Comput. Harmon. Anal. 42(1), 135–142 (2017). ISSN 1063-5203. https://doi.org/10.1016/j.acha.2015.06.007
Iwen, M.A., Preskitt, B., Saab, R., Viswanathan, A.: Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization. Appl. Comput. Harmon. Anal. (2018). ISSN 1063-5203. https://doi.org/10.1016/j.acha.2018.06.004. http://www.sciencedirect.com/science/article/pii/S1063520318301210
Jaganathan, K., Eldar, Y.C., Hassibi, B.: STFT phase retrieval: uniqueness guarantees and recovery algorithms. IEEE J. Sel. Top. Signal Process. 10(4), 770–781 (2016)
Jagatap, G., Hegde, C.: Fast, sample-efficient algorithms for structured phase retrieval. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30, pp. 4917–4927. Curran Associates, Inc. (2017). http://papers.nips.cc/paper/7077-fast-sample-efficient-algorithms-for-structured-phase-retrieval.pdf
Kech, M.: Explicit frames for deterministic phase retrieval via phaselift. Appl. Comput. Harmon. Anal. 45(2), 282–298 (2018). ISSN 1063-5203. https://doi.org/10.1016/j.acha.2016.09.005
Kueng, R., Gross, D., Krahmer, F.: Spherical designs as a tool for derandomization: the case of phaselift. In: 2015 International Conference on Sampling Theory and Applications (SampTA), pp. 192–196 (2015). https://doi.org/10.1109/SAMPTA.2015.7148878
Kueng, R., Zhu, H., Gross, D.: Low rank matrix recovery from Clifford orbits. CoRR. abs/1610.08070 (2016)
Laub, A.J.: Matrix Analysis For Scientists And Engineers, p. 0898715768. Society for Industrial and Applied Mathematics, Philadelphia (2004)
Li, X., Ling, S., Strohmer, T., Wei, K.: Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Appl. Comput. Harmon. Anal. (2018). ISSN 1063-5203. https://doi.org/10.1016/j.acha.2018.01.001
Ling, S., Strohmer, T.: Self-calibration and biconvex compressive sensing. Inverse Probl. 31(11), 115002 (2015)
Mallat, S., Waldspurger, I.: Phase retrieval for the cauchy wavelet transform. J. Fourier Anal. Appl. 21(6), 1251–1309 (2015). ISSN 1531-5851. https://doi.org/10.1007/s00041-015-9403-4
Marchesini, S., Tu, Y.-C., Wu, H.-T.: Alternating projection, ptychographic imaging and phase synchronization. Appl. Comput. Harmon. Anal. 41(3), 815–851 (2016)
Melnyk, O., Filbir, F., Krahmer, F.: Phase retrieval from local correlation measurements with fixed shift length. In: Mathematics in Imaging, p. MTu4D–3. Optical Society of America (2019)
Netrapalli, P., Jain, P., Sanghavi, S.: Phase retrieval using alternating minimization. Adv. Neural Inf. Process. Syst., pp. 2796–2804 (2013)
Pauwels, E., Beck, A., Eldar, Y.C., Sabach, S.: On Fienup methods for sparse phase retrieval. IEEE Trans. Signal Process. 1, 12 (2017). https://doi.org/10.1109/TSP.2017.2780044
Perlmutter, M., Merhi, S., Viswanathan, A., Iwen, M.: Inverting spectrogram measurements via aliased wigner distribution deconvolution and angular synchronization. arXiv preprint arXiv:1907.10773 (2019)
Pfander, G.E., Salanevich, P.: Robust phase retrieval algorithm for time-frequency structured measurements (2016). eprint arXiv:1611.02540
Portnoff, M.: Magnitude-phase relationships for short-time Fourier transforms based on gaussian analysis windows. In: ICASSP ’79. IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 4, pp. 186–189 (1979). https://doi.org/10.1109/ICASSP.1979.1170695
Preskitt, B.P.: Phase Retrieval from Locally Supported Measurements. PhD thesis, UC San Diego (2018a)
Preskitt, B.P.: Brian preskitt’s dissertation code (2018b). https://github.com/bpreskit/pr_code
Putkunz, C.T., D’Alfonso, A.J., Morgan, A.J., Weyland, M., Dwyer, C., Bourgeois, L., Etheridge, J., Roberts, A., Scholten, R.E., Nugent, K.A., Allen, L.J.: Atom-scale ptychographic electron diffractive imaging of boron nitride cones. Phys. Rev. Lett. 108, 073901 (2012)
Rabiner, L., Juang, B.-H.: Fundamentals of Speech Recognition. Prentice-Hall Inc, Upper Saddle River, NJ, USA (1993) 0-13-015157-2
Rodenburg, J.: Ptychography and related diffractive imaging methods. Adv. Imaging Electron Phys. 150, 87–184 (2008)
Salanevich, P., Pfander, G.E.: Polarization based phase retrieval for time-frequency structured measurements. In: 2015 International Conference on Sampling Theory and Applications (SampTA), pp. 187–191. IEEE (2015)
Salehi, F., Abbasi, E., Hassibi, B.: A precise analysis of phasemax in phase retrieval. In: 2018 IEEE International Symposium on Information Theory (ISIT), pp. 976–980 (2018). https://doi.org/10.1109/ISIT.2018.8437494
Shapiro, D.A., Yu, Y.-S., Tyliszczak, T., Cabana, J., Celestre, R., Chao, W., Kaznatcheev, K., Kilcoyne, A.L.D., Maia, F., Marchesini, S., Meng, Y.S., Warwick, T., Yang, L.L., Padmore, H.A.: Chemical composition mapping with nanometre resolution by soft x-ray microscopy. Nat. Photon. 8, 765–769 (2014)
Shechtman, Y., Eldar, Y.C., Cohen, O., Chapman, H.N., Miao, J., Segev, M.: Phase retrieval with application to optical imaging: a contemporary overview. IEEE Signal Process. Mag. 32(3), 87–109 (2015)
Starodub, D., Rez, P., Hembree, G., Howells, M., Shapiro, D., Chapman, H.N., Fromme, P., Schmidt, K., Weierstall, U., Doak, R.B., Spence, J.C.H.: Dose, exposure time and resolution in serial X-ray crystallography. J. Synchrotron Radiat. 15(1), 62–73 (2008). https://doi.org/10.1107/S0909049507048893
Takajo, H., Takahashi, T., Kawanami, H., Ueda, R.: Numerical investigation of the iterative phase-retrieval stagnation problem: territories of convergence objects and holes in their boundaries. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 14(12), 3175–3187 (1997)
Takajo, H., Takahashi, T., Ueda, R., Taninaka, M.: Study on the convergence property of the hybrid input–output algorithm used for phase retrieval. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 15(11), 2849–2861 (1998)
Takajo, H., Takahashi, T., Shizuma, T.: Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval. J. Opt. Soc. Am. A Opt. Image Sci. Vis. 16(9), 2163–2168 (1999)
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., Recht, B.: Low-rank solutions of linear matrix equations via procrustes flow. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceedings of The 33rd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 48, pp. 964–973, New York, New York, USA, 20–22 June 2016. PMLR. http://proceedings.mlr.press/v48/tu16.html
Waldspurger, I.: Phase retrieval with random gaussian sensing vectors by alternating projections. IEEE Trans. Inf. Theory 64(5), 3301–3312 (2018). ISSN 0018-9448. https://doi.org/10.1109/TIT.2018.2800663
Waldspurger, I., d’Aspremont, A., Mallat, S.: Phase recovery, maxcut and complex semidefinite programming. Math. Programm. 149(1), 47–81 (2015). ISSN 1436-4646. https://doi.org/10.1007/s10107-013-0738-9
Walther, A.: The question of phase retrieval in optics. Opt. Acta 10, 41–49 (1963). https://doi.org/10.1080/713817747