### Abstract

A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complex-valued signal x fromm "phaseless" quadratic equations of the form Ψ_{i} = |ai, x|. This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when n is large. When {a_{i}}^{m} i=1 are independent Gaussian, STAF provably recovers exactly any x ϵ R^{n} exponentially fast based on order of n quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian {ai} vectors demonstrate that STAF empirically reconstructs any x ϵ R^{n} exactly from about 2.3n magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations m = 2n - 1. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

Original language | English (US) |
---|---|

Article number | 7815432 |

Pages (from-to) | 1961-1974 |

Number of pages | 14 |

Journal | IEEE Transactions on Signal Processing |

Volume | 65 |

Issue number | 8 |

DOIs | |

State | Published - Apr 15 2017 |

### Fingerprint

### Keywords

- Kaczmarz algorithm
- Nonconvex optimization
- phase retrieval
- variance reduction

### Cite this

*IEEE Transactions on Signal Processing*,

*65*(8), 1961-1974. [7815432]. https://doi.org/10.1109/TSP.2017.2652392

**Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow.** / Wang, Gang; Giannakis, Georgios B.; Chen, Jie.

Research output: Contribution to journal › Article

*IEEE Transactions on Signal Processing*, vol. 65, no. 8, 7815432, pp. 1961-1974. https://doi.org/10.1109/TSP.2017.2652392

}

TY - JOUR

T1 - Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow

AU - Wang, Gang

AU - Giannakis, Georgios B.

AU - Chen, Jie

PY - 2017/4/15

Y1 - 2017/4/15

N2 - A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complex-valued signal x fromm "phaseless" quadratic equations of the form Ψi = |ai, x|. This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when n is large. When {ai}m i=1 are independent Gaussian, STAF provably recovers exactly any x ϵ Rn exponentially fast based on order of n quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian {ai} vectors demonstrate that STAF empirically reconstructs any x ϵ Rn exactly from about 2.3n magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations m = 2n - 1. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

AB - A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complex-valued signal x fromm "phaseless" quadratic equations of the form Ψi = |ai, x|. This problem, also known as phase retrieval from magnitude-only information, is NP-hard in general. Adopting an amplitude-based nonconvex formulation, STAF leads to an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve a single equation per iteration, thus rendering STAF a simple, scalable, and fast approach amenable to large-scale implementations that are useful when n is large. When {ai}m i=1 are independent Gaussian, STAF provably recovers exactly any x ϵ Rn exponentially fast based on order of n quadratic equations. STAF is also robust in the presence of additive noise of bounded support. Simulated tests involving real Gaussian {ai} vectors demonstrate that STAF empirically reconstructs any x ϵ Rn exactly from about 2.3n magnitude-only measurements, outperforming state-of-the-art approaches and narrowing the gap from the information-theoretic number of equations m = 2n - 1. Extensive experiments using synthetic data and real images corroborate markedly improved performance of STAF over existing alternatives.

KW - Kaczmarz algorithm

KW - Nonconvex optimization

KW - phase retrieval

KW - variance reduction

UR - http://www.scopus.com/inward/record.url?scp=85015039837&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015039837&partnerID=8YFLogxK

U2 - 10.1109/TSP.2017.2652392

DO - 10.1109/TSP.2017.2652392

M3 - Article

AN - SCOPUS:85015039837

VL - 65

SP - 1961

EP - 1974

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 8

M1 - 7815432

ER -