×

Admissible measurements and robust algorithms for ptychography. (English) Zbl 1459.94017

Summary: 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^\ast\) 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.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alexeev, B.; Bandeira, AS; Fickus, M.; Mixon, DG, Phase retrieval with polarization, SIAM J. Imaging Sci., 7, 1, 35-66 (2014) · Zbl 1304.49071 · doi:10.1137/12089939X
[2] 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 · Zbl 0374.94002
[3] Balan, R.: On signal reconstruction from its spectrogram. In: 2010 44th Annual Conference on Information Sciences and Systems (CISS), pp. 1-4. IEEE (2010)
[4] Balan, R.; Casazza, P.; Edidin, D., On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20, 3, 345-356 (2006) · Zbl 1090.94006 · doi:10.1016/j.acha.2005.07.001
[5] Balan, R.; Bodmann, BG; Casazza, PG; Edidin, D., Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl., 15, 4, 488-501 (2009) · Zbl 1181.42032 · doi:10.1007/s00041-009-9065-1
[6] 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) · doi:10.1364/JOSAA.20.001025
[7] Bauschke, HH; Combettes, PL; Luke, DR, 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) · doi:10.1364/JOSAA.19.001334
[8] 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). doi:10.1109/ICASSP.2017.7953062
[9] 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. doi:10.1109/LSP.2017.2690358
[10] 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. doi:10.1109/TIT.2017.2745623 · Zbl 1390.94093
[11] Bodmann, BG; Hammen, N., Stable phase retrieval with low-redundancy frames, Adv. Comput. Math., 41, 2, 317-331 (2015) · Zbl 1316.42035 · doi:10.1007/s10444-014-9359-y
[12] 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. doi:10.1016/j.acha.2016.03.005 · Zbl 1372.65357
[13] 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). doi:10.1109/ICIP.2018.8451437
[14] Bragg, WH; Bragg, L., X-rays and Crystal Structure (1915), London: G. Bell and Sons, Ltd, London · JFM 45.1048.06
[15] Candés, EJ; 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) · Zbl 1335.94013 · doi:10.1002/cpa.21432
[16] Candés, EJ; Li, X.; Soltanolkotabi, M., Phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 39, 2, 277-299 (2015) · Zbl 1329.78056 · doi:10.1016/j.acha.2014.09.004
[17] 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. doi:10.1109/TIT.2015.2399924 · Zbl 1359.94069
[18] 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) · Zbl 1444.81008 · doi:10.1107/S2053273318001924
[19] Dainty, JC; Fienup, J., Phase retrieval and image reconstruction for astronomy, Image Recovery: Theory Appl., 13, 01 (1987)
[20] 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) · doi:10.1051/epn:2008003
[21] 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) · doi:10.1109/LSP.2014.2364225
[22] Elser, V., Phase retrieval by iterated projections, J. Opt. Soc. Am. A Opt. Image Sci. Vis., 20, 1, 40-55 (2003) · doi:10.1364/JOSAA.20.000040
[23] Fienup, JR, Reconstruction of an object from the modulus of its Fourier transform, Opt. Lett., 3, 1, 27-29 (1978) · doi:10.1364/OL.3.000027
[24] Gerchberg, R.; Saxton, W., A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik, 35, 237-246 (1972)
[25] Goodman, JW, Introduction to Fourier Optics (2005), Englewood: Roberts and Company Publishers, Englewood
[26] Gray, R.M.: Toeplitz and circulant matrices: a review. Found. Trends Commun. Inf. Theory 2(3), 155-239 (2006). ISSN 1567-2190. doi:10.1561/0100000006 · Zbl 1143.15305
[27] Gross, D.; Krahmer, F.; Kueng, R., Improved recovery guarantees for phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 42, 37-64 (2015) · Zbl 1393.94250 · doi:10.1016/j.acha.2015.05.004
[28] 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. doi:10.1016/j.sigpro.2017.09.026
[29] 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. doi:10.1364/CLEO_SI.2017.STu3I.3. http://www.osapublishing.org/abstract.cfm?URI=CLEO_SI-2017-STu3I.3
[30] Hauptman, H.; Karle, J.; Association, AC, Solution of the Phase Problem (1953), New York: American Crystallographic Association, New York · Zbl 0053.33304
[31] Iwen, M.; Viswanathan, A.; Wang, Y., Fast phase retrieval from local correlation measurements, SIAM J. Imaging Sci., 9, 4, 1655-1688 (2016) · Zbl 1352.49035 · doi:10.1137/15M1053761
[32] Iwen, M., Viswanathan, A., Wang, Y.: Robust sparse phase retrieval made easy. Appl. Comput. Harmon. Anal. 42(1), 135-142 (2017). ISSN 1063-5203. doi:10.1016/j.acha.2015.06.007 · Zbl 1393.94274
[33] 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. doi:10.1016/j.acha.2018.06.004. http://www.sciencedirect.com/science/article/pii/S1063520318301210 · Zbl 07140142
[34] Jaganathan, K.; Eldar, YC; Hassibi, B., STFT phase retrieval: uniqueness guarantees and recovery algorithms, IEEE J. Sel. Top. Signal Process., 10, 4, 770-781 (2016) · doi:10.1109/JSTSP.2016.2549507
[35] 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
[36] Kech, M.: Explicit frames for deterministic phase retrieval via phaselift. Appl. Comput. Harmon. Anal. 45(2), 282-298 (2018). ISSN 1063-5203. doi:10.1016/j.acha.2016.09.005 · Zbl 1414.94294
[37] 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). doi:10.1109/SAMPTA.2015.7148878 · Zbl 1332.90197
[38] Kueng, R., Zhu, H., Gross, D.: Low rank matrix recovery from Clifford orbits. CoRR. abs/1610.08070 (2016)
[39] Laub, AJ, Matrix Analysis For Scientists And Engineers, 0898715768 (2004), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia
[40] 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. doi:10.1016/j.acha.2018.01.001 · Zbl 1422.94013
[41] Ling, S.; Strohmer, T., Self-calibration and biconvex compressive sensing, Inverse Probl., 31, 11, 115002 (2015) · Zbl 1327.93183 · doi:10.1088/0266-5611/31/11/115002
[42] Mallat, S., Waldspurger, I.: Phase retrieval for the cauchy wavelet transform. J. Fourier Anal. Appl. 21(6), 1251-1309 (2015). ISSN 1531-5851. doi:10.1007/s00041-015-9403-4 · Zbl 1361.94025
[43] Marchesini, S.; Tu, Y-C; Wu, H-T, Alternating projection, ptychographic imaging and phase synchronization, Appl. Comput. Harmon. Anal., 41, 3, 815-851 (2016) · Zbl 1388.94015 · doi:10.1016/j.acha.2015.06.005
[44] 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)
[45] Netrapalli, P., Jain, P., Sanghavi, S.: Phase retrieval using alternating minimization. Adv. Neural Inf. Process. Syst., pp. 2796-2804 (2013) · Zbl 1394.94421
[46] Pauwels, E.; Beck, A.; Eldar, YC; Sabach, S., On Fienup methods for sparse phase retrieval, IEEE Trans. Signal Process., 1, 12 (2017) · Zbl 1414.94467 · doi:10.1109/TSP.2017.2780044
[47] 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)
[48] Pfander, G.E., Salanevich, P.: Robust phase retrieval algorithm for time-frequency structured measurements (2016). eprint arXiv:1611.02540
[49] 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). doi:10.1109/ICASSP.1979.1170695
[50] Preskitt, B.P.: Phase Retrieval from Locally Supported Measurements. PhD thesis, UC San Diego (2018a)
[51] Preskitt, B.P.: Brian preskitt’s dissertation code (2018b). https://github.com/bpreskit/pr_code
[52] Putkunz, CT; D’Alfonso, AJ; Morgan, AJ; Weyland, M.; Dwyer, C.; Bourgeois, L.; Etheridge, J.; Roberts, A.; Scholten, RE; Nugent, KA; Allen, LJ, Atom-scale ptychographic electron diffractive imaging of boron nitride cones, Phys. Rev. Lett., 108, 073901 (2012) · doi:10.1103/PhysRevLett.108.073901
[53] Rabiner, L., Juang, B.-H.: Fundamentals of Speech Recognition. Prentice-Hall Inc, Upper Saddle River, NJ, USA (1993) 0-13-015157-2
[54] Rodenburg, J., Ptychography and related diffractive imaging methods, Adv. Imaging Electron Phys., 150, 87-184 (2008) · doi:10.1016/S1076-5670(07)00003-1
[55] 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)
[56] 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). doi:10.1109/ISIT.2018.8437494
[57] Shapiro, DA; Yu, Y-S; Tyliszczak, T.; Cabana, J.; Celestre, R.; Chao, W.; Kaznatcheev, K.; Kilcoyne, ALD; Maia, F.; Marchesini, S.; Meng, YS; Warwick, T.; Yang, LL; Padmore, HA, Chemical composition mapping with nanometre resolution by soft x-ray microscopy, Nat. Photon., 8, 765-769 (2014) · doi:10.1038/nphoton.2014.207
[58] Shechtman, Y.; Eldar, YC; Cohen, O.; Chapman, HN; Miao, J.; Segev, M., Phase retrieval with application to optical imaging: a contemporary overview, IEEE Signal Process. Mag., 32, 3, 87-109 (2015) · doi:10.1109/MSP.2014.2352673
[59] Starodub, D.; Rez, P.; Hembree, G.; Howells, M.; Shapiro, D.; Chapman, HN; Fromme, P.; Schmidt, K.; Weierstall, U.; Doak, RB; Spence, JCH, Dose, exposure time and resolution in serial X-ray crystallography, J. Synchrotron Radiat., 15, 1, 62-73 (2008) · doi:10.1107/S0909049507048893
[60] 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) · doi:10.1364/JOSAA.14.003175
[61] 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) · doi:10.1364/JOSAA.15.002849
[62] 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) · doi:10.1364/JOSAA.16.002163
[63] 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
[64] Waldspurger, I.: Phase retrieval with random gaussian sensing vectors by alternating projections. IEEE Trans. Inf. Theory 64(5), 3301-3312 (2018). ISSN 0018-9448. doi:10.1109/TIT.2018.2800663 · Zbl 1395.94172
[65] Waldspurger, I., d’Aspremont, A., Mallat, S.: Phase recovery, maxcut and complex semidefinite programming. Math. Programm. 149(1), 47-81 (2015). ISSN 1436-4646. doi:10.1007/s10107-013-0738-9 · Zbl 1329.94018
[66] Walther, A., The question of phase retrieval in optics, Opt. Acta, 10, 41-49 (1963) · doi:10.1080/713817747
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.