Fast Compressive Phase Retrieval under Bounded Noise

• Main Authors: Zhang, Hongyang, You, Shan, Lin, Zhouchen, Xu, Chao
• Format: Conference Proceeding
• Language: English
• ISSN: 2159-5399; 2374-3468
• DOI: 10.1609/aaai.v31i1.10876

We study the problem of recovering a t-sparse real vector from m quadratic equations yi=(ai*x)^2 with noisy measurements yi's. This is known as the problem of compressive phase retrieval, and has been widely applied to X-ray 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/epsilon)) time, where epsilon 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.