Cauchy-Schwarz Inequality

Definition 1: Cauchy-Schwarz Inequality

For xx, yy in an inner product space |<x,y>|≤∥x∥∥y∥ x y x y with equality holding if and only if xx and yy are linearly dependent, i.e. x=αy x α y for some scalar αα.

Concept behind Matched Filter

If we are given two vectors, f f and gg, then the Cauchy-Schwarz Inequality (CSI) is maximized when f=αg f α g . This tells us:

Comparing Signals

The simplest use of the Matched Filter would be to take a set of "candidate" signals, say our set of g 1 t g 2 t… g k t g 1 t g 2 t … g k t , and try to match it to a "template" signal, ft f t . For example say we are given the below template (Figure 1) and candidate signals (Figure 2):

Figure 1: Our signal we wish to find match of.

Template Signal

Figure 2: Clearly by looking at these we can see which signal will provide the better match to our template signal.

Candidate Signals
(a) (b)

Now if our only question was which function was a closer match to ft f t then we can easily come up with the answer based on inspection - g 2 t g 2 t . However, this will not always be the case. Also, we may want to develop a method, or algorithm, that could automate these comparisons. Or perhaps we wish to have a quantitative value expressing just how similar the signals are. To address these issues, we will lay out a more formal approach to comparing the signals, which will, as mentioned above, be based on the inner product.

In order to see which of our candidate signals, g 1 t g 1 t or g 2 t g 2 t , best resembles ft f t we need to perform the following steps:

Finding a Pattern

Extending these thoughts of using the Matched Filter to find similarities among signals, we can use the same idea to search for a pattern in a long signal. The idea is simply to repeatedly perform the same calculation as we did previously; however, now instead of calculating on different signals we will simply perform the inner product with different shifted versions of our "pattern" signal. For example, say we have the following two signals - a pattern signal (Figure 3) and long signal (Figure 4).

Figure 3: The pattern we are looking for in a our long signal having a length TT.

Pattern Signal

Figure 4: Here is the long signal that contains a piece that resembles our pattern signal.

Long Signal

Here we will look at two shifts of our pattern signal, shifting the signal by s 1 s 1 and s 2 s 2 . These two possibilities yield the following calculations and results:

Practical Examples

Image Detection

In 2-D, this concept is used to match images together, such as verifying fingerprints for security or to match photos of someone. For example, this idea could be used for the ever-popular "Where's Waldo?" books! If we are given the below template (Figure 5(a)) and piece of a "Where's Waldo?" book (Figure 5(b)),

Figure 5: Example of "Where's Waldo?" picture. Our Matched Filter Detector can be implemented to find a possible match for Waldo.

(a) (b)

then we could easily develop a program to find the closest resemblance to the image of Waldo's head in the larger picture. We would simply implement our same match filter algorithm: take the inner products at each shift and see how large our resulting answers are. This idea was implemented on this same picture for a Signals and Systems Project at Rice University (click the link to learn more).

Communications Systems

Matched filter detector are also commonly used in Communications Systems. In fact, they are the optimal detectors in Gaussian noise. Signals in the real-world are often distorted by the environment around them, so there is a constant struggle to develop ways to be able to receive a distorted signal and then be able to filter it in some way to determine what the original signal was. Matched filters provide one way to compare a received signal with two possible original ("template") signals and determine which one is the closest match to the received signal.

For example, below we have a simplified example of Frequency Shift Keying (FSK) where we having the following coding for '1' and '0':

Figure 6: Frequency Shift Keying for '1' and '0'.

Based on the above coding, we can create digital signals based on 0's and 1's by putting together the above two "codes" in an infinite number of ways. For this example we will transmit a basic 3-bit number, 101, which is displayed in Figure 7:

Figure 7: The bit stream "101" coded with the above FSK.

Now, the signal picture above represents our original signal that will be transmitted over some communication system, which will inevitably pass through the "communications channel," the part of the system that will distort and alter our signal. As long as the noise is not too great, our matched filter should keep us from having to worry about these changes to our transmitted signal. Once this signal has been received, we will pass the noisy signal through a simple system, similar to the simplified version shown in Figure 8:

Figure 8: Block diagram of matched filter detector.

Figure 8 basically shows that our noisy signal will be passed in (we will assume that it passes in one "bit" at a time) and this signal will be split and passed to two different matched filter detectors. Each one will compare the noisy, received signal to one of the two codes we defined for '1' and '0.' Then this value will be passed on and whichever value is higher (i.e. whichever FSK code signal the noisy signal most resembles) will be the value that the receiver takes. For example, the first bit that will be sent through will be a '1' so the upper level of the block diagram will have a higher value, thus denoting that a '1' was sent by the signal, even though the signal may appear very noisy and distorted.