Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval. (English) Zbl 1481.90260


90C26 Nonconvex programming, global optimization
90C90 Applications of mathematical programming


FTVd; Wirtinger Flow
Full Text: DOI arXiv


[1] 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, 87-109 (2015)
[2] Chen, P.; Fannjiang, A.; Liu, G., Phase retrieval with one or two coded diffraction patterns by alternating projection with the null initialization, J. Fourier Anal. Appl., 24, 719-758 (2017) · Zbl 1478.65145
[3] Gerchberg, R. W.; Saxton, W. O., A practical algorithm for the determination of phase from image and diffraction plane pictures, Optik, 35, 237-246 (1972)
[4] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization (2013)
[5] Chen, Y.; Candes, E. J., Solving random quadratic systems of equations is nearly as easy as solving linear systems (2015)
[6] Candes, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval via wirtinger flow: theory and algorithms, IEEE Trans. Inform. Theory, 61, 1985-2007 (2015) · Zbl 1359.94069
[7] Zhang, H.; Liang, Y.; Lee, D.; Sugiyama, M.; Luxburg, U.; Guyon, I.; Garnett, R., Reshaped wirtinger flow for solving quadratic system of equations, Advances in Neural Information Processing Systems, vol 29, 2630-2638 (2016)
[8] Chen, P.; Fannjiang, A.; Liu., G., Phase retrieval by linear algebra, SIAM J. Matrix Anal. Appl., 38, 864-868 (2017) · Zbl 1375.49035
[9] Luo, W.; Alghamdi, W.; Lu, Y. M., Optimal spectral initialization for signal recovery with applications to phase retrieval (2018)
[10] Lu, Y. M.; Li, G., Phase transitions of spectral initialization for high-dimensional nonconvex estimation (2017)
[11] Mondelli, M.; Montanari, A., Fundamental limits of weak recovery with applications to phase retrieval, Found. Comput. Math., 19, 703-773 (2019) · Zbl 1464.62296
[12] Duchi, J. C.; Ruan, F., Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval, Inf. Inference: J. IMA, 8, 471-529 (2019) · Zbl 1478.90084
[13] Fienup, J. R., Phase retrieval algorithms: a comparison, Appl. Opt., 21, 2758-2769 (1982)
[14] Fienup, J. R., Phase retrieval algorithms: a personal tour (invited), Appl. Opt., 52, 45-56 (2013)
[15] Bauschke, H. H.; Combettes, P. L.; Luke, D. R., Hybrid projection-reflection method for phase retrieval, J. Opt. Soc. Am. A, 20, 1025-1034 (2003)
[16] Chen, P.; Fannjiang, A., Fourier phase retrieval with a single mask by Douglas-Rachford algorithms, Appl. Comput. Harmon. Anal., 44, 665-699 (2018) · Zbl 06858981
[17] Wen, Z.; Yang, C.; Liu, X.; Marchesini, S., Alternating direction methods for classical and ptychographic phase retrieval, Inverse Problems, 28 (2012) · Zbl 1254.78037
[18] Luke, D. R., Relaxed averaged alternating reflections for diffraction imaging, Inverse Problems, 21, 37-50 (2004) · Zbl 1146.78008
[19] Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073
[20] He, B.; Yuan, X., On the convergence rate of Douglas-Rachford operator splitting method, Math. Program., 153, 715-722 (2015) · Zbl 1327.90211
[21] Li, J.; Zhou, T., On relaxed averaged alternating reflections (RAAR) algorithm for phase retrieval with structured illumination, Inverse Problems, 33 (2017) · Zbl 1360.78027
[22] Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods (1996), Belmont, MA: Athena Scientific, Belmont, MA
[23] Hong, M.; Luo, Z-Q; Razaviyayn, M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26, 337-364 (2016) · Zbl 1356.49061
[24] Li, G.; Pong, T. K., Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25, 2434-2460 (2015) · Zbl 1330.90087
[25] Wang, Y.; Yin, W.; Zeng, J., Global convergence of ADMM in nonconvex nonsmooth optimization, J. Sci. Comput., 78, 29-63 (2019) · Zbl 1462.65072
[26] Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods (2014), Amsterdam: Elsevier, Amsterdam
[27] Boyd, S.; Parikh, N.; Chu, E.; Borja, P.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122 (2011) · Zbl 1229.90122
[28] Sun, J.; Qu, Q.; Wright, J., A geometric analysis of phase retrieval, 2379-2383 (2016)
[29] Lee, J. D.; Simchowitz, M.; Jordan, M. I.; Recht, B.; Feldman, V.; Rakhlin, A.; Shamir, O., Gradient descent only converges to minimizers, Proceedings of Machine Learning Research (PMLR) vol 49, 1246-1257 (2016), New York, USA: Columbia University, New York, USA
[30] Du, S. S.; Jin, C.; Lee, J. D.; Jordan, M. I.; Singh, A.; Poczos, B.; Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; Garnett, R., Gradient descent can take exponential time to escape saddle points, Advances in Neural Information Processing Systems, vol 30, 1067-1077 (2017)
[31] Jin, C.; Ge, R.; Netrapalli, P.; Kakade, S. M.; Jordan, M. I., How to escape saddle points efficiently, 2727-2752 (2017)
[32] Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; Bengio, Y., Generative adversarial networks, Commun. ACM, 63, 139-144 (2020)
[33] Omidshafiei, S.; Pazis, J.; Amato, C.; How, J. P.; Vian, J., Deep decentralized multi-task multi-agent reinforcement learning under partial observability (2017)
[34] Leonard, A.; Daneshmand, H.; Lucchi, A.; Hofmann, T., Local saddle point optimization: a curvature exploitation approach, 486-495 (2019)
[35] Daskalakis, C.; Panageas, I., The limit points of (optimistic) gradient descent in min-max optimization, Advances in Neural Information Processing Systems, vol 31, 9256-9266 (2018)
[36] Jin, C.; Netrapalli, P.; Jordan, M., What is local optimality in nonconvex-nonconcave minimax optimization?, 4880-4889 (2020)
[37] Dai, Y-H; Zhang, L., Optimality conditions for constrained minimax optimization, CSIAM Trans. Appl. Math., 1, 296-315 (2020)
[38] Albert, F., Absolute uniqueness of phase retrieval with random illumination, Inverse Problems, 28 (2012) · Zbl 1250.78024
[39] Albert, F.; Zhang, Z., Fixed point analysis of Douglas-Rachford splitting for ptychography and phase retrieval, SIAM J. Imaging Sci., 13, 609-650 (2020) · Zbl 1461.65150
[40] Glowinski, R.; Marroco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires, ESAIM: Math. Modelling Numer. Anal., 9, 41-76 (1975) · Zbl 0368.65053
[41] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034
[42] Yang, J.; Zhang, Y.; Yin, W., An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM J. Sci. Comput., 31, 2842-2865 (2009) · Zbl 1195.68110
[43] Deka, B.; Datta, S., Compressed Sensing Magnetic Resonance Image Reconstruction Algorithms (2019), Berlin: Springer, Berlin
[44] Cherukuri, A.; Gharesifard, B.; Cortés, J., Saddle-point dynamics: conditions for asymptotic stability of saddle points, SIAM J. Control Optim., 55, 486-511 (2017) · Zbl 1364.90326
[45] Thibault, P.; Guizar-Sicairos, M., Maximum-likelihood refinement for coherent diffractive imaging, New J. Phys., 14 (2012)
[46] Chang, H.; Lou, Y.; Ng, M. K.; Zeng, T., Phase retrieval from incomplete magnitude information via total variation regularization, SIAM J. Sci. Comput., 38, A3672-A3695 (2016) · Zbl 1352.49034
[47] Eldar, Y. C.; Mendelson, S., Phase retrieval: stability and recovery guarantees, Appl. Comput. Harmon. Anal., 36, 473-494 (2014) · Zbl 06298184
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.