Any treatment of linear algebra as relates to signal processing would not be complete without a discussion of the Cauchy-Schwarz ineqaulity, a relation that enables a wide array of signal procesing applications related to pattern matching through a method called the matched filter. Recall that in standard Euclidean space, the angle $\theta $ between two vectors $x,y$ is given by

$$cos\left(\theta \right)=\frac{\u27e8x,y\u27e9}{\left|\right|x\left|\right|\left|\right|y\left|\right|}.$$

1

Since $cos\left(\theta \right)\le 1$, it follows that

$${\left|\u27e8x,y\u27e9\right|}^{2}\le \u27e8x,x\u27e9\u27e8y,y\u27e9.$$

2

Furthermore, equality holds if and only if $cos\left(\theta \right)=0$, implying that

$${\left|\u27e8x,y\u27e9\right|}^{2}=\u27e8x,x\u27e9\u27e8y,y\u27e9$$

3

if and only if $y=ax$ for some real $a$. This relation can be extended to all inner product spaces over a real or complex field and is known as the Cauchy-Schwarz inequality, which is of great importance to the study of signals.

The general statement of the Cauchy-Schwarz inequality mirrors the intuition for standard Euclidean space. Let $V$ be an inner product space over the field of complex numbers $\mathbb{C}$ with inner product $\u27e8\xb7,\xb7\u27e9$. For every pair of vectors $x,y\in V$ the inequality

$${\left|\u27e8x,y\u27e9\right|}^{2}\le \u27e8x,x\u27e9\u27e8y,y\u27e9$$

4

holds. Furthermore, the equality

$${\left|\u27e8x,y\u27e9\right|}^{2}=\u27e8x,x\u27e9\u27e8y,y\u27e9$$

5

holds if and only if $y=ax$ for some $a\in \mathbb{C}$. That is, equality holds if and only if $x$ and $y$ are linearly dependent.

Let $V$ be a vector space over the real or complex field $F$, and let $x,y\in V$ be given. In order to prove the Cauchy-Schwarz inequality, it will first be proven that ${\left|\u27e8x,y\u27e9\right|}^{2}=\u27e8x,x\u27e9\u27e8y,y\u27e9$ if $y=ax$ for some $a\in F$. It will then be shown that ${\left|\u27e8x,y\u27e9\right|}^{2}<\u27e8x,x\u27e9\u27e8y,y\u27e9$ if $y\ne ax$ for all $a\in F$.

Consider the case in which $y=ax$ for some $a\in F$. From the properties of inner products, it is clear that

$$\begin{array}{cc}\hfill {\left|\u27e8x,y\u27e9\right|}^{2}& ={\left|\u27e8x,ax\u27e9\right|}^{2}\hfill \\ & =|\overline{a}{\u27e8x,x\u27e9|}^{2}.\hfill \end{array}$$

6

Hence, it follows that

$$\begin{array}{cc}\hfill {\left|\u27e8x,y\u27e9\right|}^{2}& =|\overline{a}{|}^{2}{\left|\u27e8x,x\u27e9\right|}^{2}\hfill \\ & ={\left|a\right|}^{2}{\u27e8x,x\u27e9}^{2}.\hfill \end{array}$$

7

Similarly, it is clear that

$$\begin{array}{cc}\hfill \u27e8x,x\u27e9\u27e8y,y\u27e9& =\u27e8x,x\u27e9\u27e8ax,ax\u27e9\hfill \\ & =\u27e8x,x\u27e9a\overline{a}\u27e8x,x\u27e9\hfill \\ & ={\left|a\right|}^{2}{\u27e8x,x\u27e9}^{2}.\hfill \end{array}$$

8

Thus, it is proven that ${\left|\u27e8x,y\u27e9\right|}^{2}=\u27e8x,x\u27e9\u27e8y,y\u27e9$ if $x=ay$ for some $a\in F$.

Next, consider the case in which $y\ne ax$ for all $a\in F$, which implies that $y\ne 0$ so $\u27e8y,y\u27e9\ne 0$. Thus, it follows by the properties of inner products that, for all $a\in F$, $\u27e8x-ay,x-ay\u27e9>0.$ This can be expanded using the properties of inner products to the expression

