Connexions

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

What is a lens?

Lenses

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

What is in a lens?

Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

This content is ...
Affiliated with (?)
This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.

  • This module is included inLens: Rice University OpenCourseWare
    By: OpenCourseWare ConsortiumAs a part of collection:"Signals and Systems"

    Click the "Rice University OCW" link to see all content affiliated with them.

    Rice University OCW
Also in these lenses

  • This module is included inLens: richb's DSP resources
    By: Richard BaraniukAs a part of collection:"Signals and Systems"

    Comments:

    "My introduction to signal processing course at Rice University."

    Click the "richb's DSP" link to see all content selected in this lens.

    richb's DSP
Tags

(?)

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

Cauchy-Schwarz Inequality

Module by: Michael Haag, Justin Romberg

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.

Introduction

Recall in ℝ2 2 , <x,y>=∥x∥∥y∥cosθ x y x y θ
|<x,y>|≤∥x∥∥y∥ 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>|≤∥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 αα.

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):
Template Signal
csi_f1.png
Figure 1: Our signal we wish to find match of.
Candidate Signals
csi_f2.pngcsi_f3.png
Subfigure 2.1
Subfigure 2.2
Figure 2: Clearly by looking at these we can see which signal will provide the better match to our template signal.
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,gi>|∥gi∥ 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).
Pattern Signal
csi_pattern.png
Figure 3: The pattern we are looking for in a our long signal having a length TT.
Long Signal
csi_long.png
Figure 4: Here is the long signal that contains a piece that resembles our pattern 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:
  • Shift of s 1 s 1 :
    ∫ s 1 s 1 +Tgtft- s 1 dt∫ s 1 s 1 +T|gt|2dt="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 dt∫ s 2 s 2 +T|gt|2dt="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+Tgtft-sdt∥gt∥| L 2 ss+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*f-t 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 (subfigure 5.1) and piece of a "Where's Waldo?" book (subfigure 5.2),
waldo_head.pngwaldo_pic.png
Subfigure 5.1
Subfigure 5.2
Figure 5: Example of "Where's Waldo?" picture. Our Matched Filter Detector can be implemented to find a possible match for Waldo.
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':
mfilt_1.png
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:
mfilt_2.png
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:
mfilt_3.png
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.

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 f∈Hilbert Space S f Hilbert Space S and g∈Hilbert Space S g Hilbert Space S , show:
|<f,g>|≤∥f∥∥g∥ f g f g (7)
with equality if and only if g=αf g α f .
Proof
  • If g=αf g α f , show |<f,g>|=∥f∥∥g∥ f g f g |<f,g>|=|<f,αf>|=|α||<f,f>|=|α|∥f∥2 f g f α f α f f α f 2 |<f,g>|=∥f∥|α|∥f∥=∥f∥∥g∥ f g f α f f g This verifies our above statement of the CSI!
  • If g≠αf g α f , show |<f,g>|<∥f∥∥g∥ f g f g where we have ∀β,β∈ℝ:βf+g≠0 β β β f g 0 0<∥βf+g∥2=<β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 =β2∥f∥2+2β<f,g>+∥g∥2 β 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 β2-4ac β 2 4 a c where we have: a=∥f∥2 a f 2 b=2<f,g> b 2 f g c=∥g∥2 c g 2 Therefore, we can plug this values into the above polynomials discriminant to get:
    4|<f,g>|2-4∥f∥2∥g∥2<0 4 f g 2 4 f 2 g 2 0 (8)
    |<f,g>|<∥f∥∥g∥ 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)

Comments, questions, feedback, criticisms?

Send feedback