Skip to main content
main-content

Über dieses Buch

The aim of this work is to present several topics in time-frequency analysis as subjects in abelian group theory. The algebraic point of view pre­ dominates as questions of convergence are not considered. Our approach emphasizes the unifying role played by group structures on the development of theory and algorithms. This book consists of two main parts. The first treats Weyl-Heisenberg representations over finite abelian groups and the second deals with mul­ tirate filter structures over free abelian groups of finite rank. In both, the methods are dimensionless and coordinate-free and apply to one and multidimensional problems. The selection of topics is not motivated by mathematical necessity but rather by simplicity. We could have developed Weyl-Heisenberg theory over free abelian groups of finite rank or more generally developed both topics over locally compact abelian groups. However, except for having to dis­ cuss conditions for convergence, Haar measures, and other standard topics from analysis the underlying structures would essentially be the same. A re­ cent collection of papers [17] provides an excellent review of time-frequency analysis over locally compact abelian groups. A further reason for limiting the scope of generality is that our results can be immediately applied to the design of algorithms and codes for time­ frequency processing.

Inhaltsverzeichnis

Frontmatter

1. Review of algebra

Abstract
In this chapter we discuss some of the theory of finite abelian groups and finitely generated abelian groups. Abelian groups form the indexing sets for data. This fact by itself is not sufficient for the central importance we place on this theory. The most important processing, representational, and algorithmic constructions and procedures in DSP depend ultimately on concepts that come from abelian group theory. The general theory is considered first. We introduce the groups most often occurring in DSP applications, Z/N, the group of integers mod N, direct products of such groups, and Z, the group of integers and its direct products. Subgroups, coset decompositions and quotient groups, homomorphisms and automorphisms are discussed and highlighted by several examples that are refined throughout the text.
Richard Tolimieri, Myoung An

2. Linear algebra and abelian groups

Abstract
In this chapter we establish notation and discuss several linear algebra topics over finite abelian groups. Much of the discussion can be generalized to free abelian groups of finite rank but for the most part, we delay this theory until chapter 17.
Richard Tolimieri, Myoung An

3. Fourier transform over A

Abstract
The Fourier transform over a finite abelian group A is defined as a purely mathematical entity independent of its origins in physical applications. As such, the Fourier transform has been a source of many fruitful interpretations and generalizations ranging from the polynomial version of the Chinese remainder theorem to the Wedderburn structure theorem for group algebras over finite nonabelian groups.
Richard Tolimieri, Myoung An

4. Poisson summation formula

Abstract
The Poisson summation (PS) formula describes the fundamental duality between periodization and decimation operators under the Fourier transform. In this chapter, the finite abelian group version of the PS formula is derived as a simple application of the character formulas of Chapter 3. The general case is equally simple to prove, but special care must be taken to provide conditions for convergence. The power of the PS formula is not so much with the formula itself, but rather that it highlights a construction that is basic to many derivations and algorithms in pure and applied mathematics and engineering. Common to these applications is the importance of periodization and of computing the Fourier transform of periodizations. In algebraic and analytic number theory this computation results in closed form expressions, the transformation equations for theta and zeta functions, and other important number theoretic special functions.
Richard Tolimieri, Myoung An

5. Zak transform

Abstract
The Zak transform maps a signal of time into a signal that combines both time and frequency information. It is the simplest time-frequency representation of a signal whose value as such is often ignored as a processing tool. Its most usual role is as an intermediary between signal space and a wide range of time-frequency representations, including the ambiguity function, the Wigner distribution, and Weyl-Heisenberg representations.
Richard Tolimieri, Myoung An

6. Weyl-Heisenberg systems

Abstract
For a finite abelian group A and gL(A), we define the concept of a translate of g by an element in A × A* and form systems of functions in L(A) by translates of g over subgroups Δ of A × A*. Such systems are called Weyl-Heisenberg (W-H) systems and expansions of signals over W-H systems are called W-H expansions. W-H expansions naturally embed into many time-frequency constructions and distributions resulting in significant simplification in the form of basic formulas and in the interpretation of computations.
Richard Tolimieri, Myoung An

7. Zak transform and W-H systems

Abstract
We impose the following convention throughout this work. suppose B is a subgroup of a finite abelian group A and Δ is a subgroup of A × A*. Set
$${{\Delta }_{0}} = B \times {{B}_{*}}.$$
Richard Tolimieri, Myoung An

8. Algorithms for W-H systems

Abstract
The conventions established in the introduction to Chapter 7 continue to hold.
The Zak transform characterization of W-H systems is used to design algorithms for W-H coefficient set computation. A critically sampled algorithm is developed and then extended to an integer over-sampled algorithm by a divide-and-conquer approach. Zero set characterization plays a crucial role.
Richard Tolimieri, Myoung An

9. Orthogonal projection theorem

Abstract
Suppose Δ is a subgroup of A × A*, Δ0 is the critical sampling subgroup
$${{\Delta }_{0}} = B \times {{B}_{*}},$$
and gL(A).
Richard Tolimieri, Myoung An

10. Cross-ambiguity function

Abstract
Suppose B is a subgroup of a finite abelian group A, Δ0 is the critical sampling subgroup
$${{\Delta }_{0}} = B \times {{B}_{*}},$$
and Δ is a subgroup of A × A*. Unless otherwise specified, F denotes the Zak transform of f over B.
Richard Tolimieri, Myoung An

11. Ambiguity surfaces

Abstract
In this chapter we derive two important formulas D1 and D2 which form the basis of the Wexler-Raz results on existence and construction of dual functions and biorthogonals in Chapter 13.
Richard Tolimieri, Myoung An

12. Orthonormal W-H systems

Abstract
Suppose B is a subgroup of A, Δ0 is the critical sampling subgroup
$${{\Delta }_{0}} = B \times {{B}_{*}},$$
and Δ is a subgroup of A × A* with
$$o(\Delta ) > o(A).$$
Richard Tolimieri, Myoung An

13. Duality

Abstract
Duality as expressed by the PS formula is a central theme throughout this work. In this chapter, the special form of this duality as expressed by formulas D1 and D2 is applied to the derivation of a collection of results first investigated by Raz-Wexler on construction of biorthogonals and dual functions to W-H systems. The availability of biorthogonals opens the way to new algorithms for constructing W-H coefficient sets. In the next chapter, we compare the Raz-Wexler dual function constructions to those coming from frame theory.
Richard Tolimieri, Myoung An

14. Frames

Abstract
Suppose B and C are subgroups of a finite abelian group A, Δ is a subgroup of A × A*, and gL(A). Denote the order of A by N and set κ = ο(Δ)/N.
Richard Tolimieri, Myoung An

15. Implementation

Abstract
Generally the algorithms developed in this work are based on one- and multidimensional Fourier transforms and matrix inversions. During the last ten years much has been written in papers and books on the implementation of Fourier transforms and matrix inversions especially on multiprocessor architectures. Typically, large data sets are involved. The most time-consuming step in many computations is not arithmetic calculation but rather the complex global and local data reindexings needed to feed the Fourier transform and matrix inversion computations.
Richard Tolimieri, Myoung An

16. Algebra of multirate structures

Abstract
In this chapter we develop the algebra underlying multirate filter structures over free abelian groups of finite rank. Suppose A is a free abelian group of rank N. Each subgroup Δ of A is a free abelian group of rank n ≤ N. The basis theorem describes how Δ sits in A in the sense that it characterizes the quotient group A/Δ. This quotient group can be
  • a finite abelian group
  • a free abelian group of finite rank
  • the direct product of a finite abelian group and a free abelian group of finite rank.
Richard Tolimieri, Myoung An

17. Multirate structures

Abstract
Multirate filter structures over a free abelian group A of finite rank can be represented by elements in the algebra generated by decimators, expanders, and shift operators of L(A). If A has rank 1, then Hom(A) is commutative and the Noble identities determine a complete set of product rules for this algebra.
Richard Tolimieri, Myoung An

18. A Time-frequency search for stock market anomalies

Abstract
We carry out a time-frequency analysis of daily values of the Dow Jones Industrial Average and the S&P 500 Index of stock prices based on 62 years of data. The algorithm used is based on pruning dyadic trees to obtain optimal stationary segmentations of nonstationary time series. The resulting time-frequency representations yield insights into the frequency-domain evolution of the US stock market. Details concerning computational speed and recombination are briefly addressed.
Sudeshna Adak, Abhinanda Sarkar

Backmatter

Weitere Informationen