Partitioning algorithms for reconstruction of discrete one-dimensional and two-dimensional signals from their discrete Fourier transform magnitudes or phases.

Abstract

In our study, we develop new approaches and algorithms to reconstruct 1-D or 2-D signals from partial information of the Fourier transform of the signal. When only the magnitude of the Fourier transform of a signal is known, the signal can be reconstructed if the missing phase information can be recovered. This is often called the phase retrieval problem. We also investigate magnitude retrieval problems where only the phase of the Fourier transform is known. Furthermore, after developing a partitioning method for phase retrieval, it is applied to blind deconvolution problems, where we try to find two different unknown signals when only their convolution is known. Although there have been many efforts to solve the phase retrieval problem, each suggested approach has its shortcomings. The purpose of our study is to present alternate methods to these existing approaches that will either enhance the performances of existing algorithms or replace them altogether. First, we formulate 2nd order polynomial equations for solving phase retrieval problems. Then a new variant of the commonly used iterative transform (IT) algorithm is derived. We also derive relaxation algorithms that have different convergence characteristics from those of IT algorithms so that they can be run to escape stagnations of IT algorithms. By recognizing 1-D phase retrieval problems embedded in 2-D phase retrieval, we develop a partitioning approach for solving 2-D phase retrieval. It greatly reduces the complexity involved in solving 2-D problems, compared to other zero-tracking algorithms. As for the disconnected support phase retrieval problem, we transform a 1-D problem into a 2-D phase retrieval problem and solve it using the partitioning approach. The same partitioning approach is also applied to the blind deconvolution problem. The magnitude retrieval problem is solved by applying a simpler partition.