The inversion of covariance matrices by finite Fourier transforms (Corresp.)

A matrix series is derived that converges to the inverse of a covariance matrix. The members of the series are derived from a circular matrix that can be inverted by taking finite Fourier transforms. An example of the method is presented.     

A simple numerical method based simultaneous stochastic perturbation for estimation of high dimensional matrices

Multidimensional Systems and Signal Processing - We describe a simple algorithm for estimating the elements of a matrix as well as its decomposition under the condition that only the product of...     

The integer transforms analogous to discrete trigonometric transforms

The integer transform (such as the Walsh transform) is the discrete transform that all the entries of the transform matrix are integer. It is much easier to implement because the real number multiplication operations can be avoided, but the performance is usually worse. On the other hand, the noninteger transform, such as the DFT and DCT, has a good performance, but real number multiplication is required. W derive the integer transforms analogous to some popular noninteger transforms. These integer transforms retain most of the performance quality of the original transform, but the implementation is much simpler. Especially, for the two-dimensional (2-D) block transform in image/video, the saving can be huge using integer operations. In 1989, Cham had derived the integer cosine transform. Here, we will derive the integer sine, Hartley, and Fourier transforms. We also introduce the general method to derive the integer transform from some noninteger transform. Besides, the integer transform derived by Cham still requires real number multiplication for the inverse transform. We modify the integer transform introduced by Cham and introduce the complete integer transform. It requires no real number multiplication operation, no matter what the forward or inverse transform. The integer transform we derive would be more efficient than the original transform. For example, for the 8-point DFT and IDFT, there are in total four real numbers and eight fixed-point multiplication operations required, but for the forward and inverse 8-point complete integer Fourier transforms, there are totally 20 fixed-point multiplication operations required. However, for the integer transform, the implementation is simpler, and many of the properties of the original transform are kept.     

p-adic transforms

Two clarifications are made on the uniqueness of representation of rational numbers in a finite segmented p-adic field, and on orthogonality asserted in a recent article on p-adic transforms. One clarification also reveals a slight generalisation on dynamic range. In addition, an extension of this transform to finite-dimensional cases is also given.     

Periodicity transforms

This paper presents a method of detecting periodicities in data that exploits a series of projections onto “periodic subspaces”. The algorithm finds its own set of nonorthogonal basis elements (based on the data), rather than assuming a fixed predetermined basis as in the Fourier, Gabor, and wavelet transforms. A major strength of the approach is that it is linear-in-period rather than linear-in-frequency or linear-in-scale. The algorithm is derived and analyzed, and its output is compared to that of the Fourier transform in a number of examples. One application is the finding and grouping of rhythms in a musical score, another is the separation of periodic waveforms with overlapping spectra, and a third is the finding of patterns in astronomical data. Examples demonstrate both the strengths and weaknesses of the method     

Fast mersenne number transforms for the computation of discrete fourier transforms

In this paper we present results on the computation of Discrete Fourier Transforms (DFT) using Mersenne Number Transforms (MNT). It is shown that in the case of Mersenne-composite Number Transforms, the number of multiplications per point for real input data is never more than one, even for sequence lengths exceeding one thousand points. The computation time per point for a length (2P + 1)-point DFT is simply equal to the time for one MNT multiplication and 3 MNT additions if a high-speed, parallel hardware module is used to implement the MNT unit. This new approach allows a large choice of wordlengths and in addition the control of data flow is extremely simple. We also present the results obtained by using Winograd's Fourier Transform Algorithm and the nested MNT to compute efficiently the DFT's of long sequences. We also show that the number of additions can be reduced significantly if Pseudo Mersenne-Number Transforms are used for the computation of DFTs.     

Discrete Zak transforms, polyphase transforms, and applications

We consider three different versions of the Zak (1967) transform (ZT) for discrete-time signals, namely, the discrete-time ZT, the polyphase transform, and a cyclic discrete ZT. In particular, we show that the extension of the discrete-time ZT to the complex z-plane results in the polyphase transform, an important and well-known concept in multirate signal processing and filter bank theory. We discuss fundamental properties, relations, and transform pairs of the three discrete ZT versions, and we summarize applications of these transforms. In particular, the discrete-time ZT and the cyclic discrete ZT are important for discrete-time Gabor (1946) expansion (Weyl-Heisenberg frame) theory since they diagonalize the Weyl-Heisenberg frame operator for critical sampling and integer oversampling. The polyphase representation plays a fundamental role in the theory of filter banks, especially DFT filter banks. Simulation results are presented to demonstrate the application of the discrete ZT to the efficient calculation of dual Gabor windows, tight Gabor windows, and frame bounds     

Variable-block-size lapped transforms

A structure for implementing lapped transforms with time-varying block sizes that allows full orthogonality of the transient transforms is presented. The formulation is based on a factorization of the transfer matrix into orthogonal factors. Such an approach can be viewed as a sequence of stages with variable-block-size transforms separated by sample-shuffling (delay) stages. Details and design examples for a first-order system are presented     

Implementation of number-theoretic transforms

We propose various methods for the implementation of number-theoretic transforms to a prime or prime-power modulus. Such transforms may be performed in a processor or by special hardware. We also give, without proof, the condition for the existence of transforms in an arbitrary ring.     

Parameterisation of slant-Haar transforms

A parameterisation of the slant-Haar transform is presented, which includes an existing version of the slant-Haar transform. An efficient algorithm for the slant-Haar transform is developed and its computational complexity is estimated. The parametric slant-Haar transforms are compared to the Karhunen-Loeve transform. The parametric slant-Haar is shown to perform better than the commonly used slant-Haar and slant-Hadamard transforms for the first-order Markov model and also performs better than the discrete cosine transform for images approximated by the generalised image correlation model     

Class of fractal transforms

A general approach to the fractal coding of images is presented, in which image blocks are represented by least squares approximations by fractal functions. Previously known fractal transforms are subsets of this method, which is called the Bath fractal transform (BFT). By searching the image, a hybrid of known methods is achieved, and they are evaluated in the polynomial case with a standard test image.<>     

Optical Hartley transforms

The two-dimensional Hartley transform is of particular interest not only as a tool for analysis and processing of images and other two-dimensional functions, but because it can be implemented optically without introducing the phase ambiguities associated with intensity-only observations of Fourier transforms. The Hartley transform property of producing real transforms from real inputs means that square law detection introduces only a sign ambiguity, which can be resolved much more easily than a phase ambiguity. This suggests applications in optical signal processing, holography, and optical diffraction     

Partial Radon transforms

This article formally defines partial Radon transforms for functions of more than two dimensions. It shows that a generalized projection-slice theorem exists which connects planar and hyperplanar projections of a function to its Fourier transform. In addition, a general theoretical framework is provided for carrying out n-dimensional backprojection reconstruction in a multistage fashion through the use of the partial Radon transform.     

Fast biased polynomial transforms for 2D prime length discrete Fourier transforms

The fast biased polynomial transform (FBPT) is defined directly over a ZN ? 1 ring instead of the conventional cyclotomic polynomial rings. For N prime, these FBPTs can be used for the efficient evaluation of the 2D prime length DFT.     

Generalized discrete Hartley transforms

The discrete Hartley transform is generalized into four classes in the same way as the generalized discrete Fourier transform. Fast algorithms for the resulting transforms are derived. The generalized transforms are expected to be useful in applications such as digital filter banks, fast computation of the discrete Hartley transform for any composite number of data points, fast computations of convolution, and signal representation. The fast computation of skew-circular convolution by the generalized transforms for any composite number of data points is discussed in detail     

Design of lapped orthogonal transforms

We investigate the design of lapped orthogonal transforms for data compression of images. We present some properties and new results of paraunitary filter banks. We concentrate on the case where the filter length L=2K, where K is the number of channels. The aim is to design perceptually relevant filters, i.e., linear-phase filters that smoothly decay to zero at the boundaries.     

Multidimensional orthogonal FM transforms

The present a novel class of multidimensional orthogonal FM transforms. The analysis suggests a novel signal-adaptive FM transform possessing interesting energy compaction properties. We show that the proposed signal-adaptive FM transform produces point spectra for multidimensional signals with uniformly distributed samples. This suggests that the proposed transform is suitable for energy compaction and subsequent coding of broadband signals and images that locally exhibit significant level diversity. We illustrate these concepts with simulation experiments.