×

Phase retrieval from Fourier measurements with masks. (English) Zbl 1472.94009

Summary: This paper concerns the problem of phase retrieval from Fourier measurements with random masks. Here we focus on researching two kinds of random masks. Firstly, we utilize the Fourier measurements with real masks to estimate a general signal \(\mathfrak{x}_0\in \mathbb{R}^d\) in noiseless case when \(d\) is even. It is demonstrated that \(O(\log^2d)\) real random masks are able to ensure accurate recovery of \(\mathfrak{x}_0\). Then we find that such real masks are not adaptable to reconstruct complex signals of even dimension. Subsequently, we prove that \(O(\log^4d)\) complex masks are enough to stably estimate a general signal \(\mathfrak{x}_0\in \mathbb{C}^d\) under bounded noise interference, which extends E. J. Candès et al.’s work [SIAM Rev. 57, No. 2, 225–251 (2015; Zbl 1344.49057)]. Meanwhile, we establish tighter error estimations for real signals of even dimensions or complex signals of odd dimensions by using \(O(\log^2d)\) real masks. Finally, we intend to tackle with the noisy phase problem about an \(s\)-sparse signal by a robust and efficient approach, namely, two-stage algorithm. Based on the stable guarantees for general signals, we show that the \(s\)-sparse signal \(\mathfrak{x}_0\) can be stably recovered from composite measurements under near-optimal sample complexity up to a \(\log\) factor, namely, \(O(s\log(\frac{ed}{s})\log^4(s\log(\frac{ed}{s})))\).

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A20 Sampling theory in information and communication theory
78A45 Diffraction, scattering
90C59 Approximation methods and heuristics in mathematical programming
49N30 Problems with incomplete information (optimization)

Citations:

Zbl 1344.49057
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Adcock; A. C. Hansen, Generalized sampling and infinite-dimensional compressed sensing, Found. Comput. Math., 16, 1263-1323 (2016) · Zbl 1379.94026 · doi:10.1007/s10208-015-9276-6
[2] S. Bahmani and J. Romberg, Efficient compressive phase retrieval with constrained sensing vectors, IEEE Neural Information Processing Systems, 1 (2015), 523-531. Available from: https://dl.acm.org/doi/abs/10.5555/2969239.2969298.
[3] R. Balan; B. G. Bodmann; P. G. Cassazza; D. Edidin, Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl., 15, 488-501 (2009) · Zbl 1181.42032 · doi:10.1007/s00041-009-9065-1
[4] A. S. Bandeira; J. Cahill; D. G. Mixon; A. A. Nelson, Saving phase: Injectivity and stability for phase retrieval, Appl. Comput. Harmon. Anal., 37, 106-125 (2014) · Zbl 1305.90330 · doi:10.1016/j.acha.2013.10.002
[5] A. S. Bandeira; Y. Chen; D. G. Mixon, Phase retrieval from power spectra of masked signals, Inform. Inference: A Journal of the IMA, 3, 83-102 (2014) · Zbl 1308.94031 · doi:10.1093/imaiai/iau002
[6] T. T. Cai; X. Li; Z. Ma, Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow, Ann. Statist., 44, 2221-2251 (2016) · Zbl 1349.62019 · doi:10.1214/16-AOS1443
[7] E. J. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346, 589-592 (2008) · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014
[8] E. J. Candès; Y. C. Eldar; T. Strohmer; V. Voroninshi, Phase retrieval via matrix completion, SIAM J. Imaging Sci., 6, 199-225 (2013) · Zbl 1280.49052 · doi:10.1137/110848074
[9] E. J. Candès; X. Li, Solving quadratic equations via phaselift when there are about as many equations as unknowns, Found. Comput. Math., 149, 1-10 (2013) · Zbl 1312.90054 · doi:10.1007/s10208-013-9162-z
[10] E. J. Candès; X. Li; M. Soltanolkotabi, Phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 39, 277-299 (2015) · Zbl 1329.78056 · doi:10.1016/j.acha.2014.09.004
[11] E. J. Candès; X. Li; M. Soltanolkotabi, Phase retrieval via Wirtinger Flow: Theory and algorithms, IEEE Trans. Inform. Theory, 61, 1985-2007 (2015) · Zbl 1359.94069 · doi:10.1109/TIT.2015.2399924
[12] E. J. Candès; Y. Plan, A probabilistic and RIP-less theory of compressed sensing, IEEE Trans. Inform. Theory, 57, 7235-7254 (2011) · Zbl 1365.94174 · doi:10.1109/TIT.2011.2161794
[13] E. J. Candès; T. Stromher; V. Voroninshi, PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66, 1241-1274 (2013) · Zbl 1335.94013 · doi:10.1002/cpa.21432
[14] E. J. Candès; T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[15] E. J. Candès; T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 56, 2053-2080 (2010) · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061
[16] A. Chai, M. Moscoso and G. Papanicolaou, Array imaging using intensity-only measurements, Inverse Probl., 27 (2011), 015005, 16 pp. · Zbl 1207.78022
[17] Y. Chen; E. J. Candès, Solving random quadratic systems of equations is nearly as easy as solving linear systems, Comm. Pure Appl. Math., 70, 739-747 (2015) · Zbl 1379.90024 · doi:10.1002/cpa.21638
[18] J. V. Corbett, The Pauli problem, state reconstruction and quantum-real numbers, Rep. Math. Phys., 57, 53-68 (2006) · Zbl 1110.81007 · doi:10.1016/S0034-4877(06)80008-X
[19] J. C. Dainty and J. R. Fienup, Phase retrieval and image reconstruction for astronomy, in Image Recovery: Theory and Application, Academic Press, (1987), 231-275. Available from: https://www.researchgate.net/publication/247171131_Phase_retrieval_and_image_reconstruction_for_astronomy.
[20] L. Demanet; P. Hand, Stable optimizationless recovery from phaseless linear measurements, J. Fourier Anal. Appl., 20, 199-221 (2014) · Zbl 1330.90069 · doi:10.1007/s00041-013-9305-2
[21] A. Fannjiang and W. Liao, Phase retrieval with random phase illumination, Inverse Problems, 28 (2012), 075008, 20 pp. · Zbl 1250.78024
[22] J. R. Fienup, Phase retrieval algorithms: A comparison, Appl. Opt., 21, 2758-2769 (1982) · doi:10.1364/AO.21.002758
[23] R. W. Gerchberg and W. O. Saxton, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, 35 (1972), 237-246. Available from: https://www.researchgate.net/publication/221725051_A_practical_algorithm_for_the_determination_of_phase_from_image_and_diffraction_plane_pictures.
[24] D. Gross, Recovering low rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 1548-1566 (2011) · Zbl 1366.94103 · doi:10.1109/TIT.2011.2104999
[25] D. Gross; F. Krahmer; R. Kueng, A partial derandomization of PhaseLift using spherical designs, J. Fourier Anal. Appl., 21, 229-266 (2015) · Zbl 1332.90197 · doi:10.1007/s00041-014-9361-2
[26] D. Gross; F. Krahmer; R. Kueng, Improved recovery guarantees for phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 42, 37-64 (2017) · Zbl 1393.94250 · doi:10.1016/j.acha.2015.05.004
[27] R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Amer. A, 10, 1046-1055 (1993) · doi:10.1364/JOSAA.10.001046
[28] W. Huang; K. A. Gallivan; X. Zhang, Solving PhaseLift by low-rank Riemannian optimization methods, Procedia Computer Science, 80, 1125-1134 (2016)
[29] M. J. Humphry; B. Kraus; A. C. Hurst; A. M. Maiden; J. M. Rodenburg, Ptychographic electron microscopy using high-angle dark-field scattering for sub-nanometre resolution imaging, Nature Communications, 3, 1-7 (2012) · doi:10.1038/ncomms1733
[30] M. Iwen; A. Viswanathan; Y. Wang, Robust sparse phase retrieval made easy, Appl. Comput. Harmon. Anal., 42, 135-142 (2017) · Zbl 1393.94274 · doi:10.1016/j.acha.2015.06.007
[31] K. Jaganathan, Y. C. Eldar and B. Hassibi, Phase retrieval with masks using convex optimization, IEEE International Symposium on Information Theory, (2015), 1655-1659.
[32] F. Kramher; Y.-K. Liu, Phase retrieval without small-ball probability assumptions, IEEE Trans. Inform. Theory, 64, 485-500 (2018) · Zbl 1390.94628 · doi:10.1109/TIT.2017.2757520
[33] R. Kueng; H. Rauhut; U. Terstiege, Low rank matrix recovery from rank one measurements, Appl. Comput. Harmon. Anal., 42, 88-116 (2014) · Zbl 1393.94310 · doi:10.1016/j.acha.2015.07.007
[34] X. Li; V. Voroninski, Sparse signal recovery from quadratic measurements via convex programming, SIAM J. Math. Anal., 45, 3019-3033 (2013) · Zbl 1320.94023 · doi:10.1137/120893707
[35] R. Millane, Phase retrieval in crystallography and optics, J. Opt. Soc. Amer. A, 7, 394-411 (1990) · doi:10.1364/JOSAA.7.000394
[36] M. L. Moravec; J. K. Romberg; R. G. Baraniuk, Compressive phase retrieval, Proceedings of SPIE, 6701, 6701201-67012011 (2007) · doi:10.1117/12.736360
[37] P. Netrapalli; P. Jain; S. Sanghavi, Phase retrieval using alternating minimization, IEEE Trans. Signal Process, 63, 4814-4826 (2015) · Zbl 1394.94421 · doi:10.1109/TSP.2015.2448516
[38] H. Ohlsson, A. Yang, R. Dong and S. Sastry, CPRL-An extension of compressive sensing to the phase retrieval problem, IEEE Neural Information Processing Systems, (2012), 1367-1375. Available from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.244.9102&rep=rep1&type=pdf
[39] R. Pedarsani, K. Lee and K. Ramchandran, Phasecode: Fast and efficient compressive phase retrieval based on sparse-graph codes, Allerton Conference on Communication, Control and Computing, (2014), 842-849.
[40] B. Recht; M. Fazel; P. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[41] Y. Shechtman; A. Beck; Y. C. Eldar, GESPAR: Efficient phase retrieval of sparse signals, IEEE Trans. Signal Process, 62, 928-938 (2014) · Zbl 1394.94522 · doi:10.1109/TSP.2013.2297687
[42] Y. Shechtman; Y. C. Eldar; O. Cohen; H. N. Chapman; J. Miao; M. Segev, Phase retrieval with application to optical imaging: A contemporary overview, IEEE Signal Processing Mag., 32, 87-109 (2015) · doi:10.1109/MSP.2014.2352673
[43] Y. Shechtman; Y. C. Eldar; A. Szameit; M. Segev, Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing, Optics Express, 19, 14807-14822 (2011) · doi:10.1364/OE.19.014807
[44] I. Waldspurger; A. d’Aspremont; S. Mallat, Phase recovery, maxcut and complex semidefinite programming, Math. Prog., 149, 47-81 (2015) · Zbl 1329.94018 · doi:10.1007/s10107-013-0738-9
[45] G. Wang; L. Zhang; G. B. Giannakis; M. Akcakaya; J. Chen, Sparse phase retrieval via truncated amplitude flow, IEEE Trans. Signal Process, 66, 479-491 (2018) · Zbl 1414.94656 · doi:10.1109/TSP.2017.2771733
[46] G. Zheng; R. Horstmeyer; C. Yang, Wide-field, high-resolution Fourier pty-chographic microscopy, Nature Photonics, 7, 739-745 (2013) · doi:10.1038/nphoton.2013.187
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.