Phase retrieval of sparse L-ary signals from magnitudes of their Fourier transform

Abstract

The problem of recovering a sparse L-ary signal from magnitudes of its Fourier transform or equivalently its autocorrelation function is considered. Although, one can show that solving the phase retrieval problem for L-ary signals is possible in time that is polynomial in L and length of the signal, however, the current algorithms are still not practical. We introduce a backtracking algorithm on a tree which solves the phase retrieval problem. By simulations, we show that the average number of nodes visited on the tree by the backtracking algorithm grows polynomially in L and signal length, although the search tree has an exponential size. © 2014 IEEE.