$$\begin{array}{cc}\hfill \u27e8x-ay,x-ay\u27e9& =\u27e8x,x-ay\u27e9-a\u27e8y,x-ay\u27e9\hfill \\ & =\u27e8x,x\u27e9-\overline{a}\u27e8x,y\u27e9-a\u27e8y,x\u27e9+{\left|a\right|}^{2}\u27e8y,y\u27e9\hfill \end{array}$$

9

Choosing $a=\frac{\u27e8x,y\u27e9}{\u27e8y,y\u27e9}$,

$$\begin{array}{cc}\hfill \u27e8x-ay,x-ay\u27e9& =\u27e8x,x\u27e9-\frac{\u27e8y,x\u27e9}{\u27e8y,y\u27e9}\u27e8x,y\u27e9-\frac{\u27e8x,y\u27e9}{\u27e8y,y\u27e9}\u27e8y,x\u27e9+\frac{\u27e8x,y\u27e9\u27e8y,x\u27e9}{{\u27e8y,y\u27e9}^{2}}\u27e8y,y\u27e9\hfill \\ & =\u27e8x,x\u27e9-\frac{\u27e8x,y\u27e9\u27e8y,x\u27e9}{\u27e8y,y\u27e9}\hfill \end{array}$$

10

Hence, it follows that $\u27e8x,x\u27e9-\frac{\u27e8x,y\u27e9\u27e8y,x\u27e9}{\u27e8y,y\u27e9}>0.$ Consequently, $\u27e8x,x\u27e9\u27e8y,y\u27e9-\u27e8x,y\u27e9\overline{\u27e8x,y}\u27e9>0.$ Thus, it can be concluded that ${\left|\u27e8x,y\u27e9\right|}^{2}<\u27e8x,x\u27e9\u27e8y,y\u27e9$ if $y\ne ax$ for all $a\in F$.

Therefore, the inequality

$${\left|\u27e8x,y\u27e9\right|}^{2}\le \u27e8x,x\u27e9\u27e8y,y\u27e9$$

11

holds for all $x,y\in V$, and equality

$${\left|\u27e8x,y\u27e9\right|}^{2}=\u27e8x,x\u27e9\u27e8y,y\u27e9$$

12

holds if and only if $y=ax$ for some $a\in F$.

Consider the maximization of $\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|$ where the norm $\left|\right|\xb7\left|\right|=\u27e8\xb7,\xb7\u27e9$ is induced by the inner product. By the Cauchy-Schwarz inequality, we know that ${\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|}^{2}\le 1$ and that ${\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|}^{2}=1$ if and only if $\frac{y}{\left|\right|y\left|\right|}=a\frac{x}{\left|\right|x\left|\right|}$ for some $a\in \mathbb{C}$. Hence, $\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|$ attains a maximum where $\frac{y}{\left|\right|y\left|\right|}=a\frac{x}{\left|\right|x\left|\right|}$ for some $a\in \mathbb{C}$. Thus, collecting the scalar variables, $\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|$ attains a maximum where $y=ax$. This result will be particulaly useful in developing the matched filter detector techniques.

A great many applications in signal processing, image processing, and beyond involve determining the presence and location of a target signal within some other signal. A radar system, for example, searches for copies of a transmitted radar pulse in order to determine the presence of and distance to reflective objects such as building or aircraft. A communication system searches for copies of waveforms representing digital 0s and 1s in order to receive a message.

As has already been shown, the expression $\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|$ attains its upper bound, which is 1, when $y=ax$ for some scalar $a$ in a real or complex field. The lower bound, which is 0, is attained when $x$ and $y$ are orthogonal. In informal intuition, this means that the expression is maximized when the vectors $x$ and $y$ have the same shape or pattern and minimized when $x$ and $y$ are very different. A pair of vectors with similar but unequal shapes or patterns will produce relatively large value of the expression less than 1, and a pair of vectors with very different but not orthogonal shapes or patterns will produce relatively small values of the expression greater than 0. Thus, the above expression carries with it a notion of the degree to which two signals are “alike”, the magnitude of the normalized correlation between the signals in the case of the standard inner products.

This concept can be extremely useful. For instance consider a situation in which we wish to determine which signal, if any, from a set $X$ of signals most resembles a particular signal $y$. In order to accomplish this, we might evaluate the above expression for every signal $x\in X$, choosing the one that results in maxima provided that those maxima are above some threshold of “likeness”. This is the idea behind the matched filter detector, which compares a set of signals against a target signal using the above expression in order to determine which among them are most like the target signal. For a detailed treatment of the applications of the matched filter detector see the liked module.

The simplest variant of the matched filter detector scheme would be to find the member signal in a set $X$ of signals that most closely matches a target signal $y$. Thus, for every $x\in X$ we wish to evaluate

$$m(x,y)=\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|$$

13

in order to compare every member of $X$ to the target signal $y$. Since the member of $X$ which most closely matches the target signal $y$ is desired, ultimately we wish to evaluate

$${x}_{m}={argmax}_{x\in X}\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{y}{\left|\right|y\left|\right|}\u27e9\right|.$$

14

Note that the target signal does not technically need to be normalized to produce a maximum, but gives the desirable property that $m(x,y)$ is bounded to $[0,1]$.

The element ${x}_{m}\in X$ that produces the maximum value of $m(x,y)$ is not necessarily unique, so there may be more than one matching signal in $X$. Additionally, the signal ${x}_{m}\in X$ producing the maximum value of $m(x,y)$ may not produce a very large value of $m(x,y)$ and thus not be very much like the target signal $y$. Hence, another matched filter scheme might identify the argument producing the maximum but only above a certain threshold, returning no matching signals in $X$ if the maximum is below the threshold. There also may be a signal $x\in X$ that produces a large value of $m(x,y)$ and thus has a high degree of “likeness” to $y$ but does not produce the maximum value of $m(x,y)$. Thus, yet another matched filter scheme might identify all signals in $X$ producing local maxima that are above a certain threshold.

Example 1

For example, consider the target signal given in Figure 1 and the set of two signals given in Figure 2. By inspection, it is clear that the signal ${g}_{2}$ is most like the target signal $f$. However, to make that conclusion mathematically, we use the matched filter detector with the ${L}_{2}$ inner product. If we were to actually make the necessary computations, we would first normalize each signal and then compute the necessary inner products in order to compare the signals in $X$ with the target signal $f$. We would notice that the absolute value of the inner product for ${g}_{2}$ with $f$ when normalized is greater than the absolute value of the inner product of ${g}_{1}$ with $f$ when normalized, mathematically stated as

$${g}_{2}={argmax}_{x\in \{{g}_{1},{g}_{2}\}}\left|\u27e8\frac{x}{\left|\right|x\left|\right|},\frac{f}{\left|\right|f\left|\right|}\u27e9\right|.$$

15

Template Signal

Candidate Signals

A somewhat more involved matched filter detector scheme would involve attempting to match a target time limited signal $y=f$ to a set of of time shifted and windowed versions of a single signal $X=\left\{w{S}_{t}g\right|t\in \mathbb{R}\}$ indexed by $\mathbb{R}$. The windowing funtion is given by $w\left(t\right)=u(t-{t}_{1})-u(t-{t}_{2})$ where $[{t}_{1},{t}_{2}]$ is the interval to which $f$ is time limited. This scheme could be used to find portions of $g$ that have the same shape as $f$. If the absolute value of the inner product of the normalized versions of $f$ and $w{S}_{t}g$ is large, which is the absolute value of the normalized correlation for standard inner products, then $g$ has a high degree of “likeness” to $f$ on the interval to which $f$ is time limited but left shifted by $t$. Of course, if $f$ is not time limited, it means that the entire signal has a high degree of “likeness” to $f$ left shifted by $t$.

Thus, in order to determine the most likely locations of a signal with the same shape as the target signal $f$ in a signal $g$ we wish to compute

$${t}_{m}={argmax}_{t\in \mathbb{R}}\left|\u27e8\frac{f}{\left|\right|f\left|\right|},\frac{w{S}_{t}g}{\left|\right|w{S}_{t}g\left|\right|}\u27e9\right|$$

16

to provide the desired shift. Assuming the inner product space examined is ${L}_{2}(\mathbb{R}$ (similar results hold for ${L}_{2}\left(\mathbb{R}[a,b)\right)$, ${l}_{2}\left(\mathbb{Z}\right)$, and ${l}_{2}\left(\mathbb{Z}[a,b)\right)$), this produces

$${t}_{m}={argmax}_{t\in \mathbb{R}}\left|\frac{1}{\left|\right|f\left|\right|\left|\right|w{S}_{t}g\left|\right|}{\int}_{-\infty}^{\infty}f\left(\tau \right)w\left(\tau \right)\overline{g(\tau -t)}d\tau \right|.$$

17

Since $f$ and $w$ are time limited to the same interval

$${t}_{m}={argmax}_{t\in \mathbb{R}}\left|\frac{1}{\left|\right|f\left|\right|\left|\right|w{S}_{t}g\left|\right|}{\int}_{{t}_{1}}^{{t}_{2}}f\left(\tau \right)\overline{g(\tau -t)}d\tau \right|.$$

18

Making the subsitution $h\left(t\right)=\overline{g(-t)}$,

$${t}_{m}={argmax}_{t\in \mathbb{R}}\left|\frac{1}{\left|\right|f\left|\right|\left|\right|w{S}_{t}g\left|\right|}{\int}_{{t}_{1}}^{{t}_{2}}f\left(\tau \right)h(t-\tau )d\tau \right|.$$

19

Noting that this expression contains a convolution operation

$${t}_{m}={argmax}_{t\in \mathbb{R}}\left|\frac{(f*h)\left(t\right)}{\left|\right|f\left|\right|\left|\right|w{S}_{t}g\left|\right|}\right|.$$

20

where $h$ is the conjugate of the time reversed version of $g$ defined by $h\left(t\right)=\overline{g(-t)}.$

In the special case in which the target signal $f$ is not time limited, $w$ has unit value on the entire real line. Thus, the norm can be evaluated as $\left|\right|w{S}_{t}g\left|\right|=\left|\right|{S}_{t}g\left|\right|=\left|\right|g\left|\right|=\left|\right|h\left|\right|$. Therefore, the function reduces to ${t}_{m}={argmax}_{t\in \mathbb{R}}\frac{(f*h)\left(t\right)}{\left|\right|f\left|\right|\left|\right|h\left|\right|}$ where $h\left(t\right)=\overline{g(-t)}.$ The function $f\u2606g=\frac{(f*h)\left(t\right)}{\left|\right|f\left|\right|\left|\right|h\left|\right|}$ is known as the normalized cross-correlation of $f$ and $g$.

Hence, this matched filter scheme can be implemented as a convolution. Therefore, it may be expedient to implement it in the frequency domain. Similar results hold for the ${L}_{2}\left(\mathbb{R}[a,b)\right)$, ${l}_{2}\left(\mathbb{Z}\right)$, and ${l}_{2}\left(\mathbb{Z}[a,b]\right)$ spaces. It is especially useful to implement the ${l}_{2}\left(\mathbb{Z}[a,b]\right)$ cases in the frequency domain as the power of the Fast Fourier Transform algorithm can be leveraged to quickly perform the computations in a computer program. In the ${L}_{2}\left(\mathbb{R}[a,b)\right)$ and ${l}_{2}\left(\mathbb{Z}[a,b]\right)$ cases, care must be taken to zero pad the signal if wrap-around effects are not desired. Similar results also hold for spaces on higher dimensional intervals with the same inner products.

Of course, there is not necessarily exactly one instance of a target signal in a given signal. There could be one instance, more than one instance, or no instance of a target signal. Therefore, it is often more practical to identify all shifts corresponding to local maxima that are above a certain threshold.

Example 2

The signal in Figure 4 contains an instance of the template signal seen in Figure 3 beginning at time $t={s}_{1}$ as shown by the plot in Figure 5. Therefore,

$${s}_{1}={argmax}_{t\in \mathbb{R}}\left|\u27e8\frac{f}{\left|\right|f\left|\right|},\frac{w{S}_{t}g}{\left|\right|w{S}_{t}g\left|\right|}\u27e9\right|.$$

21

Pattern Signal

Longer Signal

Absolute Value of Output

Proof of the Cauchy-Schwarz Inequality

As can be seen, the Cauchy-Schwarz inequality is a property of inner product spaces over real or complex fields that is of particular importance to the study of signals. Specifically, the implication that the absolute value of an inner product is maximized over normal vectors when the two arguments are linearly dependent is key to the justification of the matched filter detector. Thus, it enables the use of matched filters for such pattern matching applications as image detection, communications demodulation, and radar signal analysis.