In this thesis, we study the sparse phase retrieval problem, which is to reconstruct the sparse signal x^♮ with ∥x^♮∥₀ ≤ s from its intensity-only measurements y_i = ∣a_i^T x^♮∣ for i = 1,2,…,m. The sparse phase retrieval problem arises in many applications in scientific imaging, such as bio-imaging systems, astronomical imaging, diffraction imaging and optics. The existing sparse phase retrieval algorithms are mostly first-order methods and merit a linear convergence property. However, there are only a few second-order algorithms for sparse phase retrieval. To mitigate this gap, we propose two second-order algorithms in this thesis.

The first approach is the Newton Hard Thresholding Pursuit (NHTP) algorithm, which is a provable second-order algorithm. Theoretical analysis show that NHTP conv...[ Read more ]

In this thesis, we study the sparse phase retrieval problem, which is to reconstruct the sparse signal x^♮ with ∥x^♮∥₀ ≤ s from its intensity-only measurements y_i = ∣a_i^T x^♮∣ for i = 1,2,…,m. The sparse phase retrieval problem arises in many applications in scientific imaging, such as bio-imaging systems, astronomical imaging, diffraction imaging and optics. The existing sparse phase retrieval algorithms are mostly first-order methods and merit a linear convergence property. However, there are only a few second-order algorithms for sparse phase retrieval. To mitigate this gap, we propose two second-order algorithms in this thesis.

The first approach is the Newton Hard Thresholding Pursuit (NHTP) algorithm, which is a provable second-order algorithm. Theoretical analysis show that NHTP converges at least linearly and merits a quadratic convergence after O(log(∥x^♮∥/x^♮_min)) iterations. The sparse spectral initialization method is employed for a close initial guess. Numerical simulations confirm the efficiency of the proposed NHTP algorithm in terms of sample complexity and running time. The second approach is the Primal Dual Active Set algorithm with Continuation (PDASC). Practically, the sparsity level of the underlying signal is unknown.

However, the development of most algorithms for sparse phase retrieval are based on the knowledge of the sparsity. PDASC is developed to reconstruct the signal without knowing sparsity level. We show that the update rule for PDASC can be interpreted as a Newton's method. Also, a novel initialization method which does not require the sparsity level as a prior knowledge is proposed. The effectiveness of the new initialization method is guaranteed both empirically and theoretically. Extensive experiments on both synthetic data and natural images confirm the efficiency of the proposed PDASC algorithm.