research-article

Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints

Authors:

K. A. Gallivan,

Xiangxiong ZhangAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 39, Issue 5

Pages B840 - B859

https://doi.org/10.1137/16M1072838

Published: 01 January 2017 Publication History

Abstract

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 [W. Huang, K. A. Gallivan, and X. Zhang, Procedia Comput. Sci., 80 (2016), pp. 1125--1134].

References

[1]

P.-A. Absil, M. Ishteva, L. De Lathauwer, and S. Van Huffel, A geometric Newton method for Oja's vector field, Neural Comput., 21 (2009), pp. 1415--33, https://doi.org/10.1162/neco.2008.04-08-749.

[2]

P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008.

[3]

C. G. Baker, 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, Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput., 3 (2011), pp. 165--218.

[5]

O. Bunk, A. Diaz, F. Pfeiffer, C. David, B. Schmitt, D. K. Satapathy, and J. F. van der Veen, Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallogr. Sect. A, 63 (2007), pp. 306--314, https://doi.org/10.1107/S0108767307021903.

[6]

R. Blankenbecler, Three-dimensional image reconstruction. II. Hamiltonian method for phase recovery, Phys. Rev. B, 69 (2004), https://doi.org/10.1103/PhysRevB.69.064108.

[7]

S. Burer and R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95 (2003), pp. 329--357, https://doi.org/10.1007/s10107-002-0352-8.

[8]

W. M. Boothby, An Introduction to Differentiable Manifolds and Riemannian Geometry, 2nd ed., Academic Press, New York, 1986.

[9]

Y. M. Bruck and L. G. Sodin, On the ambiguity of the image recontruction problem, Optics Commun., 30 (1979), pp. 304--308.

[10]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183--202, https://doi.org/10.1137/080716542.

[11]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004, https://doi.org/10.1017/CBO9780511804441.

[12]

E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski, Phase retrieval via matrix completion, SIAM J. Imaging Sci., 6 (2013), pp. 199--225, arXiv:1109.0573v2.

[13]

E. J. Candès and X. Li, Solving quadratic equations via phaselift when there are about as many equations as unknowns, Found. Comput. Math., 14 (2014), pp. 1017--1026, https://doi.org/10.1007/s10208-013-9162-z.

[14]

E. J. Candés, X. Li, and M. Soltanolkotabi, Phase retrieval via Wirtinger flow: Theory and algorithms, IEEE Trans. Inform. Theory, 64 (2016), pp. 1985--2007.

[15]

C. Chen, J. Miao, C. W. Wang, and T. K. Lee, Application of optimization technique to noncrystalline x-ray diffraction microscopy: Guided hybrid input-output method, Phys. Rev. B, 76 (2007), https://doi.org/10.1103/PhysRevB.76.064113.

[16]

E. J. Candès, T. Strohmer, and V. Voroninski, PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66 (2013), pp. 1241--1274.

[17]

L. Demanet and P. Hand, Stable optimizationless recovery from phaseless linear measurements, J. Fourier Anal. Appl., 20 (2014), pp. 199--221.

[18]

V. Elser, Solution of the crystallographic phase problem by iterated projections, Acta. Crystallogr. Sect. A, 59 (2003), pp. 201--209.

[19]

J. R. Fienup, Reconstruction of an object from the modulus of its Fourier transform, Optics Lett., 3 (1978), pp. 27--29.

[20]

J. R. Fienup, Phase retrieval algorithms: A comparison, Appl. Optics, 21 (1982), pp. 2758--69.

[21]

M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proc. IEEE, 93 (2005), pp. 216--231.

[22]

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.

[23]

W. Huang, P.-A. Absil, and K. A. Gallivan, A Riemannian symmetric rank-one trust-region method, Math. Program., 150 (2015), pp. 179--216.

[24]

W. Huang, P.-A. Absil, and K. A. Gallivan, A Riemannian BFGS Method for Nonconvex Optimization Problems, Lect. Notes Comput. Sci. Eng., 112, Springer, New York, 2016, pp. 627--634.

[25]

W. Huang, P.-A. Absil, and K. A. Gallivan, Intrinsic representation of tangent vectors and vector transport on matrix manifolds, Numeri. Math., 136 (2017), pp. 523--543.

[26]

W. Huang, P.-A. Absil, K. A. Gallivan, and P. Hand, ROPTLIB: An Object-Oriented C++ Library for Optimization on Riemannian Manifolds, Technical Report FSU16-14, Florida State University, 2016.

[27]

R. W. Harrison, Phase problem in crystallography, J. Opt. Soc. Amer. A, 10 (1993), pp. 1046--1055, https://doi.org/10.1364/JOSAA.10.001046.

[28]

M. H. Hayes, 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.

[29]

W. Huang, K. A. Gallivan, and P.-A. Absil, A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM J. Optim., 25 (2015), pp. 1660--1685.

