Introduction

Hopefully you are familiar with the notion of the eigenvectors of a "matrix system," if not they do a quick review of eigen-stuff. We can develop the same ideas for LTI systems acting on signals. A linear time invariant (LTI) system ℋ operating on a continuous input f(t) to produce continuous time output y(t)

ℋ[f(t) ] =y(t) (1)

Figure 1: ℋ[f(t) ] =y(t) . f and t are continuous time (CT) signals and ℋ is an LTI operator.

is mathematically analogous to an NxN matrix A operating on a vector x∈ℂ^N to produce another vector b∈ℂ^N (see Matrices and LTI Systems for an overview).

Ax=b (2)

Figure 2: Ax=b where x and b are in ℂN and A is an N x N matrix.

Just as an eigenvector of A is a v∈ℂ^N such that Av=λv, λ∈ℂ,

Figure 3: Av=λv where v∈ℂN is an eigenvector of A.

we can define an eigenfunction (or eigensignal) of an LTI system ℋ to be a signal f(t) such that

∀λ,λ∈ℂ:ℋ[f(t) ] =λf(t) (3)

Figure 4: ℋ[f(t) ] =λf(t) where f is an eigenfunction of ℋ.

Eigenfunctions are the simplest possible signals for ℋ to operate on: to calculate the output, we simply multiply the input by a complex number λ.

Eigenfunctions of any LTI System

Figure 5: ℋ[ⅇst] =λsⅇst where ℋ is an LTI system.

ℋ[ⅇst]	=	∫−∞∞h(τ) ⅇs(t−τ) dτ
	=	∫−∞∞h(τ) ⅇstⅇ−(sτ) dτ
	=	ⅇst∫−∞∞h(τ) ⅇ−(sτ) dτ

(5)

Since the expression on the right hand side does not depend on t, it is a constant, λ_s. Therefore

ℋ[ⅇ^st] =λ_sⅇ^st (6)

The eigenvalue λ_s is a complex number that depends on the exponent s and, of course, the system ℋ. To make these dependencies explicit, we will use the notation H(s) ≡λ_s.

Figure 6: ⅇst is the eigenfunction and H(s) are the eigenvalues.

Since the action of an LTI operator on its eigenfunctions ⅇ^st is easy to calculate and interpret, it is convenient to represent an arbitrary signal f(t) as a linear combination of complex exponentials. The Fourier series gives us this representation for periodic continuous time signals, while the (slightly more complicated) Fourier transform lets us expand arbitrary continuous time signals.

Comments, questions, feedback, criticisms?

Discussion forum

• Join the discussion »

Send feedback

• E-mail the author
• E-mail Connexions

More about this content: Metadata | Version History | Cite This Content

This work is licensed by Justin Romberg. See the Creative Commons License about permission to reuse this material.

Last edited by Charlet Reedstrom on Jun 20, 2005 9:14 pm GMT-5.

Eigenfunction

From Wikipedia, the free encyclopedia

In mathematics, an eigenfunction of a linear operator, A, defined on some function space is any non-zero function f in that space that returns from the operator exactly as is, except for a multiplicative scaling factor. More precisely, one has

for some scalar, λ, the corresponding eigenvalue. The solution of the differential eigenvalue problem also depends upon any boundary conditions required of f. In each case there are only certain eigenvalues λ = λ_n (n = 1,2,3,...) that admit a corresponding solution for f = f_n (with each f_n belonging to the eigenvalue λ_n) when combined with the boundary conditions. The existence of eigenvectors is typically the most insightful way to analyze A.

For example, f_k(x) = e^kx is an eigenfunction for the differential operator

for any value of k, with a corresponding eigenvalue λ = k² − k. If boundary conditions are applied to this system (e.g., f = 0 at two physical locations in space), then only certain values of k = k_n satisfy the boundary conditions, generating corresponding discrete eigenvalues .

[edit] Applications

Eigenfunctions play an important role in many branches of physics. An important example is quantum mechanics, where the Schrödinger equation

has solutions of the form

where φ_k are eigenfunctions of the operator with eigenvalues E_k. The fact that only certain eigenvalues E_k with associated eigenfunctions φ_k satisfy Schrödinger's equation leads to a natural basis for quantum mechanics and the periodic table of the elements, with each E_k an allowable energy state of the system. The success of this equation in explaining the spectral characteristics of hydrogen is considered one of the great triumphs of 20th century physics.

Due to the nature of the Hamiltonian operator , its eigenfunctions are orthogonal functions. This is not necessarily the case for eigenfunctions of other operators (such as the example A mentioned above). Orthogonal functions f_i, have the property that

whenever , in which case the set is said to be linearly independent.

Convolution

A convolution is an integral that expresses the amount of overlap of one function as it is shifted over another function . It therefore "blends" one function with another. For example, in synthesis imaging, the measured dirty map is a convolution of the "true" CLEAN map with the dirty beam (the Fourier transform of the sampling distribution). The convolution is sometimes also known by its German name, faltung ("folding"). Abstractly, a convolution is defined as a product of functions and that are objects in the algebra of Schwartz functions in . Convolution of two functions and over a finite range is given by (1) where the symbol (occasionally also written as ) denotes convolution of and . Convolution is more often taken over an infinite range, (2) (Bracewell 1999, p. 25). The animations above graphically illustrate the convolution of two rectangle functions (left) and two Gaussians (right). In the plots, the green curve shows the convolution of the blue and red curves as a function of , the position indicated by the vertical green line. The gray region indicates the product as a function of , so its area as a function of is precisely the convolution. The convolution of two rectangle functions and has the particularly simple form (3) Even more amazingly, the convolution of two Gaussians and is another Gaussian (4) Let , , and be arbitrary functions and a constant. Convolution satisfies the properties (5) (6) (7) (Bracewell 1999, p. 27), as well as (8) Taking the derivative of a convolution gives (9) The area under a convolution is the product of areas under the factors, (10) (11) (12) The horizontal function centroids add (13) as do the variances (14) where (15) There is also a definition of the convolution which arises in probability theory and is given by (16) where is a Stieltjes integral. SEE ALSO: Autocorrelation, Cauchy Product, Convolution Theorem, Cross-Correlation, Recurrence Plot, Wiener-Khinchin Theorem. [Pages Linking Here] REFERENCES: Bracewell, R. "Convolution" and "Two-Dimensional Convolution." Ch. 3 in The Fourier Transform and Its Applications, 3rd ed. New York: McGraw-Hill, pp. 25-50 and 243-244, 1999. Hirschman, I. I. and Widder, D. V. The Convolution Transform. Princeton, NJ: Princeton University Press, 1955. Morse, P. M. and Feshbach, H. Methods of Theoretical Physics, Part I. New York: McGraw-Hill, pp. 464-465, 1953. Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Convolution and Deconvolution Using the FFT." §13.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 531-537, 1992. Weisstein, E. W. "Books about Convolution." http://www.ericweisstein.com/encyclopedias/books/Convolution.html.

موشی که دانشمندان آمریکایی در آزمایشگاه به وجود آوردند حامل ژنی بود که وقتی فعال (روشن) می شد باعث رشد عضلاتی مشابه عضلات ناشی از وزنه زدن می شد.

وقتی این ژن "خاموش" می شد، موش - که با غذاهای چرب تغذیه شد- چاق شده و مشکلات کبد پیدا کرد.

به گزارش نشریه "متابولیسم سلولی" که این مطالعه در آن چاپ شده است، وقتی این ژن فعال می شد، همان موش چربی را می سوزاند.

به علاوه، بیماری کبد در اثر انباشت چربی که موش در زمان غیرفعال بودن ژن به آن مبتلا شده بود، درمان شد.

دیگر اینکه پس از فعال شدن ژن، از مقاومت موش در برابر انسولین کاسته شد. مقاومت نسبت به انسولین به دیابت نوع 2 منجر می شود.

این درحالی بود که موش هنوز یک رژیم پرچربی و پر از شکر دریافت می کرد و فعالیت جسمی آن افزایش نیافته بود.

تیم محققان در دانشکده پزشکی دانشگاه بوستون موش ها را از لحاظ ژنتیکی طوری طراحی کرده بودند که عضلات خاصی در آنها پرورش یابد. این عضلات که به "نوع 2" موسوم است ناشی از ورزش هایی مثل وزنه زدن است.

این با عضلاتی که در نتیجه ورزش های استقامت مانند دویدن تشکیل می شود و به "نوع 1" موسوم است فرق دارد.

کِنِت والش از دانشگاه بوستون گفت: "ما نشان دادیم که عضلات نوع 2 فقط برای وقتی که می خواهید چیز سنگین بلند کنید مفید نیست. این عضلات همچنین برای کنترل متابولیسم کل بدن مهم است."

پروفسور کِن فاکس متخصص تربیت بدنی در دانشگاه بریستول گفت که اکنون ورزش های فشاری، مثل وزنه زدن، به عنوان وسیله ای برای بهبود متابولیسم به تدریج مورد توجه قرار گرفته است.

وی گفت: "اگر شما این عضلات را داشته باشید، حتی وقتی کار زیادی نمی کنید درحال سوزاندن انرژی هستید."

"این در حال حاضر موضوعی داغ است. چیزی است که به خصوص می تواند برای افراد مسن تر که ممکن است با ورزش های استقامت مشکل داشته باشند مفید باشد. و می تواند خیلی لذت بخش باشد زیرا تاثیر این ورزش ها سریع آشکار می شود."

Convolution

From Wikipedia, the free encyclopedia

For the usage in formal language theory, see convolution (computer science).

In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that, in a sense, represents the amount of overlap between f and a reversed and translated version of g.

Typically, one of the functions is taken to be a fixed filter impulse response, and is known as a kernel. Such a convolution is a kind of generalized moving average, as one can see by taking the kernel to be an indicator function of an interval.

Visual explanation of convolution. Make each waveform a function of the dummy variable τ. Time-invert one of the waveforms and add t to allow it to slide back and forth on the τ-axis while remaining stationary with respect to t. Finally, start the function at negative infinity and slide it all the way to positive infinity. Wherever the two functions intersect, find the integral of their product. The resulting waveform (not shown here) is the convolution of the two functions. If the stationary waveform is a unit impulse, the end result would be the original version of the sliding waveform, as it is time-inverted back again because the right edge hits the unit impulse first and the left edge last. This is also the reason for the time-inversion in general, as complex signals can be thought to consist of unit impulses.

[edit] Definition

The convolution of and is written . It is defined as the integral of the product of the two functions after one is reversed and shifted. As such, it is a particular kind of integral transform:

The integration range depends on the domain on which the functions are defined; often a = -∞ and b = +∞. While the symbol is used above, it need not represent the time domain. In the case of a finite integration range, and are often considered to extend periodically in both directions, so that the term does not imply a range violation. This use of periodic domains is sometimes called a cyclic, circular or periodic convolution. Of course, extension with zeros is also possible. Using zero-extended or infinite domains is sometimes called a linear convolution, especially in the discrete case below.

[edit] Discrete convolution

For discrete functions, one can use a discrete version of the convolution operation. It is given by

When multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences, in this sense (using extension with zeros as mentioned above).

Generalizing the above cases, the convolution can be defined for any two integrable functions defined on a locally compact topological group (see convolutions on groups below).

A different generalization is the convolution of distributions.

Evaluating discrete convolutions using the above formula applied directly takes O(N²) arithmetic operations for N points, but this can be reduced to O(N log N) using a variety of fast algorithms.

[edit] Fast convolution algorithms

In practice, digital signal processing and other applications of discrete convolution typically use fast convolution algorithms to increase the speed of the convolution to O(N log N) complexity.

The most common fast convolution algorithms use fast Fourier transform (FFT) algorithms via the convolution theorem: the cyclic convolution of two sequences is found by taking an FFT of each sequence, multiplying pointwise, and then performing an inverse FFT. Non-cyclic convolutions, such as linear convolutions can be computed via cyclic convolution using zero-padding.

There are also other many other fast-convolution algorithms that do not employ FFTs per se, such as number-theoretic transform algorithms.

[edit] Properties

[edit] Commutativity

[edit] Associativity

[edit] Distributivity

[edit] Identity element

where δ denotes the Dirac delta

[edit] Associativity with scalar multiplication

for any real (or complex) number .

[edit] Differentiation rule

where denotes the derivative of f or, in the discrete case, the difference operator . Consequently, convolution can be viewed as a "smoothing" operation: the convolution of f and g is differentiable as many times as either f or g is, whichever is greater.

[edit] Convolution theorem

The convolution theorem states that

