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 between two vectors is given by
Since , it follows that
Furthermore, equality holds if and only if , implying that
if and only if for some real . 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 be an inner product space over the field of complex numbers with inner product . For every pair of vectors the inequality
holds. Furthermore, the equality
holds if and only if for some . That is, equality holds if and only if and are linearly dependent.
Let be a vector space over the real or complex field , and let be given. In order to prove the Cauchy-Schwarz inequality, it will first be proven that if for some . It will then be shown that if for all .
Consider the case in which for some . From the properties of inner products, it is clear that
Hence, it follows that
Similarly, it is clear that
Thus, it is proven that if for some .
Next, consider the case in which for all , which implies that so . Thus, it follows by the properties of inner products that, for all , This can be expanded using the properties of inner products to the expression
Hence, it follows that Consequently, Thus, it can be concluded that if for all .
Therefore, the inequality
holds for all , and equality
holds if and only if for some .
Consider the maximization of where the norm is induced by the inner product. By the Cauchy-Schwarz inequality, we know that and that if and only if for some . Hence, attains a maximum where for some . Thus, collecting the scalar variables, attains a maximum where . 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 attains its upper bound, which is 1, when for some scalar in a real or complex field. The lower bound, which is 0, is attained when and are orthogonal. In informal intuition, this means that the expression is maximized when the vectors and have the same shape or pattern and minimized when and 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 of signals most resembles a particular signal . In order to accomplish this, we might evaluate the above expression for every signal , 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 of signals that most closely matches a target signal . Thus, for every we wish to evaluate
in order to compare every member of to the target signal . Since the member of which most closely matches the target signal is desired, ultimately we wish to evaluate
Note that the target signal does not technically need to be normalized to produce a maximum, but gives the desirable property that is bounded to .
The element that produces the maximum value of is not necessarily unique, so there may be more than one matching signal in . Additionally, the signal producing the maximum value of may not produce a very large value of and thus not be very much like the target signal . Hence, another matched filter scheme might identify the argument producing the maximum but only above a certain threshold, returning no matching signals in if the maximum is below the threshold. There also may be a signal that produces a large value of and thus has a high degree of “likeness” to but does not produce the maximum value of . Thus, yet another matched filter scheme might identify all signals in producing local maxima that are above a certain threshold.
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 is most like the target signal . However, to make that conclusion mathematically, we use the matched filter detector with the 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 with the target signal . We would notice that the absolute value of the inner product for with when normalized is greater than the absolute value of the inner product of with when normalized, mathematically stated as
A somewhat more involved matched filter detector scheme would involve attempting to match a target time limited signal to a set of of time shifted and windowed versions of a single signal indexed by . The windowing funtion is given by where is the interval to which is time limited. This scheme could be used to find portions of that have the same shape as . If the absolute value of the inner product of the normalized versions of and is large, which is the absolute value of the normalized correlation for standard inner products, then has a high degree of “likeness” to on the interval to which is time limited but left shifted by . Of course, if is not time limited, it means that the entire signal has a high degree of “likeness” to left shifted by .
Thus, in order to determine the most likely locations of a signal with the same shape as the target signal in a signal we wish to compute
to provide the desired shift. Assuming the inner product space examined is (similar results hold for , , and ), this produces
Since and are time limited to the same interval
Making the subsitution ,
Noting that this expression contains a convolution operation
where is the conjugate of the time reversed version of defined by
In the special case in which the target signal is not time limited, has unit value on the entire real line. Thus, the norm can be evaluated as . Therefore, the function reduces to where The function is known as the normalized cross-correlation of and .
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 , , and spaces. It is especially useful to implement the 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 and 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.
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.