WEEK TASK Proposal Research Implementation- Iterative Algorithms Debugging and Testing GUI development Final Paper Presentation and Demo Schedule of Completion of Key Tasks. 5 6 7 8 9 2 3 4 proposal for Reconstruction of Signals from Irregularly Sampled Data submitted to fulfill the semester project requirement for EE 4773/6773: Digital Signal Processing September 19, 1997 submitted to: Dr. Joseph Picone Department of Electrical and Computer Engineering 413 Simrall, Hardy Rd. Mississippi State University Box 9 571 MS State, MS 39762 submitted by: Vamsidhar Juvvigunta, Balakrishna Nakshatrala and Nagamohan Kompella Signal Reconstruction Group Department of Electrical and Computer Engineering Mississippi State University Box 9571 Mississippi State, Mississippi 39762 Tel: 601-325-8335 Fax: 601-325-3149 email: {vamsi, balki, mohi}@ERC.MsState.Edu I. Abstract This project aims at the implementation and comparison of some algorithms for the reconstruction of irregularly sampled band-limited signals. These algorithms include the ADPW method, the POCS method and the Wiley/Marvasti (WILMAR) method. The results of these methods will be compared using criteria like error estimates, computational expense etc. II. Introduction The sampling problem is one of the standard problems in signal analysis. Since a signal f(x) cannot be recorded in it's entirety, it is sampled at a sequence ??? . In practice only a finite number of samples can be measured and stored. In this case the irregular sampling problem becomes a finite dimensional problem. The problem of irregular sampling and the subsequent reconstruction of the signal is not a contrived one but on the contrary is a very common problem. For example when a signal is transmitted there will always be a loss of information when sampling it in the receiver. This will result in a larger sampling gap and ofcourse you get noise. There might be loss of data even in the original sampling itself. Data samples may be lost due to deterioration of signals stored on magnetic media and so on. In all these cases uniform sampling and reconstruction methods will not work properly. Another field where nonuniform sampling and reconstruction may be of use is with ( adaptive ) data compression of signals, using adaptive non uniform samplers, sampling only, if the signal is changing. Just think of CT ??? where you get very large data packets and it will be of use if you sample with larger gaps in regions of less interest ( or less change of the signal ) and nevertheless, will be able to reconstruct the signal properly. A third motivation for non uniform sampling may be that it is more natural, in the sense that the receptors in your eye/ear are sampling non uniform ( and band limited). In this project however, we restrict ourselves to the reconstruction of discrete 1-D band-limited signals only. III. Iterative Reconstruction Algorithms Most of the Iterative algorithms can be considered as alternating mapping methods using the given irregular spaced sampling information about the signal f and the information about the spectral support of f. Actually the following iterative two-step algorithm is typical for most of the methods. 1. As the first step an Auxiliary signal is constructed from the given sampling values of f by an approximation operator A. A is a linear operator, except in the POCS ??? method. The resulting function Af can be either a step function or a piece-wise linear interpolation or as well chosen discrete measure. It is important that only the sampling values of f are required to construct Af. 2. We project the in general not -band-limited signal Af into the space by an orhtogonal projection , in order to kill the high frequencies of Af. One may think of this mapping as a smoothing operation which eliminates the discontinuity of Af. As mentioned this projection can be described as a low-pass filter, using as a transfer function the indicator function of the set , i.e. The (linear) two step algorithms are all based on a recursion of the form: usually with where A is some approximation operator, using only the sampling values and is the orthogonal projection, mapping a given signal onto the space of band-limited signals with spectrum . Of course this projection can be described as a low pass filter, the transfer function of the set , i.e. , 0 elsewhere. Alternatively the projection can be described as convolution using SINC-type kernel (SINC) is the inverse fourier transform of the indicator function given by , and . 1. The Wiley/Marvasti Method: The Marvasti approach has its origin in Wiley's natural sampling method and makes use of the formula (f = f * sinc) and the interpretation of the shift operator as convolution with Dirac measures. Thus the Marvasti approximation operator A-f is nothing but a discrete measure of the form and the first approximation signal can be obtained by convolving A-f with the Sinc function. Hence, Often, the speed of the convergence of the algorithm increases rapidly, if one multiplies by a global relaxation parameter and we obtain 2. The Adaptive Weights Method : In this case the approximation operator is of the form . The weights are established in an adaptive way, depending on the sampling geometry. A good way to determine the `s is given by the "nearest neighborhood" method : Here, the `s are related to the of the Voronoi method, since . The essential effect of the adaptive weights algorithm is, to attach lower importance to those sampling points which are in the regions of higher sampling density, and vice versa to lend higher weight to those sampling points, which are more isolated. The Marvasti method is a special case of the adaptive weights method, if one determines all weights to be equal (to ). 3. POCS Method : POCS stands for "Projection Onto Convex Sets" and is a recursive algorithm for finding the point in the intersection of p given closed convex sets (remember that a set C is said to be convex if, with 2 arbitrary points , the whole line between and belongs to C). The central idea of the POCS method is as follows: Nearly most data consisting of an unknown signal can be viewed as a constraint that restricts f to lie in a closed convex set in Thus, for p known properties there are p closed convex sets , i = 1,...,p and f must lie in the intersection The problem is then to find a point in given the sets and projection operators projecting onto , i = 1,...,p. The recursive relations given by ; k = 0, 1,... The two methods of reconstructing a signal by POCS are "One-Step Method" and "Iterative Method". In this project we will be dealing with the latter. · ITERATIVE METHOD In the iterative description, the information of the sampling values is used step by step as a correction term, and at each step a certain multiple of the shifted filter is added to the approximation. With explicitly defined, the iterative reconstruction algorithm becomes , with . represents the kth estimate of a band limited function consistent to all sampling values, is the 1 - cycle improvement over , and h(x) is the initial estimate, which represents a first approximation of the unknown function f. III. Evaluation The various criteria to describe the quality of iterative algorithms are.. 1. Speed of convergence 2. Noise sensitivity and stability 3. Finding auxiliary parameters 4. Role of the sampling geometry etc. IV. Work division · Vamsidhar : GUI and the POCS method implementation · Balki : Literature survey and ADPW algorithm implementation. · Nagamohan : Wiley/Marvasti method implementation. Later all the parts will be integrated and tested by all of us together. V. References [1] H.G. Feichtinger and K. Gröchenig. Theory and practice of irregular sampling. In Benedetto J. and Frazier M., Wavelets: Mathematics and Applications, CRC Press, pages 305-363, 1993. [2] H.G. Feichtinger, C.Cenker, and M.Herrmann. Iterative algorithms in irregular sampling: A first comparison of methods. In Conf. ICCCP`91, March 1991, Phoenix, AZ pages 483-489, 1991. [3] H.G.Feichtinger and C.Cenker. Reconstruction algorithms for discrete non-uniform sampled band-limited signals. In 15.ÖAGM Conf., ÖCG, volume 56, pages 51 61, May 1991. [4] T.Strohmer. Irregular sampling, frames and pseudo-inverse. Masters Thesis, University of Vienna, 1991. VI. Schedule A schedule for the major tasks in this project are shown below. 1 14 13 12 11 10