Phase retrieval for sparse binary signal: uniqueness and algorithm. (English) Zbl 1429.94038
Summary: Phase retrieval, i.e. recovering a signal from its Fourier magnitude, is known to be an ill-posed inverse problem. For general 1-D signal without any constraints, there is originally no uniqueness guarantees for phase retrieval. We consider the phase retrieval problem of a special kind of signal, binary signal in this paper. Firstly, we show that if the number of measurements is no less than \(2n-1\), almost all binary signals of length \(n\) can be uniquely identified by their Fourier magnitude. Then we come up with a sparse binary phase retrieval algorithm utilizing the constrained Simulated Annealing (SA) method. Numerical tests show a good performance of the constrained SA method. At last, the constrained SA is combined with the Greedy Sparse Phase Retrieval (Gespar) to deal with the phase retrieval of general sparse signal. The effectiveness of this hybrid algorithm is demonstrated by numerical experiments too.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
binary signal; phase retrieval; simulated annealing (SA); Newman polynomial; nonconvex optimizationReferences:
| [1] | Millane RP. Phase retrieval in crystallography and optics. J Opt Soc Am A. 1990;7(3):394-411. |
| [2] | Walther A. The question of phase retrieval in optics. Opt Acta. 1963;10(1):41-49. |
| [3] | Jaganathan K, Oymak S, Hassibi B. Sparse phase retrieval: convex algorithms and limitations. In: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT); Istanbul, Turkey; 2013. p. 1022-1026. · Zbl 1414.94273 |
| [4] | Gerchberg RW. A practical algorithm for the determination of phase from image and diffraction plane pictures. Optik. 1971;35:237-250. |
| [5] | Fienup JR. Phase retrieval algorithms: a comparison. Appl Opt. 1982;21(15):2758-2769. |
| [6] | Guo C, Liu S, Sheridan JT. Iterative phase retrieval algorithms. I: optimization. Appl Opt. 2015;54(15):4698-4708. |
| [7] | Liu Z, Guo C, Tan J, et al. Iterative phase-amplitude retrieval with multiple intensity images at output plane of gyrator transforms. J Opt. 2015;17(2):025701. |
| [8] | Guo C, Wei C, Tan J, et al. A review of iterative phase retrieval for measurement and encryption. Opt Lasers Eng. 2016;89:2-12. |
| [9] | Shechtman Y, Beck A, Eldar YC. Gespar: efficient phase retrieval of sparse signals. IEEE Trans Signal Process. 2013;62(4):928-938. · Zbl 1394.94522 |
| [10] | Mukherjee S, Seelamantula CS. An iterative algorithm for phase retrieval with sparsity constraints: application to frequency domain optical coherence tomography. IEEE. 2012;13(14-16):553-556. |
| [11] | Candes EJ, Li X, Soltanolkotabi M. Phase retrieval via wirtinger flow: theory and algorithms. IEEE Trans Inform Theory. 2014;61(4):1985-2007. · Zbl 1359.94069 |
| [12] | Chen Y, Candès E. Solving random quadratic systems of equations is nearly as easy as solving linear systems. Advances in neural information processing systems; Montreal, Canada; 2015. p. 739-747. |
| [13] | Sun J, Qu Q, Wright J. A geometric analysis of phase retrieval. arXiv e-prints; 2016. · Zbl 1401.94049 |
| [14] | Balan R, Casazza P, Dan E. On signal reconstruction without phase. Appl Comput Harmonic Anal. 2006;20(3):345-356. · Zbl 1090.94006 |
| [15] | Bandeira AS, Cahill J, Mixon DG, et al. Saving phase: injectivity and stability for phase retrieval. Appl Comput Harmonic Anal. 2013;37(1):106-125. · Zbl 1305.90330 |
| [16] | Eldar YC, Mendelson S. Phase retrieval: stability and recovery guarantees. Appl Comput Harmonic Anal. 2014;36(3):473-494. · Zbl 06298184 |
| [17] | Wang Z, Lv X, Wang H, et al. Hierarchical multiple binary image encryption based on a chaos and phase retrieval algorithm in the fresnel domain. Laser Phys Lett. 2016;13(3):036201. |
| [18] | Peng W, Wang H. Binary sparse phase retrieval via simulated annealing. Hindawi. 2016;2016(1):1-7. · Zbl 1400.94062 |
| [19] | Wirgin A. Equivalent permittivity of binary objects obtained by inversion of their response to impressed potentials. Inverse Prob Sci Eng. 2016;24(6):1065-1103. · Zbl 1342.78015 |
| [20] | Nakarmi U, Rahnavard N. Bcs: compressive sensing for binary sparse signals. In: Military Communications Conference, 2012 – MILCOM 2012; Orlando, FL; 2012. p. 1-5. |
| [21] | Alpers A, Herman GT, Poulsen HF, et al. Phase retrieval for superposed signals from multiple binary objects. J Opt Soc Am A. 2010;27(9):1927-37. |
| [22] | Osherovich E, Shechtman Y, Szameit A, et al. Sparsity-based single-shot sub-wavelength coherent diffractive imaging. Nat Mater. 2012;11(5):1-4. |
| [23] | Hofstetter EM. Construction of time-limited functions with specified autocorrelation functions. IEEE Trans Inform Theory. 1964;10(2):119-126. · Zbl 0141.15001 |
| [24] | Bruck YuM, Sodin LG. On the ambiguity of the image reconstruction problem. Opt Commun. 1979;30(3):304-308. |
| [25] | Hayes MH. The reconstruction of a multidimensional sequence from the phase or magnitude of its fourier transform. IEEE Trans Acoust Speech Signal Process. 1982;30(2):140-154. · Zbl 0563.65084 |
| [26] | Ranieri J, Chebira A, Lu YM, et al. Phase retrieval for sparse signals: uniqueness conditions. arXiv preprint arXiv:1308.3058; 2013. |
| [27] | Osherovich E. Numerical methods for phase retrieval. arXiv preprint arXiv:1203.4756; 2012. |
| [28] | Jaganathan K, Oymak S, Hassibi B. Sparse phase retrieval: uniqueness guarantees and recovery algorithms. arXiv preprint arXiv:1311.2745; 2013. · Zbl 1414.94273 |
| [29] | Filaseta M, Meade DB. Irreducibility testing of lacunary 0,1-polynomials. J Algorithms. 2005;55(55):21-28. · Zbl 1094.68124 |
| [30] | Newman DJ. An l_1 extremal problem for polynomials. Usp Mat Nauk. 1963;29(1):159-161. |
| [31] | Filaseta M, Matthews M. On the irreducibility of 0,1-polynomials of the form f(x)x^1+g(x). Colloq Math. 2004;99(1):1-5. · Zbl 1060.11066 |
| [32] | Filaseta M. On the factorization of polynomials with small euclidean norm. In: Number theory in progress (Zakopane-Koscielisko, 1997). Vol. 1. Berlin: de Gruyter; 1999. p. 143-163. · Zbl 0928.11015 |
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.
