Abstract
We study the problem of recovering a t-sparse vector ±x0 in R^n from m quadratic equations yi = (a^T_i x)^2 with noisy measurements y_i’s. This is known as the problem of compressive phase retrieval, and has been widely applied to Xray diffraction imaging, microscopy, quantum mechanics, etc. The challenge is to design a a) fast and b) noise-tolerant algorithms with c) near-optimal sample complexity. Prior work in this direction typically achieved one or two of these goals, but none of them enjoyed the three performance guarantees simultaneously. In this work, with a particular set of sensing vectors ai’s, we give a provable algorithm that is robust to any bounded yet unstructured deterministic noise. Our algorithm requires roughly O(t) measurements and runs in O(tn log(1/eps)) time, where eps is the error. This result advances the state-of-the-art work, and guarantees the applicability of our method to large datasets. Experiments on synthetic and real data verify our theory.