Timezone: »
Poster
Approximate message passing for amplitude based optimization
Junjie Ma · Ji Xu · Arian Maleki
We consider an $\ell_2$regularized nonconvex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty$, $m/n \rightarrow \delta$ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals the algorithm can perform accurate recovery with only $m=\left ( \frac{64}{\pi^2}4\right)n\approx 2.5n$ measurements. Also, we provide sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: (i) Adding $\ell_2$ regularization to the nonconvex loss function can be beneficial even in the noiseless setting; (ii) spectral initialization has marginal impact on the performance of the algorithm.
Author Information
Junjie Ma (Columbia University)
Ji Xu (Columbia University)
Arian Maleki (Columbia)
Related Events (a corresponding poster, oral, or spotlight)

2018 Oral: Approximate message passing for amplitude based optimization »
Thu Jul 12th 02:00  02:20 PM Room A9
More from the Same Authors

2018 Poster: Approximate LeaveOneOut for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni 
2018 Oral: Approximate LeaveOneOut for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni