×

Solving phaselift by low-rank Riemannian optimization methods for complex semidefinite constraints. (English) Zbl 1373.65044

Summary: A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers are known to have low rank. This paper considers an approach based on an alternative cost function defined on a union of appropriate manifolds. It is related to the original cost function in a manner that preserves the ability to find a global minimizer and is significantly more efficient computationally. A rank-based optimality condition for stationary points is given and optimization algorithms based on state-of-the-art Riemannian optimization and dynamically reducing rank are proposed. Empirical evaluations are performed using the PhaseLift problem. The new approach is shown to be an effective method of phase retrieval with computational efficiency increased substantially compared to a state-of-the-art algorithm, the Wirtinger flow algorithm. A preliminary version of this paper can be found in the authors’ paper [Procedia Comput. Sci. 80, 1125–1134 (2016)].

MSC:

65K10 Numerical optimization and variational techniques
49N30 Problems with incomplete information (optimization)
49N45 Inverse problems in optimal control
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.-A. Absil, M. Ishteva, L. De Lathauwer, and S. Van Huffel, {\it A geometric Newton method for Oja’s vector field}, Neural Comput., 21 (2009), pp. 1415-33, . · Zbl 1186.65062
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, {\it Optimization Algorithms on Matrix Manifolds}, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043
[3] C. G. Baker, {\it Riemannian Manifold Trust-Region Methods with Applications to Eigenproblems}. PhD thesis, Department of Computational Science, Florida State University, 2008.
[4] S. Becker, E. J. Cand, and M. Grant, {\it Templates for convex cone problems with applications to sparse signal recovery}, Math. Program. Comput., 3 (2011), pp. 165-218. · Zbl 1257.90042
[5] O. Bunk, A. Diaz, F. Pfeiffer, C. David, B. Schmitt, D. K. Satapathy, and J. F. van der Veen, {\it Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels}, Acta Crystallogr. Sect. A, 63 (2007), pp. 306-314, .
[6] R. Blankenbecler, {\it Three-dimensional image reconstruction. II. Hamiltonian method for phase recovery}, Phys. Rev. B, 69 (2004), .
[7] S. Burer and R. D. C. Monteiro, {\it A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization}, Math. Program., 95 (2003), pp. 329-357, . · Zbl 1030.90077
[8] W. M. Boothby, {\it An Introduction to Differentiable Manifolds and Riemannian Geometry}, 2nd ed., Academic Press, New York, 1986. · Zbl 0596.53001
[9] Y. M. Bruck and L. G. Sodin, {\it On the ambiguity of the image recontruction problem}, Optics Commun., 30 (1979), pp. 304-308.
[10] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, . · Zbl 1175.94009
[11] S. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, Cambridge, UK, 2004, . · Zbl 1058.90049
[12] E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski, {\it Phase retrieval via matrix completion}, SIAM J. Imaging Sci., 6 (2013), pp. 199-225, . · Zbl 1280.49052
[13] E. J. Candès and X. Li, {\it Solving quadratic equations via phaselift when there are about as many equations as unknowns}, Found. Comput. Math., 14 (2014), pp. 1017-1026, . · Zbl 1312.90054
[14] E. J. Candés, X. Li, and M. Soltanolkotabi, {\it Phase retrieval via Wirtinger flow: Theory and algorithms}, IEEE Trans. Inform. Theory, 64 (2016), pp. 1985-2007. · Zbl 1359.94069
[15] C. Chen, J. Miao, C. W. Wang, and T. K. Lee, {\it Application of optimization technique to noncrystalline x-ray diffraction microscopy: Guided hybrid input-output method}, Phys. Rev. B, 76 (2007), .
[16] E. J. Candès, T. Strohmer, and V. Voroninski, {\it PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming}, Commun. Pure Appl. Math., 66 (2013), pp. 1241-1274. · Zbl 1335.94013
[17] L. Demanet and P. Hand, {\it Stable optimizationless recovery from phaseless linear measurements}, J. Fourier Anal. Appl., 20 (2014), pp. 199-221. · Zbl 1330.90069
[18] V. Elser, {\it Solution of the crystallographic phase problem by iterated projections}, Acta. Crystallogr. Sect. A, 59 (2003), pp. 201-209.
[19] J. R. Fienup, {\it Reconstruction of an object from the modulus of its Fourier transform}, Optics Lett., 3 (1978), pp. 27-29.
[20] J. R. Fienup, {\it Phase retrieval algorithms: A comparison}, Appl. Optics, 21 (1982), pp. 2758-69.
[21] M. Frigo and S. G. Johnson, {\it The design and implementation of FFTW3}, Proc. IEEE, 93 (2005), pp. 216-231.
[22] R. W. Gerchberg and W. O. Saxton, {\it A practical algorithm for the determination of phase from image and diffraction plane pictures}, Optik, 35 (1972), pp. 237-246.
[23] W. Huang, P.-A. Absil, and K. A. Gallivan, {\it A Riemannian symmetric rank-one trust-region method}, Math. Program., 150 (2015), pp. 179-216. · Zbl 1314.65083
[24] W. Huang, P.-A. Absil, and K. A. Gallivan, {\it A Riemannian BFGS Method for Nonconvex Optimization Problems}, Lect. Notes Comput. Sci. Eng., 112, Springer, New York, 2016, pp. 627-634. · Zbl 1352.65153
[25] W. Huang, P.-A. Absil, and K. A. Gallivan, {\it Intrinsic representation of tangent vectors and vector transport on matrix manifolds}, Numeri. Math., 136 (2017), pp. 523-543. · Zbl 1366.65062
[26] W. Huang, P.-A. Absil, K. A. Gallivan, and P. Hand, {\it ROPTLIB: An Object-Oriented C++ Library for Optimization on Riemannian Manifolds}, Technical Report FSU16-14, Florida State University, 2016. · Zbl 1484.65142
[27] R. W. Harrison, {\it Phase problem in crystallography}, J. Opt. Soc. Amer. A, 10 (1993), pp. 1046-1055, .
[28] M. H. Hayes, {\it The reconstruction of a multidimensional sequence from the phase or magnitude of its Fourier transform}, IEEE Trans. Acoustics Speech Signal process., 30 (1982), pp. 140-154. · Zbl 0563.65084
[29] W. Huang, K. A. Gallivan, and P.-A. Absil, {\it A Broyden class of quasi-Newton methods for Riemannian optimization}, SIAM J. Optim., 25 (2015), pp. 1660-1685. · Zbl 1461.65156
[30] W. Huang, K. A. Gallivan, and X. Zhang, {\it Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints}, UCL-INMA-2015.01.v2, 2016. · Zbl 1373.65044
[31] W. Huang, K. A. Gallivan, and X. Zhang, {\it Solving phaselift by low rank Riemannian optimization methods}, Procedia Comput. Sci., 80 (2016), pp. 1125-1134.
[32] W. Huang, {\it Optimization Algorithms on Riemannian Manifolds with Applications}, PhD thesis, Department of Mathematics, Florida State University, 2013.
[33] M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, {\it Low-rank optimization on the cone of positive semidefinite matrices}, SIAM J. Optim., 20 (2010), pp. 2327-2351. · Zbl 1215.65108
[34] S. Marchesini, {\it Invited article: a unified evaluation of iterative projection algorithms for phase retrieval}, Rev. Sci. Instruments, 78 (2007), .
[35] J. Miao, T. Ishikawa, Q. Shen, and T. Earnest, {\it Extending X-ray crystallography to allow the imaging of noncrystalline materials, cells, and single protein complexes}, Annu. Rev. Physical chemistry, 59 (2008), pp. 387-410, .
[36] Y. Nesterov, {\it Introductory Lectures on Convex Programming: A Basic Course}, Vol. I, Springer, New York, 2004. · Zbl 1086.90045
[37] W. Ring and B. Wirth, {\it Optimization methods on Riemannian manifolds and their application to shape space}, SIAM J. Optim., 22 (2012), pp. 596-627, . · Zbl 1250.90111
[38] J. L. C. Sanz, {\it Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude}, SIAM J. Appl. Math., 45 (1985), pp. 651-664. · Zbl 0569.42009
[39] H. Sato, {\it A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions}, Comput. Optim. Appl., 64 (2016), pp. 101-118. · Zbl 1338.65164
[40] H. Sato and T. Iwai, {\it A new, globally convergent Riemannian conjugate gradient method}, Optimization, 64 (2015), pp. 1011-1031. · Zbl 1311.65072
[41] K. C. Toh, M. J. Todd, and R. H. Tutuncu, {\it SDPT3: A MATLAB software package for semidefinite programming}, Optim. Methods Softw., 11 (1999), pp. 545-581. · Zbl 0997.90060
[42] A. Walther, {\it The question of phase retrieval in optics}, Optica Acta, 10 (1963), pp. 41-49, .
[43] I. Waldspurger, A. D’Aspremont, and S. Mallat, {\it Phase recovery, MaxCut and complex semidefinite programming}, Math. Program., 149 (2015), pp. 47-81, . · Zbl 1329.94018
[44] G. Zhou, W. Huang, K. A. Gallivan, P. Van Dooren, and P.-A. Absil, {\it A Riemannian rank-adaptive method for low-rank optimization}, Neurocomputing, 192 (2016), pp. 72-80.
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.