Fast rank-one alternating minimization algorithm for phase retrieval

DOI10.1007/S10915-018-0857-9MaRDI QIDQ2000029zbMATH OpenOpenAlexWikidataFDO

Authors Haixia Liu, Yang Wang, Jian-Feng Cai

Publication date 27 June 2019

Published in Journal of Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08751

zbMATH Keywords

alternating gradient descentalternating minimizationnon-convex optimizatonphase retrievalrank-one

Mathematics Subject Classification ID

Numerical methods in Fourier analysis (65T99) Nonconvex programming, global optimization (90C26) Applications of mathematical programming (90C90) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The phase retrieval problem is a fundamental problem in many fields, which is appealing for investigation. It is to recover the signal vector $ildexinmathbb{C}^d$ from a set of $N$ measurements $b_n=|f_n^{\ast }ildex{|}^2,n=1,cdots,N$, where ${f_n}_{n=1}^N$ forms a frame of $mathbb{C}^d$. %It is generally a non-convex minimization problem, which is NP-hard. Existing algorithms usually use a least squares fitting to the measurements, yielding a quartic polynomial minimization. In this paper, we employ a new strategy by splitting the variables, and we solve a bi-variate optimization problem that is quadratic in each of the variables. An alternating gradient descent algorithm is proposed, and its convergence for any initialization is provided. Since a larger step size is allowed due to the smaller Hessian, the alternating gradient descent algorithm converges faster than the gradient descent algorithm (known as the Wirtinger flow algorithm) applied to the quartic objective without splitting the variables. Numerical results illustrate that our proposed algorithm needs less iterations than Wirtinger flow to achieve the same accuracy.

Recommendations

• Phase retrieval using alternating minimization in a batch setting
• Phase retrieval via Wirtinger flow: theory and algorithms
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
• Phase retrieval for sub-Gaussian measurements

Cites work

• A flexible convex relaxation for phase retrieval
• A geometric analysis of phase retrieval
• Array imaging using intensity-only measurements
• Guarantees of Riemannian optimization for low rank matrix recovery
• Low rank matrix completion by alternating steepest descent methods
• Low-rank matrix completion using alternating minimization
• Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers
• On signal reconstruction without phase
• Painless reconstruction from magnitudes of frame coefficients
• Phase recovery, MaxCut and complex semidefinite programming
• Phase Retrieval Using Alternating Minimization
• Phase retrieval via matrix completion
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval with polarization
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Quantum tomography under prior information
• Robust sparse phase retrieval made easy
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

Cited in

(13)

• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• Phase retrieval for sub-Gaussian measurements
• Phase retrieval using alternating minimization in a batch setting
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• A brief introduction to manifold optimization
• Steklov convexification and a trajectory method for global optimization of multivariate quartic polynomials
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• scientific article; zbMATH DE number 7295466 (Why is no real title available?)
• Accelerated Alternating Projections for Robust Principal Component Analysis
• Finding robust minimizer for non-convex phase retrieval
• A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
• Adaptive trust-region method on Riemannian manifold
• Riemannian trust region methods for \(\mathrm{SC}^1\) minimization

Describes a project that uses

Uses Software

• PhaseLift
• Wirtinger Flow
• SparsePR
• PhaseMax

This page was built for publication: Fast rank-one alternating minimization algorithm for phase retrieval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000029)