×

A proximal operator for multispectral phase retrieval problems. (English) Zbl 1448.94083

Summary: Proximal algorithms have gained popularity in recent years in large-scale and distributed optimization problems. One such problem is the phase retrieval problem, for which proximal operators have been proposed recently. The phase retrieval problem commonly refers to the task of recovering a target signal based on the magnitude of linear projections of that signal onto known vectors, usually in the presence of noise. A more general problem is the multispectral phase retrieval problem, where sums of these magnitudes are observed instead. In this paper we study the proximal operator for this problem, which appears in applications like X-ray solution scattering. We show that despite its nonconvexity, all local minimizers are global minimizers, guaranteeing the optimality of simple descent techniques. An efficient linear time exact Newton method is proposed based on the structure of the problem’s Hessian. Initialization criteria are discussed and the computational performance of the proposed algorithm is compared to that of traditional descent methods. The studied proximal operator can be used in distributed and parallel scenarios using proximal implementations and allows for exploiting the spectral characteristics of the problem’s measurement matrices, known in many physical sensing applications, in a way that is not possible with nonsplit optimization algorithms. The dependency of the proximal operator on the rank of these matrices, instead of their dimension, can greatly reduce the memory and computation requirements for problems of moderate to large size \((N>10^4)\) when these measurement matrices admit a low-rank representation.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C25 Convex programming
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM J. Optim., 17 (2006), pp. 844-860, https://doi.org/10.1137/050644471. · Zbl 1128.90044
[2] S. Burer and R. D. C. Monteiro, Local minima and convergence in low-rank semidefinite programming, Math. Program., 103 (2005), pp. 427-444, https://doi.org/10.1007/s10107-004-0564-1. · Zbl 1099.90040
[3] E. Candes, X. Li, and M. Soltanolkotabi, Phase retrieval via Wirtinger flow: Theory and algorithms, IEEE Trans. Inf. Theory, 61 (2015), pp. 1985-2007, https://doi.org/10.1109/TIT.2015.2399924. · Zbl 1359.94069
[4] E. J. Candes, Y. Eldar, T. Strohmer, and V. Voroninski, Phase Retrieval via Matrix Completion, preprint, http://arxiv.org/abs/1109.0573, 2011. · Zbl 1280.49052
[5] E. J. Candès, T. Strohmer, and V. Voroninski, PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66 (2013), pp. 1241-1274, https://doi.org/10.1002/cpa.21432. · Zbl 1335.94013
[6] Y. Chen and E. J. Candès, Solving random quadratic systems of equations is nearly as easy as solving linear systems, Comm. Pure Appl. Math., 70 (2017), pp. 822-883, https://doi.org/10.1002/cpa.21638. · Zbl 1379.90024
[7] P. L. Combettes and J. C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer Optim. Appl. 49, Springer, Cham, 2011, pp. 185-212, https://doi.org/10.1007/978-1-4419-9569-8_10. · Zbl 1242.90160
[8] J. R. Fienup, Reconstruction of an object from the modulus of its Fourier transform, Optics Lett., 3 (1978), pp. 27-29, https://doi.org/10.1364/OL.3.000027.
[9] J. R. Fienup, Phase retrieval algorithms: A comparison, Appl. Optim., 21 (1982), pp. 2758-2769.
[10] F. Fogel, I. Waldspurger, and A. D’Aspremont, Phase retrieval for imaging problems, Math. Program. Comput., 8 (2016), pp. 311-335, https://doi.org/10.1007/s12532-016-0103-0. · Zbl 1349.94060
[11] R. W. Gerchberg and W. O. Saxton, A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, 35 (1972), pp. 237-246.
[12] G. H. Golub, Some modified matrix eigenvalue problems, SIAM Rev., 15 (1973), pp. 318-334, https://doi.org/10.1137/1015032. · Zbl 0254.65027
[13] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, MD, 2012.
[14] R. A. Hauser and A. Eftekhari, PCA by optimisation of symmetric functions has no spurious local optima, in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2018, pp. 1504-1511, https://doi.org/10.1145/3219819.3220069.
[15] K. Huang, Y. C. Eldar, and N. D. Sidiropoulos, Phase retrieval from \(1\) D Fourier measurements: Convexity, uniqueness, and algorithms, IEEE Trans. Signal Process., 64 (2016), pp. 6105-6117, https://doi.org/10.1109/TSP.2016.2601291. · Zbl 1414.94252
[16] P. V. Konarev, V. V. Volkov, A. V. Sokolova, M. H. J. Koch, and D. I. Svergun, PRIMUS: A Windows PC-based system for small-angle scattering data analysis, J. Appl. Crystallogr., 36 (2003), pp. 1277-1282, https://doi.org/10.1107/S0021889803012779.
[17] X. Li and V. Voroninski, Sparse signal recovery from quadratic measurements via convex programming, SIAM J. Math. Anal., 45 (2013), pp. 3019-3033, https://doi.org/10.1137/120893707. · Zbl 1320.94023
[18] S. Mukherjee, S. Shit, and C. S. Seelamantula, Phasesplit: A variable splitting framework for phase retrieval, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE Press, Piscataway, NJ, 2018, pp. 4709-4713.
[19] N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optim., 1 (2014), pp. 127-239.
[20] B. Roig-Solvas and L. Makowski, Calculation of the cross-sectional shape of a fibril from equatorial scattering, J. Struct. Biol., 200 (2017), pp. 248-257, https://doi.org/10.1016/j.jsb.2017.05.003.
[21] A. Schutz, A. Ferrari, D. Mary, F. Soulez, É. Thiébaut, and M. Vannier, PAINTER: A spatiospectral image reconstruction algorithm for optical interferometry, J. Opt. Soc. Am. A, 31 (2014), pp. 2334-2345, https://doi.org/10.1364/JOSAA.31.002334.
[22] Y. Shechtman, A. Beck, and Y. C. Eldar, GESPAR: Efficient phase retrieval of sparse signals, IEEE Trans. Signal Process., 62 (2014), pp. 928-938, https://doi.org/10.1109/TSP.2013.2297687. · Zbl 1394.94522
[23] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev, Phase retrieval with application to optical imaging: A contemporary overview, IEEE Signal Process. Mag., 32 (2015), pp. 87-109.
[24] F. Soulez, É. Thiébaut, A. Schutz, A. Ferrari, F. Courbin, and M. Unser, Proximity operators for phase retrieval, Appl. Optics, 55 (2016), pp. 7412-7421, https://doi.org/10.1364/AO.55.007412.
[25] I. Waldspurger, A. D’Aspremont, and S. Mallat, Phase recovery, MaxCut and complex semidefinite programming, Math. Program., 149 (2013), pp. 47-81. · Zbl 1329.94018
[26] D. S. Weller, A. Pnueli, G. Divon, O. Radzyner, Y. C. Eldar, and J. A. Fessler, Undersampled phase retrieval with outliers, IEEE Trans. Comput. Imag., 1 (2015), pp. 247-258.
[27] D. S. Weller, A. Pnueli, O. Radzyner, G. Divon, Y. C. Eldar, and J. A. Fessler, Phase retrieval of sparse signals using optimization transfer and ADMM, in Proceedings of the 2014 IEEE International Conference on Image Processing, IEEE Press, Piscataway, NJ, 2014, pp. 1342-1346, https://doi.org/10.1109/ICIP.2014.7025268.
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.