where denotes the Fourier transform of f, and k is a constant which depends upon the specific normalization of the Fourier transform (e.g., k = 1 if ). Versions of this theorem also hold for the Laplace transform, two-sided Laplace transform, Z-transform and Mellin transform.

See also less trivial Titchmarsh convolution theorem.

[edit] Convolutions on groups

If G is a suitable group endowed with a measure m (for instance, a locally compact Hausdorff topological group with the Haar measure) and if f and g are real or complex valued m-integrable functions on G, then we can define their convolution by

The circle group T with the Lebesgue measure is an immediate example. For a fixed g in L¹(T), we have the following familiar operator acting on the Hilbert space L²(T):

The operator T is compact. A direct calculation shows that its adjoint T* is convolution with

By the commutativity property cited above, T is normal, i.e. T*T = TT*. Also, T commutes with the translation operators. Consider the family S of operators consisting of all such convolutions and the translation operators. S is a commuting family of normal operators. According to spectral theory, there exists an orthonormal basis {h_k} that simultaneously diagonalizes S. This characterizes convolutions on the circle. Specifically, we have

which are precisely the characters of T. Each convolution is a compact multiplication operator in this basis. This can be viewed as a version of the convolution theorem discussed above.

The above example may convince one that convolutions arise naturally in the context of harmonic analysis on groups. For more general groups, it is also possible to give, for instance, a Convolution Theorem, however it is much more difficult to phrase and requires representation theory for these types of groups and the Peter-Weyl theorem . It is very difficult to do these calculations without more structure, and Lie groups turn out to be the setting in which these things are done.

[edit] Convolution of measures

If μ and ν are measures on the family of Borel subsets of the real line, then the convolution μ * ν is defined by

In case μ and ν are absolutely continuous with respect to Lebesgue measure, so that each has a density function, then the convolution μ * ν is also absolutely continuous, and its density function is just the convolution of the two separate density functions.

If μ and ν are probability measures, then the convolution μ * ν is the probability distribution of the sum X + Y of two independent random variables X and Y whose respective distributions are μ and ν.

[edit] Applications

Convolution and related operations are found in many applications of engineering and mathematics.

• In statistics, as noted above, a weighted moving average is a convolution.
• In probability theory, the probability distribution of the sum of two independent random variables is the convolution of their individual distributions.
• In optics, many kinds of "blur" are described by convolutions. A shadow (e.g. the shadow on the table when you hold your hand between the table and a light source) is the convolution of the shape of the light source that is casting the shadow and the object whose shadow is being cast. An out-of-focus photograph is the convolution of the sharp image with the shape of the iris diaphragm. The photographic term for this is bokeh.
• Similarly, in digital image processing, convolutional filtering plays an important role in many important algorithms in edge detection and related processes.
• In linear acoustics, an echo is the convolution of the original sound with a function representing the various objects that are reflecting it.
• In artificial reverberation (digital signal processing, pro audio), convolution is used to map the impulse response of a real room on a digital audio signal (see previous and next point for additional information).
• In electrical engineering and other disciplines, the output (response) of a (stationary, or time- or space-invariant) linear system is the convolution of the input (excitation) with the system's response to an impulse or Dirac delta function. See LTI system theory and digital signal processing.
• In time-resolved fluorescence spectroscopy, the excitation signal can be treated as a chain of delta pulses, and the measured fluorescence is a sum of exponential decays from each delta pulse.
• In physics, wherever there is a linear system with a "superposition principle", a convolution operation makes an appearance.
• This is the fundamental problem term in the Navier Stokes Equations relating to the Clay Mathematics Millennium Problem and the associated million dollar prize.
• In digital signal processing, frequency filtering can be simplified by convolving two functions (data with a filter) in the time domain, which is analogous to multiplying the data with a filter in the frequency domain.

[edit] See also

• Toeplitz matrix (convolutions can be considered a Toeplitz matrix operation where each row is a shifted copy of the convolution kernel)
  • Circulant matrix
• Cross-correlation
• Deconvolution
• Dirichlet convolution
• Titchmarsh convolution theorem
• Convolution power
• Analog signal processing

[edit] External links

• Convolution, on The Data Analysis BriefBook
• http://www.jhu.edu/~signals/convolve/index.html Visual convolution Java Applet.
• http://www.jhu.edu/~signals/discreteconv2/index.html Visual convolution Java Applet for Discrete Time functions.
• Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lecture 7 is on 2-D convolution., by Alan Peters.
• http://www.boingboing.net/2006/10/25/engineering-prof-tea.html - this one more link to the Lectures on Image Processing by Alan Peters (see discussions at the bottom of the page; PDF & DjVu) since above link doesn't working (2008/01/20)

Chapter 6: Convolution

Convolution

Let's summarize this way of understanding how a system changes an input signal into an output signal. First, the input signal can be decomposed into a set of impulses, each of which can be viewed as a scaled and shifted delta function. Second, the output resulting from each impulse is a scaled and shifted version of the impulse response. Third, the overall output signal can be found by adding these scaled and shifted impulse responses. In other words, if we know a system's impulse response, then we can calculate what the output will be for any possible input signal. This means we know everything about the system. There is nothing more that can be learned about a linear system's characteristics. (However, in later chapters we will show that this information can be represented in different forms).

The impulse response goes by a different name in some applications. If the system being considered is a filter, the impulse response is called the filter kernel, the convolution kernel, or simply, the kernel. In image processing, the impulse response is called the point spread function. While these terms are used in slightly different ways, they all mean the same thing, the signal produced by a system when the input is a delta function.

Convolution is a formal mathematical operation, just as multiplication, addition, and integration. Addition takes two numbers and produces a third number, while convolution takes two signals and produces a third signal. Convolution is used in the mathematics of many fields, such as probability and statistics. In linear systems, convolution is used to describe the relationship between three signals of interest: the input signal, the impulse response, and the output signal.

Figure 6-2 shows the notation when convolution is used with linear systems. An input signal, x[n], enters a linear system with an impulse response, h[n], resulting in an output signal, y[n]. In equation form: x[n] * y[n] = y[n]. Expressed in words, the input signal convolved with the impulse response is equal to the output signal. Just as addition is represented by the plus, +, and multiplication by the cross, ×, convolution is represented by the star, *. It is unfortunate that most programming languages also use the star to indicate multiplication. A star in a computer program means multiplication, while a star in an equation means convolution.

Figure 6-3 shows convolution being used for low-pass and high-pass filtering. The example input signal is the sum of two components: three cycles of a sine wave (representing a high frequency), plus a slowly rising ramp (composed of low frequencies). In (a), the impulse response for the low-pass filter is a smooth arch, resulting in only the slowly changing ramp waveform being passed to the output. Similarly, the high-pass filter, (b), allows only the more rapidly changing sinusoid to pass.

Figure 6-4 illustrates two additional examples of how convolution is used to process signals. The inverting attenuator, (a), flips the signal top-for-bottom, and reduces its amplitude. The discrete derivative (also called the first difference), shown in (b), results in an output signal related to the slope of the input signal.

Notice the lengths of the signals in Figs. 6-3 and 6-4. The input signals are 81 samples long, while each impulse response is composed of 31 samples. In most DSP applications, the input signal is hundreds, thousands, or even millions of samples in length. The impulse response is usually much shorter, say, a few points to a few hundred points. The mathematics behind convolution doesn't restrict how long these signals are. It does, however, specify the length of the output signal. The length of the output signal is

equal to the length of the input signal, plus the length of the impulse response, minus one. For the signals in Figs. 6-3 and 6-4, each output signal is: 81 + 31 - 1 = 111 samples long. The input signal runs from sample 0 to 80, the impulse response from sample 0 to 30, and the output signal from sample 0 to 110.

Now we come to the detailed mathematics of convolution. As used in Digital Signal Processing, convolution can be understood in two separate ways. The first looks at convolution from the viewpoint of the input signal. This involves analyzing how each sample in the input signal contributes to many points in the output signal. The second way looks at convolution from the viewpoint of the output signal. This examines how each sample in the output signal has received information from many points in the input signal.

Keep in mind that these two perspectives are different ways of thinking about the same mathematical operation. The first viewpoint is important because it provides a conceptual understanding of how convolution pertains to DSP. The second viewpoint describes the mathematics of convolution.

This typifies one of the most difficult tasks you will encounter in DSP: making your conceptual understanding fit with the jumble of mathematics used to communicate the ideas.

Next Section: The Input Side Algorithm

Download this chapter in PDF format

Chapter6.pdf