Reconstruction of signals from the sign data.

Abstract

This thesis deals with the problem of reconstruction of signals as a function of time or space, from the given information of the type of sign data in the space domain. The problem of signal representation and reconstruction from partial information has been studied extensively in the literature. Previous work in this area has considered, first, the derivation (or establishment) of conditions under which signals are uniquely specified by zero-crossings, Fourier transform magnitude or phase, or signed magnitude information, and next, the development of practical algorithms for recovering signals from this information. Work on the reconstruction of signals from non-uniformly sampled signals has also been reported in the literature.

The importance of zero-crossing locations in determining the nature of both one- and two-dimensional signals has been recognized for some time. Experiments in speech processing have shown that speech with only zero-crossing information preserves much of the intelligibility of the original signal. In the computational theory of human vision, zero-crossing detection has been proposed as one important preliminary stage of human visual information processing.

Two approaches are adopted in this thesis to reconstruct the signal from the zero-crossing or sign information. In the first approach, the reconstruction problem is formulated based on the method of Projection onto Convex Sets (POCS). In this method, the known constraints on the signal are modeled as convex sets with projection operators defined. The signal satisfying all the constraints lies in the intersection set of all the convex sets. The reconstruction algorithm is developed to reconstruct from the sign information of signals. Information regarding the dominant frequency of the signal (in the Fourier space) is estimated from the given sign data.

In the second approach, the problem of reconstruction of one-dimensional signals using zero-crossing information is reformulated as follows: Given the signum function of a one-dimensional signal and the constraint on the “effective space width” or “effective bandwidth” (the so-called space-bandwidth product), is it possible to reconstruct the signal uniquely (except for a scale factor)? If the answer is yes, what is the possible procedure to accomplish the reconstruction? It is shown that the answer to the first question is yes in a certain sense and under certain conditions, which are made explicit in the thesis. As far as the second question is concerned, granted the conditions under which a reconstruction is unique, a procedure to reconstruct the unknown signal is given in the form of an algorithm. In view of the non-convex nature of the error functional defined for quantifying the difference between the original signum function and the signum function of the reconstructed signal, simulated annealing is exploited to optimize the reconstruction.

A theorem on unique reconstruction is presented. It assumes that the zero-crossing points (or equivalently, the signum function of the unknown signal) are given along with the constraint that the “effective signal spread” (either in the spatial or spectral domain) is a pre-specified number and the actual physical spread is to be minimal or maximal.

The main contributions of the thesis are:

A formulation of the reconstruction problem for signals along with the development of an algorithm to reconstruct the signals from the sign information based on the POCS method.

Use of generalized Hermite functions and optimization (by simulated annealing) for signal reconstruction.

Chapter 1 outlines the concept of zero-crossings of one-dimensional signals. Various conditions and techniques available in the literature to reconstruct the one-dimensional signal from its zero-crossings are surveyed. In addition, techniques to reconstruct a two-dimensional signal from its zero-crossings are summarized. Signal reconstruction from other partial information such as signed magnitude and one-bit phase is also discussed.

Chapter 2 introduces the idea of projection onto convex sets. The reconstruction problem is posed and formulated in this framework. The development of a method to obtain spectral information from the sign data and an algorithm for the reconstruction of the signals are discussed. Results of the algorithm as applied to one-dimensional signals are presented.

Chapter 3 introduces the idea of representing a signal in terms of generalized Hermite functions. A procedure to reconstruct the signal from the given sign information and the effective spatial spread has been described. The algorithm employs simulated annealing to minimize the cost functional while attempting to obtain the unique signal from the given data. Results of this algorithm, as applied to one-dimensional signals, are given.

Chapter 4 presents a possible extension of the reconstruction method using generalized Hermite polynomials to one-dimensional signals with complex zeros and to two-dimensional signals.

A comprehensive list of relevant references has been included at the end of the thesis.