Paulo J. S. G. Ferreira

Superoscillations Bioinformatics Shannon sampling Sensor networks and precision agriculture Toeplitz and random matrices Simulation and differential equations Real and DFT codes Uncertainty-based and fuzzy information Frames, codes and reconstruction Sorting and the analog median filter Missing samples Nonlinear systems Approximation and coding DFT Education and teaching Copyrights

Frames, codes and reconstruction

Certain signal reconstruction problems can be understood in terms of frames and redundant representations. The redundancy is useful because it leads to robust signal representations, that is, representations in which partial loss of data can be tolerated without misbehavior or adverse effects. These papers explore the interplay between frames, signal reconstruction algorithms, and error control coding in the real field (or DFT codes). They are also related to some of the papers mentioned in the section on Missing samples (bandlimited interpolation and erasure correction, a linear problem) and in the section on Real and DFT codes (detecting the position of the errors and correcting them, a nonlinear problem).

In an attempt to circumvent the numerical difficulties that low-pass DFT codes face when dealing with bursty (contiguous) error patterns, some of the papers introduce parallel concatenated DFT codes with an interleaver. The structure of these two-channel codes is similar to parallel concatenated turbo codes, and their numerical performance seems to be much better than the usual DFT codes (the condition number of the matrices involved can be smaller by many orders of magnitude).

10.1109/LSP.2002.807876

P. J. S. G. Ferreira and J. M. N. Vieira. Stable DFT Codes and Frames. IEEE Signal Processing Letters, vol. 10, no. 2, pp. 50-53, Feb. 2003.

DFT or real number codes have been studied and recognized as useful (as joint source-channel codes, for example) but are not stable under bursty losses. This paper introduces a two-channel DFT code with an interleaver, and shows that its numerical stability far exceeds that of the corresponding single-channel DFT code (the ratio of the frame bounds for the two-channel system can be smaller by many orders of magnitude). This leads to a stable way of dealing with bursts of errors using DFT codes.

P. J. S. G. Ferreira. Stable interpolation and error correction: concatenated real-codes with an interleaver. In: Proceedings of the 2001 Workshop on Sampling Theory and Applications, SampTA'2001, Orlando, Florida, pp. 177-182, May 2001.

This paper introduces a new class of real codes, which can be described as two parallel concatenated DFT codes with an interleaver. Numerical examples show that the numerical stability of the two-channel codes exceeds that of the corresponding single-channel DFT code with the same code rate (the ratio of the frame bounds for the two-channel system can be smaller by many orders of magnitude). This leads to a stable way of dealing with bursts of errors using DFT codes.

10.1109/97.823525

P. J. S. G. Ferreira. Stability Issues in Error Control Coding in the Complex Field, Interpolation, and Frame Bounds. IEEE Signal Processing Letters, vol. 7, no. 3, pp. 57-59, Mar. 2000.

The paper derives bounds for the eigenvalues and condition number of a matrix, with applications to error control coding in the complex field, spectrum analysis, the missing data problem, interpolation, and the determination of discrete finite frame bounds.

P. J. S. G. Ferreira. Mathematics for Multimedia Signal Processing II — Discrete Finite Frames and Signal Reconstruction. In: Signal Processing for Multimedia, J. S. Byrnes (Ed.). IOS Press, pp. 35-54, 1999.

Part of the material in this book chapter was presented at the NATO Advanced Study Institute "Signal Processing for Multimedia", Il Ciocco, Italy, July 1998.

This chapter contains a tutorial on discrete finite frames, and explains the equivalence between the frame algorithm and certain iterative methods (POCS bandlimited reconstruction, and the discrete Papoulis-Gerchberg algorithm). It begins by presenting a few engineering problems in which robust data representations play a central role. It turns out that these problems, which occur in signal processing, spectrum analysis, information theory, and fault-tolerant computing, are closely related or even equivalent. However, perhaps surprisingly, the connections between them have gone nearly unnoticed so far.

Frames provide one of the ways of understanding certain of these problems, including the missing data problem. Some of the methods that can be used to recover from missing data errors are examined, emphasizing finite-dimensional theory because of its simplicity and practical usefulness, and interpreting the results in terms of discrete finite frames. The connection between the frame algorithm and a few other iterative reconstruction methods, such as POCS and the Papoulis-Gerchberg iteration, is detailed.

10.1109/78.324726

P. J. S. G. Ferreira. Interpolation and the Discrete Papoulis-Gerchberg Algorithm. IEEE Transactions on Signal Processing, vol. 42, no. 10, pp. 2596-2606, Oct. 1994.

This paper studies the performance of an iterative algorithm which can be used to recover missing samples in finite-length records of band-limited data. The algorithm is in fact equivalent to the frame algorithm, as shown in the book chapter Mathematics for Multimedia Signal Processing II — Discrete Finite Frames and Signal Reconstruction. The paper is also closely related to the papers in the section on Missing samples.

No assumptions are made regarding the distribution of the missing samples, in contrast with the often studied extrapolation problem, in which the known samples are grouped together: the observed signal is regarded as a sampled version of the original, and the reconstruction result can be seen as a sampling result.

Main results:

The iterative algorithm converges if the density of the sampling set exceeds a certain minimum value which naturally increases with the bandwidth of the data.
Explicit best-possible upper and lower bounds for the error as a function of the number of iterations, and the signals for which the bounds are attained.
Analysis of the effect of a relaxation parameter on the spectral radius of the iteration matrix, and the optimum value of that parameter.
The sampling sets for which the convergence rate of the recovery algorithm is maximum or minimum (among all sets of the same density).
For low-pass signals the best convergence rates are obtained when the distances among the missing samples are a multiple of a certain integer. The worst convergence rates generally occur when the missing samples are contiguous. For bandpass signals, this is no longer the case.

Universidade de Aveiro
Paulo J. S. G. Ferreira
About Research Contact	Superoscillations Bioinformatics Shannon sampling Sensor networks and precision agriculture Toeplitz and random matrices Simulation and differential equations Real and DFT codes Uncertainty-based and fuzzy information Frames, codes and reconstruction Sorting and the analog median filter Missing samples Nonlinear systems Approximation and coding DFT Education and teaching Copyrights Frames, codes and reconstruction Certain signal reconstruction problems can be understood in terms of frames and redundant representations. The redundancy is useful because it leads to robust signal representations, that is, representations in which partial loss of data can be tolerated without misbehavior or adverse effects. These papers explore the interplay between frames, signal reconstruction algorithms, and error control coding in the real field (or DFT codes). They are also related to some of the papers mentioned in the section on Missing samples (bandlimited interpolation and erasure correction, a linear problem) and in the section on Real and DFT codes (detecting the position of the errors and correcting them, a nonlinear problem). In an attempt to circumvent the numerical difficulties that low-pass DFT codes face when dealing with bursty (contiguous) error patterns, some of the papers introduce parallel concatenated DFT codes with an interleaver. The structure of these two-channel codes is similar to parallel concatenated turbo codes, and their numerical performance seems to be much better than the usual DFT codes (the condition number of the matrices involved can be smaller by many orders of magnitude). 10.1109/LSP.2002.807876 P. J. S. G. Ferreira and J. M. N. Vieira. Stable DFT Codes and Frames. IEEE Signal Processing Letters, vol. 10, no. 2, pp. 50-53, Feb. 2003. DFT or real number codes have been studied and recognized as useful (as joint source-channel codes, for example) but are not stable under bursty losses. This paper introduces a two-channel DFT code with an interleaver, and shows that its numerical stability far exceeds that of the corresponding single-channel DFT code (the ratio of the frame bounds for the two-channel system can be smaller by many orders of magnitude). This leads to a stable way of dealing with bursts of errors using DFT codes. P. J. S. G. Ferreira. Stable interpolation and error correction: concatenated real-codes with an interleaver. In: Proceedings of the 2001 Workshop on Sampling Theory and Applications, SampTA'2001, Orlando, Florida, pp. 177-182, May 2001. This paper introduces a new class of real codes, which can be described as two parallel concatenated DFT codes with an interleaver. Numerical examples show that the numerical stability of the two-channel codes exceeds that of the corresponding single-channel DFT code with the same code rate (the ratio of the frame bounds for the two-channel system can be smaller by many orders of magnitude). This leads to a stable way of dealing with bursts of errors using DFT codes. 10.1109/97.823525 P. J. S. G. Ferreira. Stability Issues in Error Control Coding in the Complex Field, Interpolation, and Frame Bounds. IEEE Signal Processing Letters, vol. 7, no. 3, pp. 57-59, Mar. 2000. The paper derives bounds for the eigenvalues and condition number of a matrix, with applications to error control coding in the complex field, spectrum analysis, the missing data problem, interpolation, and the determination of discrete finite frame bounds. P. J. S. G. Ferreira. Mathematics for Multimedia Signal Processing II — Discrete Finite Frames and Signal Reconstruction. In: Signal Processing for Multimedia, J. S. Byrnes (Ed.). IOS Press, pp. 35-54, 1999. Part of the material in this book chapter was presented at the NATO Advanced Study Institute "Signal Processing for Multimedia", Il Ciocco, Italy, July 1998. This chapter contains a tutorial on discrete finite frames, and explains the equivalence between the frame algorithm and certain iterative methods (POCS bandlimited reconstruction, and the discrete Papoulis-Gerchberg algorithm). It begins by presenting a few engineering problems in which robust data representations play a central role. It turns out that these problems, which occur in signal processing, spectrum analysis, information theory, and fault-tolerant computing, are closely related or even equivalent. However, perhaps surprisingly, the connections between them have gone nearly unnoticed so far. Frames provide one of the ways of understanding certain of these problems, including the missing data problem. Some of the methods that can be used to recover from missing data errors are examined, emphasizing finite-dimensional theory because of its simplicity and practical usefulness, and interpreting the results in terms of discrete finite frames. The connection between the frame algorithm and a few other iterative reconstruction methods, such as POCS and the Papoulis-Gerchberg iteration, is detailed. 10.1109/78.324726 P. J. S. G. Ferreira. Interpolation and the Discrete Papoulis-Gerchberg Algorithm. IEEE Transactions on Signal Processing, vol. 42, no. 10, pp. 2596-2606, Oct. 1994. This paper studies the performance of an iterative algorithm which can be used to recover missing samples in finite-length records of band-limited data. The algorithm is in fact equivalent to the frame algorithm, as shown in the book chapter Mathematics for Multimedia Signal Processing II — Discrete Finite Frames and Signal Reconstruction. The paper is also closely related to the papers in the section on Missing samples. No assumptions are made regarding the distribution of the missing samples, in contrast with the often studied extrapolation problem, in which the known samples are grouped together: the observed signal is regarded as a sampled version of the original, and the reconstruction result can be seen as a sampling result. Main results: The iterative algorithm converges if the density of the sampling set exceeds a certain minimum value which naturally increases with the bandwidth of the data. Explicit best-possible upper and lower bounds for the error as a function of the number of iterations, and the signals for which the bounds are attained. Analysis of the effect of a relaxation parameter on the spectral radius of the iteration matrix, and the optimum value of that parameter. The sampling sets for which the convergence rate of the recovery algorithm is maximum or minimum (among all sets of the same density). For low-pass signals the best convergence rates are obtained when the distances among the missing samples are a multiple of a certain integer. The worst convergence rates generally occur when the missing samples are contiguous. For bandpass signals, this is no longer the case.