Fast Algorithms for Multidimensional Signals

A Mathematical Expression is sufficient to represent an algorithm which in most cases represents input/output relationships. The efficiency of such an Algorithm can be evaluated by the amount of computational resources it takes to compute output or the quantity of interest.

Motivation and applications

In an algorithm we can assume that we have a mathematical expression relating the output and input. Example of Algorithms can be Filters, Fourier Transforms, Histograms, Image Enhancements and etc. All of these operations can be expressed as mathematical formulas and can be directly computed as we write the expressions. As one would expect this can be termed as the Obvious Implementation [1] of the Algorithm. Also it is not necessary that this obvious implementation is always efficient. When people began to compute such things, they began to look for more efficient ways. The wiki page aims at showcasing such efficient and Fast Algorithms for Multidimensional Signals. A multidimensional (M-D) signal can be modeled as a function of independent variables, where is greater than or equal to 2. These signals may be categorized as continuous, discrete, or mixed. A continuous signal can be modeled as a function of independent variables which range over a continuum of values, example – an audio wave travelling in space, space waves measured at different times. A discrete signal, on the other hand, can be modelled as a function defined only on a set of points, such as the set of integers. An Image is the simplest example of 2-D Signal which is spatial in Nature. In the context of Fast Algorithms, consider the below example: We need to compute A which is given by A = αγ + αδ + βγ + βδ where α,β,γ and δ are complex variables. To compute A, we need 4 complex multiplications and 3 complex additions. The above equation can be written in its simplified form as A = (α + β)(γ + δ) This form requires only 1 complex multiplication and 2 complex additions. Thus the second way of computing A is much more efficient and fast compared to the first method of computing A. This is the motivation for the evolution of the Fast Algorithms in the Digital Signal Processing Field. Consequently, many of the real life applications make use of these efficient Algorithms for fast computations.