Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Cauchy-Schwarz Inequality

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Cauchy-Schwarz Inequality

Module by: Michael Haag, Justin Romberg. E-mail the authors

Summary: This module defines the Cauchy-Schwarz Inequality and discusses some of its practical usefulness, especially in the Matched filter detector. Also, we will prove the CSI for real vector spaces.

Note: You are viewing an old version of this document. The latest version is available here.

Introduction

Recall in R2 2 , x,y=xycosθ x y x y θ

|x,y|xy x y x y
(1)
The same relation holds for inner product spaces in general...

Cauchy-Schwarz Inequality

Definition 1: Cauchy-Schwarz Inequality
For xx, yy in an inner product space |x,y|xy 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 αα.

Matched Filter Detector

Also referred to as Cauchy-Schwarz's "Killer App."

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:

  • ff is in the same "direction" as gg
  • if ff and gg are functions, f=αg f α g means ff and gg have the same shape.
For example, say we are in a situation where we have a set of signals, defined as g 1 t g 2 t g k t g 1 t g 2 t g k t , and we want to be able to tell which, if any, of these signals resemble another given signal ft f t .

strategy:

In order to find the signal(s) that resembles ft f t we will take the inner products. If g i t g i t resembles ft f t , then the absolute value of the inner product, |ft, g i t| f t g i t , will be large.
This idea of being able to measure and rank the "likeness" of two signals leads us to the Matched Filter Detector.

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
Template Signal (csi_f1.png)
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)
Figure 2(a) (csi_f2.png)Figure 2(b) (csi_f3.png)

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:

  • Normalize the g i t g i t
  • Take the inner product with ft f t
  • Find the biggest!
Or, putting it mathematically:
Best candidate=argmaxi|f, g i | g i Best candidate i f g i g i
(2)

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
Pattern Signal (csi_pattern.png)
Figure 4: Here is the long signal that contains a piece that resembles our pattern signal.
Long Signal
Long Signal (csi_long.png)

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:

  • Shift of s 1 s 1 :
    s 1 s 1 +Tgtft s 1 d t s 1 s 1 +T|gt|2d t ="large" t s 1 T s 1 g t f t s 1 t s 1 T s 1 g t 2 "large"
    (3)
  • Shift of s 2 s 2 :
    s 2 s 2 +Tgtft s 2 d t s 2 s 2 +T|gt|2d t ="small" t s 2 T s 2 g t f t s 2 t s 2 T s 2 g t 2 "small"
    (4)
Therefore, we can define a generalized equation for our matched filter:
ms=matched filter m s matched filter
(5)
ms=ss+Tgtftsd t gt| L 2 s s+T m s t s T s g t f t s L 2 s s T g t
(6)
where the numerator in Equation 6 is the convolution of gt*ft g t f t . Now in order to decide whether or not the result from our matched filter detector is high enough to indicate an acceptable match between the two signals, we define some threshold. If m s 0 threshold m s 0 threshold then we have a match at location s 0 s 0 .

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)
Figure 5(a) (waldo_head.png)Figure 5(b) (waldo_pic.png)

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'.
Figure 6 (mfilt_1.png)

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.
Figure 7 (mfilt_2.png)

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 (mfilt_3.png)

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.

Proof of CSI

Here will look at the proof of our Cauchy-Schwarz Inequality (CSI) for a real vector space.

Theorem 1: CSI for Real Vector Space

For fHilbert Space S f Hilbert Space S and gHilbert Space S g Hilbert Space S , show:

|f,g|fg f g f g
(7)
with equality if and only if g=αf g α f .

Proof

  • If g=αf g α f , show |f,g|=fg f g f g |f,g|=|f,αf|=|α||f,f|=|α|f2 f g f α f α f f α f 2 |f,g|=f(|α|f)=fg f g f α f f g This verifies our above statement of the CSI!
  • If gαf g α f , show |f,g|<fg f g f g where we have β ,βR:βf+g0 β β β f g 0 0<βf+g2=βf+g,βf+g=β2(f,f)+2β(f,g)+g,g 0 β f g 2 β f g β f g β 2 f f 2 β f g g g β2f2+2β(f,g)+g2 β 2 f 2 2 β f g g 2 And we get a quadratic in β β. Visually, the quadratic polynomial in β>0 β 0 for all ββ. Also, note that this polynomial has no real roots and the discriminant is less than 0. - BLAH BLAH BLAH -- aβ2+bβ+c a β 2 b β c has discriminant β24ac β 2 4 a c where we have: a=f2 a f 2 b=2(f,g) b 2 f g c=g2 c g 2 Therefore, we can plug this values into the above polynomials discriminant to get:
    4|f,g|24f2g2<0 4 f g 2 4 f 2 g 2 0
    (8)
    |f,g|<fg f g f g
    (9)
    And finally we have proven the Cauchy-Schwarz Inequality formula for real vectors spaces.
    question:
    What changes do we have to make to the proof for a complex vector space? (try to figure this out at home)

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks