PhaseCode: Fast and Efficient Compressive Phase Retrieval Based on Sparse-Graph Codes

摘要: We consider the problem of recovering a complex signal $ {x} \in \mathbb {C}^{n}$ from $m$ intensity measurements form | {a}_{i} ^{\mathrm{ H}} {x}|, ~1 \leq i m$ , where H}}$ is $i$ th row measurement matrix {A} {C}^{m \times n}$ . Our main focus on case vectors are unconstrained, and {x}$ exactly $K$ -sparse, or so-called general compressive phase retrieval problem. introduce PhaseCode novel family fast efficient algorithms that based sparse-graph coding framework. show in noiseless case, algorithm can recover an arbitrarily-close-to-one fraction nonzero components using only slightly more than $4K$ when support uniformly random, with order-optimal time memory complexity $\Theta (K)$ 1 It known fundamental limit for number $4K - o(K)$ difficult no assumptions its distribution. This shows under mild relaxation conditions, our first constructive capacity-approaching algorithm: fact, also memory. Furthermore, we any random $(1 p)$ -fraction high probability, $p$ be made arbitrarily close to zero, sample $m = c(p)K$ $c(p)$ small constant depending precisely calculated, optimal complexity. As result, assuming lower bounded by (1)$ upper (K^{\gamma })$ some positive $\gamma able provide strong $\ell _{1}$ guarantee estimated $\hat { {x}}$ as follows: $\| \hat {x}} {x}\|_{1} p \| \|_{1}(1 + o(1))$ zero. one instance, provably recover, $1 10^{-7}$ significant components, at most 14K$ measurements. Next, motivated important practical classes optical systems, “Fourier-friendly” constrained setting, performance matches unconstrained sparse Fourier domain uniform support. In Fourier-friendly setting consider, cascade matrices (corresponding lenses) diagonal diffraction mask patterns). Finally, tackle presence noise, $y_{i}= {x}|^{2}+w_{i}$ $w_{i}$ additive noise measurement. assume quantized, each component take $L_{m}$ possible magnitudes $L_{p}$ phases. regime, $K=\beta n^\delta $\delta (0,1)$ use same architecture robustify it two schemes: almost-linear scheme sublinear scheme. prove recovers (K \log (n))$ computational (L_{m} L_{p} n (K\log ^{3}(n))$ K\log Throughout, extensive simulation results validate power proposed settings, noisy scenarios. Here, define notation \mathcal {O}(\cdot )$ (\cdot $\Omega have $f= {O}(g)$ if there exists $C_{1}>0$ such \left |{f/g}\right ; $f=\Theta (g)$ exist constants $C_{1},C_{2}>0$ $C_{1} $f=\Omega |>C_{1}$