[30]

W. Huang, K. A. Gallivan, and X. Zhang, Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints, UCL-INMA-2015.01.v2, 2016.

[31]

W. Huang, K. A. Gallivan, and X. Zhang, Solving phaselift by low rank Riemannian optimization methods, Procedia Comput. Sci., 80 (2016), pp. 1125--1134.

[32]

W. Huang, Optimization Algorithms on Riemannian Manifolds with Applications, PhD thesis, Department of Mathematics, Florida State University, 2013.

[33]

M. Journée, F. Bach, P.-A. Absil, and R. Sepulchre, Low-rank optimization on the cone of positive semidefinite matrices, SIAM J. Optim., 20 (2010), pp. 2327--2351.

[34]

S. Marchesini, Invited article: a unified evaluation of iterative projection algorithms for phase retrieval, Rev. Sci. Instruments, 78 (2007), https://doi.org/10.1063/1.2403783.

[35]

J. Miao, T. Ishikawa, Q. Shen, and T. Earnest, 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, https://doi.org/10.1146/annurev.physchem.59.032607.093642.

[36]

Y. Nesterov, Introductory Lectures on Convex Programming: A Basic Course, Vol. I, Springer, New York, 2004.

[37]

W. Ring and B. Wirth, Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optim., 22 (2012), pp. 596--627, https://doi.org/10.1137/11082885X.

[38]

J. L. C. Sanz, Mathematical considerations for the problem of Fourier transform phase retrieval from magnitude, SIAM J. Appl. Math., 45 (1985), pp. 651--664.

[39]

H. Sato, A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions, Comput. Optim. Appl., 64 (2016), pp. 101--118.

[40]

H. Sato and T. Iwai, A new, globally convergent Riemannian conjugate gradient method, Optimization, 64 (2015), pp. 1011--1031.

[41]

K. C. Toh, M. J. Todd, and R. H. Tutuncu, SDPT3: A MATLAB software package for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 545--581.

[42]

A. Walther, The question of phase retrieval in optics, Optica Acta, 10 (1963), pp. 41--49, https://doi.org/10.1080/713817747.

[43]

I. Waldspurger, A. D'Aspremont, and S. Mallat, Phase recovery, MaxCut and complex semidefinite programming, Math. Program., 149 (2015), pp. 47--81, https://doi.org/10.1007/s10107-013-0738-9.

[44]

G. Zhou, W. Huang, K. A. Gallivan, P. Van Dooren, and P.-A. Absil, A Riemannian rank-adaptive method for low-rank optimization, Neurocomputing, 192 (2016), pp. 72--80.

Cited By

Luo YHuang WLi XZhang A(2024)Recursive Importance Sketching for Rank Constrained Least SquaresOperations Research10.1287/opre.2023.244572:1(237-256)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2023.2445
Luo YLi XZhang A(2024)On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix OptimizationMathematics of Operations Research10.1287/moor.2023.137749:2(782-825)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/moor.2023.1377
Li YSun X(2024)Sensor Network Localization via Riemannian Conjugate Gradient and Rank ReductionIEEE Transactions on Signal Processing10.1109/TSP.2024.337837872(1910-1927)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3378378

Recommendations

Solving PhaseLift by Low-rank Riemannian Optimization Methods1

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 paper considers an approach ...
A Riemannian rank-adaptive method for low-rank matrix completion
Abstract
The low-rank matrix completion problem can be solved by Riemannian optimization on a fixed-rank manifold. However, a drawback of the known approaches is that the rank parameter has to be fixed a priori. In this paper, we consider the optimization ...
Riemannian Preconditioning

This paper exploits a basic connection between sequential quadratic programming and Riemannian gradient optimization to address the general question of selecting a metric in Riemannian optimization, in particular when the Riemannian structure is sought on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 39, Issue 5

^† Special Section: 2016 Copper Mountain Conference

2017

1763 pages

ISSN:1064-8275

DOI:10.1137/sjoce3.39.5

Issue’s Table of Contents

© 2017, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2017

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo YHuang WLi XZhang A(2024)Recursive Importance Sketching for Rank Constrained Least SquaresOperations Research10.1287/opre.2023.244572:1(237-256)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2023.2445
Luo YLi XZhang A(2024)On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix OptimizationMathematics of Operations Research10.1287/moor.2023.137749:2(782-825)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/moor.2023.1377
Li YSun X(2024)Sensor Network Localization via Riemannian Conjugate Gradient and Rank ReductionIEEE Transactions on Signal Processing10.1109/TSP.2024.337837872(1910-1927)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3378378
Huang WGallivan K(2022)A Limited-Memory Riemannian Symmetric Rank-One Trust-Region Method with a Restart StrategyJournal of Scientific Computing10.1007/s10915-022-01962-093:1Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10915-022-01962-0

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents