Reshaped Wirtinger Flow for Solving Quadratic System of Equations
We study the problem of recovering a vector $\bx\in \bbR^n$ from its magnitude measurements $y_i=|\langle \ba_i, \bx\rangle|, i=1,..., m$. Our work is along the line of the Wirtinger flow (WF) approach \citet{candes2015phase}, which solves the problem by minimizing a nonconvex loss function via a gradient algorithm and can be shown to converge to a global optimal point under good initialization. In contrast to the smooth loss function used in WF, we adopt a nonsmooth but lower-order loss function, and design a gradient-like algorithm (referred to as reshaped-WF). We show that for random Gaussian measurements, reshaped-WF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is at the order of $\cO(n)$, where $n$ is the dimension of the unknown $\bx$. This improves the sample complexity of WF, and achieves the same sample complexity as truncated-WF \citet{chen2015solving} but without truncation at gradient step. Furthermore, reshaped-WF costs less computationally than WF, and runs faster numerically than both WF and truncated-WF. Bypassing higher-order variables in the loss function and truncations in the gradient loop, analysis of reshaped-WF is simplified.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
We study the phase retrieval problem, which solves quadratic system of equations, i.e., recovers a vector $\boldsymbol{x}\in \mathbb{R}^n$ from its magnitude measurements $y_i=|\langle \boldsymbol{a}_i, \boldsymbol{x}\ra…
RetrievalSolving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
We consider the fundamental problem of solving quadratic systems of equations in $n$ variables, where $y_i = |\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$, $i = 1, \ldots, m$ and $\boldsymbol{x} \in \mathbb{R}^n$…
Phase Retrieval of Quaternion Signal via Wirtinger Flow
The main aim of this paper is to study quaternion phase retrieval (QPR), i.e., the recovery of quaternion signal from the magnitude of quaternion linear measurements. We show that all $d$-dimensional quaternion signals c…
RetrievalPhase Retrieval via Incremental Truncated Wirtinger Flow
In the phase retrieval problem, an unknown vector is to be recovered given quadratic measurements. This problem has received considerable attention in recent times. In this paper, we present an algorithm to solve a nonco…
RetrievalPhase Retrieval via Randomized Kaczmarz: Theoretical Guarantees
We consider the problem of phase retrieval, i.e. that of solving systems of quadratic equations. A simple variant of the randomized Kaczmarz method was recently proposed for phase retrieval, and it was shown numerically …
Retrieval