GESPAR: Efficient Phase Retrieval of Sparse Signals and QCS: Sparsity based sub-wavelength imaging) -implementations-

You probably recall the mention of GESPAR (Phase Retrieval of Sparse Signals) earlier this year or QCS (Sparsity based sub-wavelength imaging) two years ago. Yoav Shechtman released an implementation of both of these algorithms on his webpage:

* GESPAR: Efficient Phase Retrieval of Sparse Signals

Recovery of a signal from the magnitude of its Fourier transform, also known as phase retrieval, is of great interest in applications such as optical imaging, crystallography and more. Due to the loss of Fourier phase information, the problem (in 1D) is generally ill-posed. A common approach to overcome this ill-posedeness is to exploit prior information on the signal. We develop a method that exploits signal sparsity.

We propose GESPAR (GrEedy Sparse PhAse Retrieval): An efficient method for phase retrieval which also leads to good recovery performance. Our algorithm is based on a fast 2-opt local search method applied to a sparsity constrained non-linear optimization formulation of the problem. In essence, GESPAR is a local-search method, where the support of the sought signal is updated iteratively, according to certain selection rules. A local minimum of the objective function is then found given the current support using the damped Gauss Newton algorithm. We demonstrate through numerical simulations that the proposed algorithm is both efficient and more accurate than current techniques. .........

* QCS

A matlab function that performs the SDP-based QCS algorithm used to find a sparse solution to a set of quadratic equations in Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing.

Note: It uses cvx

Note: It uses cvx

The attendant papers relevant to these implementations are:

GESPAR: Efficient Phase Retrieval of Sparse Signals by Yoav Shechtman, Amir Beck, Yonina C. Eldar. The abstract reads:

We consider the problem of one dimensional (1D) phase retrieval, namely, recovery of a 1D signal from the magnitude of its Fourier transform. This problem is ill-posed since the Fourier phase information is lost. Therefore, prior information on the signal is needed in order to recover it. In this work we consider the case in which the prior information on the signal is that it is sparse, i.e., it consists of a small number of nonzero elements. We propose a fast local search method for recovering a sparse 1D signal from measurements of its Fourier transform magnitude. Our algorithm does not require matrix lifting, unlike previous approaches, and therefore is potentially suitable for large scale problems such as images. Simulation results indicate that the proposed algorithm is fast and more accurate than existing techniques.

and Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing by Yoav Shechtman, Yonina C. Eldar, Alexander Szameit, and Mordechai Segev . The abstract reads:

We demonstrate that sub-wavelength optical images borne on partially-spatially-incoherent light can be recovered, from their far-field or from the blurred image, given the prior knowledge that the image is sparse, and only that. The reconstruction method relies on the recently demonstrated sparsity-based sub-wavelength imaging. However, for partially-spatially-incoherent light, the relation between the measurements and the image is quadratic, yielding non-convex measurement equations that do not conform to previously used techniques. Consequently, we demonstrate new algorithmic methodology, referred to as quadratic compressed sensing, which can be applied to a range of other problems involving information recovery from partial correlation measurements, including when the correlation function has local dependencies. Specifically for microscopy, this method can be readily extended to white light microscopes with the additional knowledge of the light source spectrum.

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.