Phase Retrieval via Sensor Network Localization

doi:10.1007/s40305-018-0222-6

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (1): 127-146.doi: 10.1007/s40305-018-0222-6

Special Issue: Discrete optimization

Previous Articles Next Articles

Phase Retrieval via Sensor Network Localization

Sherry Xue-Ying Ni¹, Man-Chung Yue², Kam-Fung Cheung³, Anthony Man-Cho So¹

1 Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China;
2 Imperial College Business School, Imperial College London, London, UK;
3 Institute of Transport and Logistics Studies, The University of Sydney, Sydney, Australia

Received:2018-02-19 Revised:2018-04-20 Online:2019-03-30 Published:2019-03-30
Contact: Sherry Xue-Ying Ni, Man-Chung Yue, Kam-Fung Cheung, Anthony Man-Cho So E-mail:xyni@se.cuhk.edu.hk;m.yue@imperial.ac.uk;kf.cheung@sydney.edu.au;manchoso@se.cuhk.edu.hk

Abstract

Abstract: The problem of phase retrieval is revisited and studied from a fresh perspective. In particular, we establish a connection between the phase retrieval problem and the sensor network localization problem, which allows us to utilize the vast theoretical and algorithmic literature on the latter to tackle the former. Leveraging this connection, we develop a two-stage algorithm for phase retrieval that can provably recover the desired signal. In both sparse and dense settings, our proposed algorithm improves upon prior approaches simultaneously in the number of required measurements for recovery and the reconstruction time. We present numerical results to corroborate our theory and to demonstrate the efficiency of the proposed algorithm. As a side result, we propose a new form of phase retrieval problem and connect it to the complex rigidity theory proposed by Gortler and Thurston (in:Connelly R, Ivic Weiss A, Whiteley W (eds) Rigidity and symmetry, Springer, New York, pp 131-154, 2014).

Key words: Phase retrieval, Distance geometry, Rigidity theory, Sensor network localization

Sherry Xue-Ying Ni, Man-Chung Yue, Kam-Fung Cheung, Anthony Man-Cho So. Phase Retrieval via Sensor Network Localization[J]. Journal of the Operations Research Society of China, 2019, 7(1): 127-146.

TrendMD

References

[1] Harrison, R.W.:Phase problem in crystallography. J. Opt. Soc. Am. A 10(5), 1046-1055(1993)
[2] Mirhosseini, M., Magaña-Loaiza, O.S., Rafsanjani, S.M.H., Boyd, R.W.:Compressive direct measurement of the quantum wave function. Phys. Rev. Lett. 113(9), 090402(2014)
[3] Fienup, C., Dainty, J.:Phase retrieval and image reconstruction for astronomy. In:Stark, H. (ed.) Image Recovery:Theory and Application, pp. 231-275. Academic Press, New York (1987)
[4] Balan, R.:On signal reconstruction from its spectrogram. In:Proceedings of the 201044th Annual Conference on Information Sciences and Systems (CISS), pp. 1-4. IEEE (2010)
[5] Miao, J., Ishikawa, T., Shen, Q., Earnest, T.:Extending X-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes. Ann. Rev. Phys. Chem. 59, 387-410(2008)
[6] Luke, D.R.:Phase retrieval, what's new. SIAG/OPT Views News. 25(1), 1-5(2017)
[7] 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)
[8] Gerchberg, R.W., Saxton, W.O.:A practical algorithm for the determination of the phase from image and diffraction plane pictures. Optik. 35, 237-246(1972)
[9] Fienup, J.R.:Reconstruction of an object from the modulus of its fourier transform. Opt. Lett. 3(1), 27-29(1978)
[10] Fienup, J.R.:Phase retrieval algorithms:a comparison. Appl. Opt. 21(15), 2758-2769(1982)
[11] Netrapalli, P., Jain, P., Sanghavi, S.:Phase retrieval using alternating minimization. In:Leen, T.K., Dietterich, T.G., Tresp, V. (eds.) Advances in Neural Information Processing Systems, pp. 2796-2804. MIT press (2013)
[12] 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)
[13] Waldspurger, I., d'Aspremont, A., Mallat, S.:Phase recovery, maxcut and complex semidefinite programming. Math. Program. 149(1-2), 47-81(2015)
[14] Li, X., Voroninski, V.:Sparse signal recovery from quadratic measurements via convex programming. SIAM J. Math. Anal. 45(5), 3019-3033(2013)
[15] Iwen, M., Viswanathan, A., Wang, Y.:Fast Phase Retrieval for High-Dimensions. arXiv:1501.02377(2015)
[16] Candès,E.J.,Li,X.,Soltanolkotabi,M.:Phaseretrievalfromcodeddiffractionpatterns.Appl.Comput. Harmon. Anal. 39(2), 277-299(2015)
[17] Alexeev, B., Bandeira, A.S., Fickus, M., Mixon, D.G.:Phase retrieval with polarization. SIAM J. Imaging Sci. 7(1), 35-66(2014)
[18] Pedarsani, R., Yin, D., Lee, K., Ramchandran, K.:PhaseCode:fast and efficient compressive phase retrieval based on sparse-graph codes. IEEE Trans. Inf. Theory 63(6), 3663-3691(2017)
[19] Bandeira, A.S., Cahill, J., Mixon, D.G., Nelson, A.A.:Saving phase:injectivity and stability for phase retrieval. Appl. Comput. Harmon. Anal. 37(1), 106-125(2014)
[20] Fickus, M., Mixon, D.G., Nelson, A.A., Wang, Y.:Phase retrieval from very few measurements. Linear Algebra Appl. 449, 475-499(2014)
[21] Pohl, V., Yang, F., Boche, H.:Phase Retrieval from Low-Rate Samples. arXiv:1311.7045(2013)
[22] Vinzant, C.:A small frame and a certificate of its injectivity. In:Proceedings of the 2015 International Conference on Sampling Theory and Application, pp. 197-200. IEEE (2015)
[23] Zhu, Z., So, A.M.C., Ye, Y.:Universal rigidity:towards accurate and efficient localization of wireless networks. In:Proceedings of the 29th Conference on Computer Communications (INFOCOM 2010), pp. 1-9. IEEE (2010)
[24] Gortler, S.J., Thurston, D.P.:Generic global rigidity in complex and pseudo-Euclidean spaces. In:Connelly, R., Ivic Weiss, A., Whiteley, W. (eds.) Rigidity and Symmetry, pp. 131-154. Springer, New York (2014)
[25] Pedarsani, R., Lee, K., Ramchandran, K.:PhaseCode:Fast and Efficient Compressive Phase Retrieval Based on Sparse-Graph-Codes. arXiv:1408.0034(2014)
[26] Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Morse, A.S., Anderson, B.D.O., Belhumeur, P.N.:Rigidity, computation, and randomization in network localization. In:Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) 4, pp. 2673-2684. IEEE (2004)
[27] Saxe, J.B.:Embeddability of weighted graphs in k-space is strongly NP-hard. In:Proceedings of the 17th Allerton Conference in Communication, Control, and Computing, pp. 480-489(1979)
[28] So, A.M.C., Ye, Y.:Theory of semidefinite programming for sensor network localization. Math. Program. 109(2-3), 367-384(2007)
[29] Aspnes, J., Eren, T., Goldenberg, D.K., Morse, A.S., Whiteley, W., Yang, Y.R., Anderson, B.D., Belhumeur, P.N.:A theory of network localization. IEEE Trans. Mob. Comput. 5(12), 1663-1678(2006)
[30] Jaganathan, K., Eldar, Y.C., Hassibi, B.:Phase Retrieval:An Overview of Recent Developments. arXiv:1510.07713(2015)
[31] Basu, A., Gao, J., Mitchell, J.S.B., Sabhnani, G.:Distributed localization using noisy distance and angle information. In:Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 262-273. ACM (2006)
[32] Zhang, Y., Liu, S., Jia, Z.:Localization using joint distance and angle information for 3D wireless sensor networks. IEEE Commun. Lett. 16(6), 809-811(2012)
[33] Balan, R., Casazza, P., Edidin, D.:On signal reconstruction without phase. Appl. Comput. Harmon. Anal. 20(3), 345-356(2006)

Phase Retrieval via Sensor Network Localization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments