Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Signals and Systems » Cauchy-Schwarz Inequality

Navigation

Table of Contents

Lenses

What is a lens?

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.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

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.

Also in these lenses

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

  • richb's DSP display tagshide tags

    This collection is included inLens: richb's DSP resources
    By: Richard Baraniuk

    Comments:

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

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

    Click the tag icon tag icon to display tags associated with this content.

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, Stephen Kruzick, Dan Calderon, Catherine Elder. E-mail the authors

Summary: This module provides both statement and proof of the Cauchy-Schwarz inequality and discusses its practical implications with regard to the matched filter detector.

Introduction

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 x,yx,y is given by

cos ( θ ) = x , y | | x | | | | y | | . cos ( θ ) = x , y | | x | | | | y | | .
(1)

Since cos(θ)1cos(θ)1, it follows that

| x , y | 2 x , x y , y . | x , y | 2 x , x y , y .
(2)

Furthermore, equality holds if and only if cos(θ)=0cos(θ)=0, implying that

| x , y | 2 = x , x y , y | x , y | 2 = x , x y , y
(3)

if and only if y=axy=ax for some real aa. 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 Cauchy-Schwarz Inequality

Statement of the Cauchy-Schwarz Inequality

The general statement of the Cauchy-Schwarz inequality mirrors the intuition for standard Euclidean space. Let VV be an inner product space over the field of complex numbers CC with inner product ·,··,·. For every pair of vectors x,yVx,yV the inequality

| x , y | 2 x , x y , y | x , y | 2 x , x y , y
(4)

holds. Furthermore, the equality

| x , y | 2 = x , x y , y | x , y | 2 = x , x y , y
(5)

holds if and only if y=axy=ax for some aCaC. That is, equality holds if and only if xx and yy are linearly dependent.

Proof of the Cauchy-Schwarz Inequality

Let VV be a vector space over the real or complex field FF, and let x,yVx,yV be given. In order to prove the Cauchy-Schwarz inequality, it will first be proven that |x,y|2=x,xy,y|x,y|2=x,xy,y if y=axy=ax for some aFaF. It will then be shown that |x,y|2<x,xy,y|x,y|2<x,xy,y if yaxyax for all aFaF.

Consider the case in which y=axy=ax for some aFaF. From the properties of inner products, it is clear that

| x , y | 2 = | x , a x | 2 = | a ¯ x , x | 2 . | x , y | 2 = | x , a x | 2 = | a ¯ x , x | 2 .
(6)

Hence, it follows that

| x , y | 2 = | a ¯ | 2 | x , x | 2 = | a | 2 x , x 2 . | x , y | 2 = | a ¯ | 2 | x , x | 2 = | a | 2 x , x 2 .
(7)

Similarly, it is clear that

x , x y , y = x , x a x , a x = x , x a a ¯ x , x = | a | 2 x , x 2 . x , x y , y = x , x a x , a x = x , x a a ¯ x , x = | a | 2 x , x 2 .
(8)

Thus, it is proven that |x,y|2=x,xy,y|x,y|2=x,xy,y if x=ayx=ay for some aFaF.

Next, consider the case in which yaxyax for all aFaF, which implies that y0y0 so y,y0y,y0. Thus, it follows by the properties of inner products that, for all aFaF, x-ay,x-ay>0.x-ay,x-ay>0. This can be expanded using the properties of inner products to the expression

x - a y , x - a y = x , x - a y - a y , x - a y = x , x - a ¯ x , y - a y , x + | a | 2 y , y x - a y , x - a y = x , x - a y - a y , x - a y = x , x - a ¯ x , y - a y , x + | a | 2 y , y
(9)

Choosing a=x,yy,ya=x,yy,y,

x - a y , x - a y = x , x - y , x y , y x , y - x , y y , y y , x + x , y y , x y , y 2 y , y = x , x - x , y y , x y , y x - a y , x - a y = x , x - y , x y , y x , y - x , y y , y y , x + x , y y , x y , y 2 y , y = x , x - x , y y , x y , y
(10)

Hence, it follows that x,x-x,yy,xy,y>0.x,x-x,yy,xy,y>0. Consequently, x,xy,y-x,yx,y¯>0.x,xy,y-x,yx,y¯>0. Thus, it can be concluded that |x,y|2<x,xy,y|x,y|2<x,xy,y if yaxyax for all aFaF.

Therefore, the inequality

| x , y | 2 x , x y , y | x , y | 2 x , x y , y
(11)

holds for all x,yVx,yV, and equality

| x , y | 2 = x , x y , y | x , y | 2 = x , x y , y
(12)

holds if and only if y=axy=ax for some aFaF.

Additional Mathematical Implications

Consider the maximization of x||x||,y||y||x||x||,y||y|| where the norm ||·||=·,·||·||=·,· is induced by the inner product. By the Cauchy-Schwarz inequality, we know that x||x||,y||y||21x||x||,y||y||21 and that x||x||,y||y||2=1x||x||,y||y||2=1 if and only if y||y||=ax||x||y||y||=ax||x|| for some aCaC. Hence, x||x||,y||y||x||x||,y||y|| attains a maximum where y||y||=ax||x||y||y||=ax||x|| for some aCaC. Thus, collecting the scalar variables, x||x||,y||y||x||x||,y||y|| attains a maximum where y=axy=ax. This result will be particulaly useful in developing the matched filter detector techniques.

Matched Filter Detector

Background Concepts

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 x||x||,y||y||x||x||,y||y|| attains its upper bound, which is 1, when y=axy=ax for some scalar aa in a real or complex field. The lower bound, which is 0, is attained when xx and yy are orthogonal. In informal intuition, this means that the expression is maximized when the vectors xx and yy have the same shape or pattern and minimized when xx and yy 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 XX of signals most resembles a particular signal yy. In order to accomplish this, we might evaluate the above expression for every signal xXxX, 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.

Signal Comparison

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

m ( x , y ) = x | | x | | , y | | y | | m ( x , y ) = x | | x | | , y | | y | |
(13)

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

x m = argmax x X x | | x | | , y | | y | | . x m = argmax x X x | | x | | , y | | y | | .
(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)m(x,y) is bounded to [0,1][0,1].

The element xmXxmX that produces the maximum value of m(x,y)m(x,y) is not necessarily unique, so there may be more than one matching signal in XX. Additionally, the signal xmXxmX producing the maximum value of m(x,y)m(x,y) may not produce a very large value of m(x,y)m(x,y) and thus not be very much like the target signal yy. Hence, another matched filter scheme might identify the argument producing the maximum but only above a certain threshold, returning no matching signals in XX if the maximum is below the threshold. There also may be a signal xXxX that produces a large value of m(x,y)m(x,y) and thus has a high degree of “likeness” to yy but does not produce the maximum value of m(x,y)m(x,y). Thus, yet another matched filter scheme might identify all signals in XX 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 g2g2 is most like the target signal ff. However, to make that conclusion mathematically, we use the matched filter detector with the L2L2 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 XX with the target signal ff. We would notice that the absolute value of the inner product for g2g2 with ff when normalized is greater than the absolute value of the inner product of g1g1 with ff when normalized, mathematically stated as

g 2 = argmax x { g 1 , g 2 } x | | x | | , f | | f | | . g 2 = argmax x { g 1 , g 2 } x | | x | | , f | | f | | .
(15)
Figure 1: We wish to find a match for this target signal in the set of signals below.
Template Signal
Template Signal (csi_f1.png)
Figure 2: We wish to find a match for the above target signal in this set of signals.
Candidate Signals
(a) (b)
Figure 2(a) (csi_f2.png)Figure 2(b) (csi_f3.png)

Pattern Detection

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

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

t m = argmax t R f | | f | | , w S t g | | w S t g | | t m = argmax t R f | | f | | , w S t g | | w S t g | |
(16)

to provide the desired shift. Assuming the inner product space examined is L2(RL2(R (similar results hold for L2(R[a,b))L2(R[a,b)), l2(Z)l2(Z), and l2(Z[a,b))l2(Z[a,b))), this produces

t m = argmax t R 1 | | f | | | | w S t g | | - f ( τ ) w ( τ ) g ( τ - t ) ¯ d τ . t m = argmax t R 1 | | f | | | | w S t g | | - f ( τ ) w ( τ ) g ( τ - t ) ¯ d τ .
(17)

Since ff and ww are time limited to the same interval

t m = argmax t R 1 | | f | | | | w S t g | | t 1 t 2 f ( τ ) g ( τ - t ) ¯ d τ . t m = argmax t R 1 | | f | | | | w S t g | | t 1 t 2 f ( τ ) g ( τ - t ) ¯ d τ .
(18)

Making the subsitution h(t)=g(-t)¯h(t)=g(-t)¯,

t m = argmax t R 1 | | f | | | | w S t g | | t 1 t 2 f ( τ ) h ( t - τ ) d τ . t m = argmax t R 1 | | f | | | | w S t g | | t 1 t 2 f ( τ ) h ( t - τ ) d τ .
(19)

Noting that this expression contains a convolution operation

t m = argmax t R ( f * h ) ( t ) | | f | | | | w S t g | | . t m = argmax t R ( f * h ) ( t ) | | f | | | | w S t g | | .
(20)

where hh is the conjugate of the time reversed version of gg defined by h ( t ) = g ( - t ) ¯ . h ( t ) = g ( - t ) ¯ .

In the special case in which the target signal ff is not time limited, ww has unit value on the entire real line. Thus, the norm can be evaluated as ||wStg||=||Stg||=||g||=||h||||wStg||=||Stg||=||g||=||h||. Therefore, the function reduces to tm=argmaxtR(f*h)(t)||f||||h||tm=argmaxtR(f*h)(t)||f||||h|| where h(t)=g(-t)¯.h(t)=g(-t)¯. The function fg=(f*h)(t)||f||||h||fg=(f*h)(t)||f||||h|| is known as the normalized cross-correlation of ff and gg.

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 L2(R[a,b))L2(R[a,b)), l2(Z)l2(Z), and l2(Z[a,b])l2(Z[a,b]) spaces. It is especially useful to implement the l2(Z[a,b])l2(Z[a,b]) 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 L2(R[a,b))L2(R[a,b)) and l2(Z[a,b])l2(Z[a,b]) 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=s1t=s1 as shown by the plot in Figure 5. Therefore,

s 1 = argmax t R f | | f | | , w S t g | | w S t g | | . s 1 = argmax t R f | | f | | , w S t g | | w S t g | | .
(21)
Figure 3: This function shows tha pattern we are looking for in the signal below, which occurs at time t=s1t=s1.
Pattern Signal
Pattern Signal (csi_pattern.png)
Figure 4: This signal contains an instance of the above signal starting at time t=s1t=s1.
Longer Signal
Longer Signal (csi_long.png)
Figure 5: This signal shows a sketch of the absolute value of the matched filter output for the interval shown. Note that this was just an "eyeball approximation" sketch. Observe the pronounced peak at time t=s1t=s1.
Absolute Value of Output
Absolute Value of Output (mfout2.png)

Cauchy-Schwarz Inequality Video Lecture

Figure 6: Video lecture on the proof of the Cauchy-Schwarz inequality from Khan Academy. Only part of the theorem is proven.
Proof of the Cauchy-Schwarz Inequality

Cauchy-Schwarz Inequality Summary

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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection 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

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