  A novel approach termed \emph{stochastic truncated amplitude flow} (STAF) is
developed to reconstruct an unknown $n$-dimensional real-/complex-valued signal
$\bm{x}$ from $m$ `phaseless' quadratic equations of the form
$\psi_i=|\langle\bm{a}_i,\bm{x}\rangle|$. This problem, also known as phase
retrieval from magnitude-only information, is \emph{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 is useful when $n$ is large. When $\{\bm{a}_i\}_{i=1}^m$
are independent Gaussian, STAF provably recovers exactly any
$\bm{x}\in\mathbb{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 $\{\bm{a}_i\}$ vectors
demonstrate that STAF empirically reconstructs any $\bm{x}\in\mathbb{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.
