The following paper is hypnotic. Why ? Because had we not have a sharp phase transition, a somehow objective limit to our current knowledge, we couldn't compare the different algorithms out there and this paper would just be presenting just one algorithm against another. With the sharp phase transitions, we get to decide as a reader, that yes, I want to use this algorithm in the future because it is indeed the better solution. The second aspect of this is that they compare it with a sparse implementation of the Fienup algorithm. The algorithms by Fienup have been the mainstay of phase retrieval since the first paper came out in the mid-1980s and one isn't sure what signal structure is being reconstructed.
As an aside, James Fienup is known among other things for performing the characterization of the, then, faulty Hubble telescope [1-3] and you know how much the whole repair mission (Service Mission 1 or SM-1) hinged on me throwing the wrong M&Ms :-).
Without further due here is the rapid and most phase transition busting algorithm in phase retrieval:
Compressive Phase Retrieval via Generalized Approximate Message Passing by Philip Schniter, Sundeep Rangan
In phase retrieval, the goal is to recover a signal $\boldsymbol{x}\in\mathbb{C}^N$ from the magnitudes of linear measurements $\boldsymbol{Ax}\in\mathbb{C}^M$. While recent theory has established that $M\approx 4N$ intensity measurements are necessary and sufficient to recover generic $\boldsymbol{x}$, there is great interest in reducing the number of measurements through the exploitation of sparse $\boldsymbol{x}$, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. For example, to successfully recover $K$-sparse signals, approximately $M\geq 2K\log_2(N/K)$ intensity measurements suffice when $K\ll N$ and $\boldsymbol{A}$ has i.i.d Gaussian entries. When recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements, PR-GAMP achieved 99\% success rate with a median runtime of only 12.6 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, experiments show that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the problem dimensions increase.
[1] "Diagnosing the Aberrations of the Hubble Space Telescope," J.R. Fienup, in J.C. Dainty, ed., Current Trends in Optics (Academic Press, London, 1994), Ch. 20, pp. 279-287. [PDF, 2 MB]
[2] "Hubble Space Telescope Characterized by Using Phase Retrieval Algorithms," J.R. Fienup, J.C. Marron, T.J. Schulz and J.H. Seldin, Appl. Opt. 32, 1747-1767 (1 April 1993). [PDF, 3.1 MB]
[3] "Phase-Retrieval Algorithms for a Complicated Optical System," J.R. Fienup, Appl. Opt. 32, 1737-1746 (1 April 1993). [PDF, 1.1 MB]
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
[3] "Phase-Retrieval Algorithms for a Complicated Optical System," J.R. Fienup, Appl. Opt. 32, 1737-1746 (1 April 1993). [PDF, 1.1 MB]
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment