Deteccion y Estimacion

Maestrıa en Ing. Electronica

Capitulo III

Estimacion de Parametros

D.U. Campos-Delgado

Facultad de Ciencias

UASLP

Agosto-Diciembre/2017

1

CONTENIDO

Introduccion

Estimacion de Maxima Verosimilitud

Prueba Generalizada de Maxima Verosimilitud

Criterios para Estimacion

Estimacion de Bayes

Desigualdad de Cramer-Rao

Estimacion Multiple de Parametros

Estimador Optimo Lineal

Estimacion de Mınimos Cuadrados Lineal

Estimacion Recursiva de Mınimos Cuadrados

Estimacion de Mınimos Cuadrados Nolineal

2

Introduccion

Considerar que en un problema de deteccion, se

ha elegido la hipotesis correcta, pero se desco-

nocen ciertos parametros que pueden estimar-

se con base a las observaciones.

PROBLEMA: se tienen K i.i.d muestras de

una VA Y1, . . . , YK

Y =[

Y1 . . . YK]

que se caracterizan por cierta funcion de den-

sidad f(y|θ) que depende de un parametro θ.

Considerar que θ se estima con base a una fun-

cion estatica g(·) de las observaciones, es decir

θ = g (Y1, . . . , YK)

Se plantean 2 soluciones dependiendo de la su-

posicion de la naturaleza de θ: determinıstico

o estocastico.

3

Estimacion de Maxima Verosimilitud

Definir la funcion de verosimilitud como

L(θ) = f(y|θ) = f(y1, . . . , yK|θ) =K∏

i=1

f(yi|θ)

Se plantea el problema de estimacion por me-

dio de un proceso de optimizacion para parame-

tros no-aleatorios

θ = argmaxL(θ)

θ se define como estimacion de maxima vero-

similitud (MLE)

∼ maxθ

ln[L(θ)]

Una condicion necesaria para una estimacion

ML es resolver la ecuacion de verosimilitud

∂

∂θln[f(y|θ)] = 0

4

PRINCIPIO DE INVARIANCIA: asumir que

ξ(θ) es una funcion inyectiva, si θ es un MLE

de θ, entonces ξ(θ) es un MLE de ξ(θ).

Ejemplo 1: las muestras recibidas bajo las hipote-

sis H1 y Ho son

H1 : Yi = m+ Vi, i = 1, . . . ,K

Ho : Yi = Vi.

donde E(Vi) = 0 y E(V 2i ) = σ2.

(A) Suponer que m es una constante descono-

cida, obtener un MLE m del promedio.

(B) Suponer que el valor medio m se conoce,

pero la varianza σ2 es desconocida. Obtener

un MLE de σ2.�

5

Prueba Gen. de Maxima Verosimilitud

Considerar nuevamente el problema de hipote-

sis compuesta, donde la observacion es conta-

minada por ruido normal sobre ambas hipotesis

⇒ existe una prueba UMP para tomar la deci-

sion para m > 0

yH1

RHo

σ2

mln τ +

m

2

y para m < 0

yHo

RH1

σ2

mln τ +

m

2

⇒ Como ambas pruebas son diferentes, no exis-

te un UMP para cualquier valor de m.

Otro enfoque: utilizar la informacion para es-

timar el parametro desconocido θ como si la

hipotesis H1 fuera cierta, y utilizar el estimado

en la prueba de hipotesis de verosimilitud.

6

Si la estimacion a utilizar es la MLE ⇒ prueba

generalizada de maxima verosimilitud

Lg(y) =maxθ1 f(y|θ1)maxθ0 f(y|θ0)

H1

RHo

τ

donde θ0 y θ1 son los parametros desconocidos

que seran estimados bajo las hipotesis Ho y H1.

Ejemplo: considerar el problema de hipotesis

binaria

H1 : Yi = m+ Vi, i = 1, . . . ,K

Ho : YI = V.

donde E(Vi) = 0 y E(V 2i ) = σ2. Considerar

que m es un parametro desconocido. Obtener

la prueba generalizada de maxima verosimilitud

y compararla con la prueba optima de Neyman-

Pearson. �

7

Criterios para Estimacion

Considerar ahora que el parametro descono-

cido θ es una VA, y se definen ciertos parame-

tros para caracterizar una “buena” estimacion.

Estimacion Sin Polarizacion: si el estimado θ

cumple E[θ] = θ ∀θ.

Estimacion Polarizada: si se cumple E[θ] = θ+b

1. Polarizacion Conocida: si el valor constante

b no depende de θ, es decir E[θ − b] = θ es

una estimacion sin polarizacion.

2. Polarizacion Desconocida: si b no puede co-

nocerse de antemano.

8

Ademas de que el promedio del parametro es-

timado coincida con el valor real, se debe cum-

plir que la varianza en la estimacion se encuen-

tre limitada.

f( )

0

θ

θ

θ

σ1

σ2

σ3

σ1<σ2<σ3

Varianza Mınima sin Polarizacion: θ debe ser

una estimacion de varianza mınima y sin po-

larizacion, es decir para cualquier estimacion θ

tal que E[θ] = θ se debe cumplir V [θ] ≤ V [θ]

∀θ.

9

Estimacion Consistente: considerar que la es-

timacion θ se basa en K observaciones ⇒ se

cumple

lımK→∞

P(

|θ − θ| > ǫ)

= 0 ∀ǫ > 0

∴ θ es una estimacion consistente de θ si cum-

ple

lımK→∞

E[θ] = θ & lımK→∞

V [θ] = 0

10

Estimacion de Bayes

Se considera que la funcion de riesgo se con-

forma como una funcion entre el valor real θ y

su estimado θ ⇒ C(θ, θ):

Error Cuadratico: R = E[(θ − θ)2]

Valor Absoluto del Error: R = E[|θ − θ|]

Funcion de Costo Uniforme: R = E[CU(θ, θ)]

CU(θ, θ) =

{

1, |θ − θ| ≥ ∆2

0, |θ − θ| < ∆2

⇒ R =

∫ ∞

−∞

∫ ∞

−∞C(θ, θ)f(θ,y)dθdy

0 0 0

(θ−θ)2^ |θ−θ|^

θ θ

(θ,θ)^CU

θ^ ^ ^

∆/2−∆/2θ θ θ

1

11

[A] Considerar entonces la estimacion que mi-

nimiza el error cuadratico medio (MMSE)

mınθ

E[

(θ − θ)2]

Entonces recordando que

f(θ|y) =f(θ,y)

f(y)

el riesgo esta dado por

RMS =

∫ ∞

−∞f(y)

[∫ ∞

−∞(θ − θ)2f(θ|y)dθ

]

dy

Como f(y) ≥ 0 ∀y ⇒ la minimizacion de RMS

es equivalente a

mınθ

∫ ∞

−∞(θ − θ)2f(θ|y)dθ

Tomando la parcial de la nueva funcion de cos-

to con respecto de θ (regla de Leibniz) e igua-

lando a cero, se obtiene la estimacion optima

θMS =∫ ∞

−∞θ f(θ|y)dθ = E[θ|y]

12

La funcion de riesgo mınima

RMS =

∫ ∞

−∞f(y)V (θ|y)dy

donde

V (θ|y) =∫ ∞

−∞[θ − E(θ|y)]2f(θ|y)dθ

es decir la varianza condicional de θ dado el

vector de observacion Y, promediado sobre to-

dos los posibles valores de Y.

[B] Analizar ahora la estimacion que minimiza

el valor absoluto del error

mınθ

E[

|θ − θ|]

el riesgo esta dado por

RABS =

∫ ∞

−∞f(y)

[∫ ∞

−∞|θ − θ|f(θ|y)dθ

]

dy

De forma similar al caso anterior, el problema

de optimizacion es equivalente a

mınθ

∫ θ

−∞(θ − θ)f(θ|y)dθ +

∫ ∞

θ(θ − θ)f(θ|y)dθ

13

Al tomar la parcial de la nueva funcion de costo

con respecto de θ (regla de Leibniz) e igualan-

do a cero, se obtiene

∫ θABS

−∞f(θ|y)dθ =

∫ ∞

θABS

f(θ|y)dθ

es decir, el valor estimado θABS representa la

mediana de la densidad condicional f(θ|y) ⇒estimado de valor absoluto mınimo del error

(MAVE) θABS = θMAVE.

[C] Considerar una funcion de error uniforme,

y la funcion de riesgo es

RU =

∫ ∞

−∞f(y)

∫ θ−∆2

−∞f(θ|y)dθ +

∫ ∞

θ+∆2

f(θ|y)dθ

dy

⇒ RU =∫ ∞

−∞f(y)

1−∫ θ+∆

2

θ−∆2

f(θ|y)dθ

dy

donde se observa que

∫ θ+∆2

θ−∆2

f(θ|y)dθ = P

[

θ − ∆

2≤ Θ ≤ θ +

∆

2

∣∣∣∣y

]

14

Por lo tanto, minimizar RU es equivalente a

maxθ

∫ θ+∆2

θ−∆2

f(θ|y)dθ

⇒ el valor optimo maximiza f(θ|y) (moda) →estimador maximo a posteriori (MAP)

∂f(θ|y)∂θ

∣∣∣∣∣θ=θMAP

= 0 o∂ ln f(θ|y)

∂θ

∣∣∣∣∣θ=θMAP

= 0

Pero multiples puntos extremos, utilizando la

ley de Bayes

f(θ|y) =f(y|θ)f(θ)

f(y)

se obtiene una caracterizacion alternativa de la

ecuacion MAP:

∂ ln f(θ|y)∂θ

=∂ ln f(y|θ)

∂θ+

∂ ln f(θ)

∂θ= 0

Ejemplo: considerar que K observaciones estan

por la expresion

Yi = M +Ni i = 1, . . . ,K

donde M y Ni son VA’s Gaussianas indepen-

dientes con media cero y varianza σ2 . Encon-

trar las estimaciones mMS, mMAV E y mMAP .

�15

PROPIEDADES:

i) La estimacion que minimiza el error cuadrati-

co promedio (MMSE) es siempre el valor es-

perado de la densidad a posteriori (promedio

condicional).

ii) La estimacion maxima a posteriori (MAP)

es el valor de θ donde la densidad a posteriori

tiene su maximo.

iii) Para una clase grande de funciones de cos-

to, el estimador optimo es el promedio condi-

cional, siempre y cuando, la densidad a poste-

riori sea unimodal (maximo unico y distribucion

acumulada convexa) y simetrica alrededor de la

probabilidad condicional.

f( | y )θ

0 0

f( | y )θ

θ θ

MAPMMSEMAVE

MAP

MAVE MMSE

moda, mediana, ymedia

modamediana

media

16

iv) Si en el criterio MAP, se considera que

f(θ) = 0 −∞ < θ < ∞ (no existe informacion a

priori), el estimado ML puede verse como un

caso especial del MAP.

v) El estimado MAP para una densidad Gaus-

siana del parametro desconocido θ es equiva-

lente al ML si la varianza crece, es decir, la

distribucion del parametro θ tiene a un distri-

bucion uniforme ⇒∂ ln f(θ)

∂θ= 0

17

Desigualdad de Cramer-Rao

• Con el objeto de evaluar si una estimacion es

buena se debe considerar: polarizacion, varian-

za del error, y ası determinar su consistencia.

• Calcular estos ındices de manera explıcita

puede ser complicado ⇒ se emplean desigual-

dades de acuerdo a la naturaleza del parametro

estimado.

• Asumir un parametro constante ⇒ Desigual-

dad de Cramer-Rao.

TEOREMA: considerar el vector de K ob-

servaciones Y = [Y1 . . . YK], y θ como una

estimacion no polarizada de θ ⇒ se cumple

V[

θ − θ|θ]

≥

E

(

∂ ln f(y|θ)∂θ

)2

−1

donde

E

(

∂ ln f(y|θ)∂θ

)2

= −E

[

∂2 ln f(y|θ)∂θ2

]

.

18

Asumiendo que

∂f(y|θ)∂θ

&∂2f(y|θ)

∂θ2

existen y son integrables en el sentido absoluto.

Demostracion: como se asume una estima-

cion no polarizada ⇒ E[θ|θ] = θ y por lo tanto

E[θ−θ|θ] = 0. Diferenciando esta expresion con

respecto de θ se tiene

d

dθ

∫ ∞

−∞(θ − θ)f(y|θ)dy = 0

Aplicando el Regla de Leibniz se puede introdu-

cir la operacion derivada dentro de la integral

y se obtiene

∫ ∞

−∞(θ − θ)

∂f(y|θ)∂θ

dy =

∫ ∞

−∞f(y|θ)dy = 1

Recordar que ∂ ln g(x)∂x = 1

g(x)∂g(x)∂x y entonces se

tiene

∂f(y|θ)∂θ

= f(y|θ)∂ ln f(y|θ)∂θ

19

Sustituyendo se encuentra que∫ ∞

−∞(θ − θ)f(y|θ)∂ ln f(y|θ)

∂θdy = 1

Recordar la desigualdad de Cauchy-Schwarz

| < x, y > | ≤ ‖x‖‖y‖aplicando esta desigualdad se obtiene{∫ ∞

−∞(θ − θ)2f(y|θ)dy

}{∫ ∞

−∞

[∂ ln f(y|θ)

∂θ

]2

f(y|θ)dy}

≥ 1

y concluimos

V[

θ − θ|θ]

E

(

∂ ln f(y|θ)∂θ

)2

≥ 1

Enseguida se demuestra la equivalencia para

el valor esperado, ya que∫∞−∞ f(y|θ)dy = 1 se

obtiene

∫ ∞

−∞

∂f(y|θ)∂θ

dy = 0 ⇒∫ ∞

−∞

∂ ln f(y|θ)∂θ

f(y|θ)dy = 0

Tomando nuevamente la parcial con respecto

de θ, se concluye que

∫ ∞

−∞

∂2 ln f(y|θ)∂θ2

f(y|θ)dy +

∫ ∞

−∞

∂ ln f(y|θ)∂θ

∂f(y|θ)∂θ

dy = 0

20

A partir de esta ultima expresion se obtiene

E

[

∂2 ln f(y|θ)∂θ2

]

+ E

(

∂ ln f(y|θ)∂θ

)2

= 0

�

Al aplicar la desigualdad de Cauchy-Schwarz,

se logra la igualdad si los elementos son co-

lineales

⇒ ∂ ln f(y|θ)∂θ

= ξ(θ)(θ − θ) ∀y, θ

Cualquier estimador que cumple la igualdad, se

define como un estimador eficiente.

Observar que si existe un estimador eficiente,

este cumple el criterio de maxima verosimilitud

(ML) cuando θ = θML

∂ ln f(y|θ)∂θ

∣∣∣∣∣θ=θML

= ξ(θ)(θ − θ)∣∣∣θ=θML

21

Ejemplo 1: considerar K observaciones, tal que

Yi = m+ Vi i = 1, . . . ,K

donde m es un parametro desconocido y las

muestras de ruido Gaussiano Vi son i.i.d con

E[Vi] = 0 y E[V 2i ] = σ2, donde tambien se

desconoce σ2. (A) Encontrar los estimados de

m y σ2. (B) ¿El estimado obtenido es eficien-

te ? (C) Obtener la varianza condicionada del

error V [m−m|m]. �

Ejemplo 2:considerar K observaciones, tal que

Yi = Γ(m) + Vi i = 1, . . . ,K

donde m es un parametro desconocido, Γ(·) es

una funcion no-lineal biyectiva, y las muestras

de ruido Gaussiano Vi son i.i.d con E[Vi] = 0

y E[V 2i ] = σ2. (A) Encontrar el estimado ML

mML. (B) Utilizar la desigualdad de Cramer-

Rao para obtener una cota inferior en la va-

rianza del error. ¿De que parametro depende

esta varianza?.

22

Solucion: la densidad condicional esta dada

por

f(y|m) =

[

1√2πσ

]K

e− 1

2σ2

∑Ki=1[yi−Γ(m)]2

por lo que la condicion de ML es

∂ ln f(y|m)

∂m=

1

σ2

K∑

i=1

[yi − Γ(m)]∂Γ(m)

∂m= 0

y como ∂Γ(m)∂m 6= 0, entonces ya que se asume

que Γ es biyectiva, se tiene

mML = Γ−1

1

K

K∑

i=1

yi

Para obtener el estimado de la varianza del

error, se asume que la estimacion no tiene po-

larizacion y se toma nuevamente la derivada

con respecto de m

∂2 ln f(y|m)

∂m2=

1

σ2

K∑

i=1

[yi − Γ(m)]∂2Γ(m)

∂m2− K

σ2

[∂Γ(m)

∂m

]2

Recordar que

E[Yi − Γ(m)] = E[Vi] = 0

23

Por lo tanto

E

[

∂2 ln f(y|m)

∂m2

]

= −K

σ2

[

∂Γ(m)

∂m

]2

y se llega por medio de la desigualdad de Cramer-

Rao a

V [mML −m|m] ≥ σ2

K[∂Γ(m)∂m

]2.

�

• Asumir ahora un parametro aleatorio y asu-

mir que se conoce la densidad conjunta f(y, θ)

del vector de observacion Y y el parametro des-

conocido θ.

TEOREMA: considerar el vector de K obser-

vaciones Y = [Y1 . . . YK], y θ como una VA ⇒el error medio cuadratico cumple la siguiente

desigualdad

E[

(θ − θ)2]

≥

E

(

∂ ln f(y, θ)

∂θ

)2

−1

24

donde

E

(

∂ ln f(y, θ)

∂θ

)2

= −E

[

∂2 ln f(y, θ)

∂θ2

]

.

Asumiendo que

∂f(y, θ)

∂θ&

∂2f(y, θ)

∂θ2

existen y son integrables en el sentido absoluto

con respecto de y y θ. La igualdad se cumple,

si y solo si,

∂ ln f(y, θ)

∂θ= k[θ − θ] ∀y, θ

o

∂2 ln f(y, θ)

∂θ2= −k.

PROPIEDADES

• Observar que la funcion de densidad es con-

junta, y la esperanza se toma sobre y y θ.

25

• Como f(y, θ) = f(θ|y)f(y), la condicion de

igualdad se convierte en

∂2 ln f(θ|y)∂θ2

= −k

Lo que implica que

f(θ|y) = e−k2θ

2+C1θ+C2 ∀y, θ

donde C1 y C2 so constantes, es decir, la pro-

babilidad a posteriori de θ debe ser Gaussiana

para todo y, si se quiere un estimado eficien-

te.

• Si se cumple ∂2 ln f(y,θ)∂θ2

= −k (condicion para

un maximo), el estimado MAP sera eficiente.

• Como el MMSE es optimo (error mınimo),

este no puede tener un error mayor al MAP y

en consecuencia θMAP = θMS, cuando existe

un estimado eficiente ⇒ mas sencillo encon-

trar el estimado MAP, que el MMSE (media

condicionada).

26

Estimacion Multiple de Parametros

• Considerar que se buscan estimar K parame-

tros de manera simultanea. Definir el vector de

parametros desconocidos como θ ∈ RK

θ = [θ1 . . . θK]⊤

Asumir que el vector de observacion Y es N-

dimensional, es decir

Y = [Y1 . . . YN ]⊤ ∈ RN

Para compactar la notacion, definir el operador

∇θ ,[

∂

∂θ1. . .

∂

∂θK

]⊤

Si se tiene un vector N-dimensional

X = [X1 . . . XN ]⊤

y se le aplica el operador anterior obtenemos

∇θX⊤ =

∂X1∂θ1

. . . ∂XN∂θ1... . . . ...

∂X1∂θK

. . . ∂XN∂θK

27

• Dependiendo de la naturaleza de los parame-

tros a estimar se estudian 2 enfoques: (A) Parame-

tros No-Aleatorios y (B) Parametros Aleato-

rios.

y

θ

Espacio de ParámetrosK-dimensional

θθEspacio de Observación

N-dimensional

Mapeof(y| )

Estimación

(Estimación K-dimensional)

θ (y)θθ

θθθ

FUENTE

28

• Asumir un vector de parametros no-aleatorio

θ.

⇒ El criterio de Maxima Verosimilitud (ML) se

convierte en

∇θ [ln f(y|θ)]|θ=θML

= 0

• Criterios para analizar una buena estimacion:

i) Polarizacion

E[

θ|θ]

= θ + θB

donde θB ∈ RK representa el vector de pola-

rizacion. Si cada elemento en θB es cero ⇒estimacion no-polarizada.

ii) Matriz de Covarianza Condicional

C = E[

(θ − θB)(θ − θB)⊤|θ]

∈ RK×K

donde θ = θ − θ representa el error de estima-

cion. Tomando la i-esima fila y j-esima colum-

na tenemos

Cij = E[

(θi − θB,i)(θj − θB,j)|θ]

29

Es decir, los elementos de la diagonal de C

representan la varianza condicionada del error

Cii = V[

θi|θ]

TEOREMA: (Desigualdad de Cramer-Rao) si

θ es un estimado sin polarizacion de θ basado

en el vector de observaciones Y ⇒ la matriz de

covarianza del error se encuentra acotada por

debajo por la inversa de la Matriz de Informa-

cion de Fisher J ∈ RK×K:

E[

(θ − θ)(θ − θ)⊤|θ]

≥ J−1

donde

J = E[

{∇θ [ln f(y|θ)]} {∇θ [ln f(y|θ)]}⊤]

= −E[

∇θ {∇θ (ln f(y|θ))}⊤]

,

se asume que J > 0 y

∂f(y|θ)∂θi

&∂2f(y|θ)∂θi∂θj

∀i, j

existen y son integrables en el sentido absoluto.

30

Lo que puede escribirse como

V[

θi|θ]

≥ Jii

donde Jii representa el i-esimo elemento en la

diagonal de J−1.

El componente en la i-esima fila y j-esima co-

lumna de J esta dado por

Jij = E

[

∂ ln f(y|θ)∂θi

· ∂ ln f(y|θ)∂θj

∣∣∣∣∣θ

]

= −E

[

∂2 ln f(y|θ)∂θi∂θj

∣∣∣∣∣θ

]

Observar que la igualdad se mantiene si se sa-

tisface

∇θ [ln f(y|θ)] = K(θ)[

θ − θ]

donde K(θ) ∈ RK×K representa una matriz

que, en general, puede depender del parametro

desconocido.

31

• Asumir ahora un vector de parametros alea-

torio θ definido en una region O ⊂ RK y un

vector de salidas y tambien definido en una

region Y ⊂ RN .

[A] Considerar la estimacion que minimiza el

error cuadratico medio (MMSE)

mınθ

E[

‖θ − θ‖2]

donde ‖x‖2 = x⊤x representa la norma Eucli-

diana ∀x ∈ RK. El riesgo esta dado por

RMS =

∫

O

∫

Y‖θ − θ‖2f(y, θ)dydθ

=∫

Yf(y)

[∫

O‖θ − θ‖2f(θ|y)dθ

]

dy

Como f(y) ≥ 0 ∀y ⇒ la minimizacion de RMSes equivalente a

mınθ

∫

O‖θ − θ‖2f(θ|y)dθ

Tomando la parcial de la nueva funcion de cos-

to con respecto de θ e igualando a cero, y al

considerar que

∂x⊤Ax

∂x= (A⊤ +A)x A ∈ R

K×K

32

⇒ ‖θ − θ‖2

∂θ= −2(θ − θ)

se obtiene la estimacion optima

θMS =

∫

Oθ f(θ|y)dθ = E[θ|y].

[B] Considerar el estimado MAP, este criterio

es equivalente a minimizar

RMAP = 1−∫

‖θ−θ‖∞<∆2

f(θ|y)dθ

lo que conlleva a maximizar f(θ|y) si ∆ es su-

ficientemente pequeno, y se deduce entonces

el siguiente criterio

∇θ [ln f(θ|y)]|θ=θMAP

= 0

TEOREMA: (Desigualdad de Cramer-Rao) si

θ es un estimado sin polarizacion de θ basado

en el vector de observaciones Y ⇒ la matriz de

covarianza del error se encuentra acotada por

debajo por:

E[

(θ − θ)(θ − θ)⊤]

≥ L−1

33

donde L ∈ RK×K

L = E[

{∇θ [ln f(y, θ)]} {∇θ [ln f(y, θ)]}⊤]

= −E[

∇θ {∇θ (ln f(y, θ))}⊤]

,

se asume que L > 0, y

∂f(y, θ)

∂θi&

∂2f(y, θ)

∂θi∂θj∀i, j

existen y son integrables en el sentido absoluto.

34

Est. Optima Lineal

En ocasiones no se tiene acceso a la funcion de

densidad conjunta entre el parametro θ (alea-

torio) y la medicion y (caso escalar) para cal-

cular las estimaciones optimas.

Pero se pueden evaluar los momentos de pri-

mer y segundo orden de la observacion (E[Y ], E[Y 2]),

el valor medio del parametro desconocido E[Θ],

y el estadıstico conjunto E[ΘY ].

PROBLEMA: asumir un parametro aleatorio

desconocido θ y una observacion y ⇒ encon-

trar el parametro estimado θ segun el siguiente

criterio

mınθ=ay+b

E[

(Θ− Θ)2]

donde a y b son las constantes a calcular.

Solucion: la funcion de riesgo esta dada por

RLMS = E[

(Θ− Θ)2]

=

∫ ∞

−∞

∫ ∞

−∞(θ−θ)2f(θ, y)dθ dy

=

∫ ∞

−∞

∫ ∞

−∞(θ − ay − b)2f(θ, y)dθ dy

35

calculado las condiciones necesarias para un

pto. extremo

∂RLMS

∂a= 0 &

∂RLMS

∂b= 0

y verificando

∂2RLMS

∂a2= 2E[Y 2] > 0 &

∂2RLMS

∂b2= 2 > 0

Se obtienen las siguientes condiciones para un

mınimo:

−E[ΘY ] + aE[Y 2] + bE[Y ] = 0

−E[Θ] + aE[Y ] + b = 0

y despejando

a =E[Θ Y ]−E[Θ]E[Y ]

E[Y 2]−E[Y ]2

b = E[Θ]− E[Y ] · E[Θ Y ]−E[Θ]E[Y ]

E[Y 2]− E[Y ]2

Recordando que

Cov(X, Y ) = E[X Y ]−µXµY & ρXY =Cov(X, Y )

σXσY

donde µX = E[X], µY = E[Y ], σX =√

V [X] =

E[(X − µX)2] y σY =√

V [Y ].

36

Se obtienen los valores optimos

a =Cov(Θ, Y )

σ2Y= ρΘY

σΘσY

b = µΘ − µYσΘσY

ρΘY

y el costo mınimo es

RLMS = σ2Θ

(

1− ρ2ΘY

)

Si se asume que E[Θ] = E[Y ] = 0 ⇒ el esti-

mado es no-polarizado (b = 0):

θMLS = CΘYC−1Y Y · y

donde CΘY , E[Θ Y ] y CY Y , E[Y 2].

PROBLEMA: asumir un vector de parame-

tros aleatorios desconocidos θ ∈ RK y un

vector de observaciones y ∈ RN con valores

esperados cero (E[Θ] = 0 y E[Y] = 0) y K < N

⇒ encontrar el vector de parametros estimados

θ segun el siguiente criterio (varianza mınima)

mınθ=Ay

E[

‖Θ− Θ‖2]

donde A ∈ RK×N .

37

Solucion: observar que

R = E[

‖Θ− Θ‖2]

= E[

(Θ− Θ)⊤(Θ− Θ)]

= Tr{

E[

(Θ− Θ)(Θ− Θ)⊤]}

= Tr{

E[

(Θ−AY)(Θ−AY)⊤]}

= Tr{

CΘΘ − CΘYA⊤ −ACYΘ +ACYYA⊤}

donde Tr{·} representa el operador de traza

y CUV , Cov[U,V] = E[

(U− µU)(V − µV)⊤]

(matriz de covarianza). Recordando que

∂Tr {UXV}∂X

= U⊤V⊤

∂Tr{

UXVX⊤W}

∂X= U⊤W⊤XV⊤ +WUXV

donde U,X,V y W son matrices con dimensio-

nes compatibles. Por lo tanto, al considerar las

condiciones necesarias para un mınimo ∂R∂A = 0,

se obtiene A = CΘYC−1YY y el estimado MLS

esta dado por

ΘMLS = CΘYC−1YYy

38

Enseguida, si se asume que Θ y Y no tienen

valores esperados cero (E[Θ] = µΘ y E[Y] =

µY), la estructura del estimado cambia

θ = Ay + b

donde b ∈ RK, y los valores optimos estan da-

dos por

A = CΘYC−1YY

& b = µΘ − CΘYC−1YY

µY

Dos propiedades importantes de la solucion opti-

ma

E[

(Θ− ΘMLS)Y⊤] = 0

E

[

(Θ− ΘMLS)ΘMLS⊤]

= 0

lo que quiere decir que el error de estimacion

es ortogonal al vector de observacion y al esti-

mado en sı.

39

PROBLEMA: asumir un vector de parame-

tros aleatorios desconocidos θ ∈ RK (E[Θ] =

0) y un vector de observaciones y ∈ RN

(K < N). Asumir que el vector de observa-

ciones Y depende linealmente del vector de

parametros Θ

Y = HΘ+N

donde H ∈ RN×K es una matriz conocida y N ∈

RN es un vector de ruido Gaussiano (E[N] = 0

y E[NN⊤] = CNN > 0) ⇒ encontrar el vector

de parametros estimados θ segun el criterio de

varianza mınima

mınθ=Ay

E[

‖Θ− Θ‖2]

donde A ∈ RK×N .

Solucion: la funcion de costo en la optimiza-

cion esta dada por

J = E[

(Θ− Θ)⊤(Θ− Θ)]

= Tr{

E[

(Θ− Θ)(Θ− Θ)⊤]}

= Tr{

E[

(Θ−AHΘ−AN)(Θ−AHΘ−AN)⊤]}

40

= Tr{

CΘΘ − 2AHCΘΘ +AHCΘΘH⊤A⊤

+ACNNA⊤}

∴ Al aplicar la condicion de un punto extremo∂J∂A = 0 se obtiene

−CΘΘH⊤ +AHCΘΘH⊤ +ACNN = 0

A partir de esta ultima ecuacion se deduce la

solucion optima A y se calcula el vector esti-

mado

⇒ θ = CΘΘH⊤ (HCΘΘH⊤ + CNN

)−1y

41

Estimacion de Mınimos Cuadrados

FORMULACION: en el problema de estima-

cion de mınimos cuadrados (least-square) se

busca calcular un vector de parametros des-

conocidos (constantes) θ ∈ RK, en base a un

vector de mediciones y ∈ RN y asumiendo una

relacion lineal entre ellos

Y = Hθ +N

donde H ∈ RN×K es una matriz conocida y

N ∈ RN es un vector de ruido o errores. El

criterio de diseno se basa en minimizar el error

cuadratico entre el vector de medicion y y su

estimado y (y = Hθ).

Dependiendo de la formulacion de la funcion

de costo se derivan las soluciones

(I) Mınimos Cuadrados Estandar

mınθ

‖y − y‖2

⇒ θ =(

H⊤H)−1

H⊤y

42

Solucion: la funcion de costo esta dada por

J = (y − y)⊤(y − y)

= Tr{

(y −Hθ)(y −Hθ)⊤}

Al tomar la condicion para un punto extremo∂J∂θ

= 0 se obtiene

−H⊤y+H⊤Hθ = 0 ⇒ H⊤(y −Hθ) = 0

y al despejar se deduce el estimado optimo. �

(II) Mınimos Cuadrados con Pesos

mınθ

(y − y)⊤W(y − y) W > 0

⇒ θ =(

H⊤WH)−1

H⊤Wy

(III) Mınimos Cuadrados Regularizado

mınθ

‖y − y‖2 + θ⊤Rθ R > 0

⇒ θ =(

R+H⊤H)−1

H⊤y

43

Ejemplo 1: considerar que se tienen N medi-

ciones dadas por

Yi = θ +Ni i = 1, . . . , N

donde θ es un parametro constante y desco-

nocido, y Ni son muestras de ruido Gaussiano.

Obtener el estimado de mınimos cuadrados pa-

ra θ. �

Ejemplo 2: suponer que se tienen 3 mediciones

de la senal sk = θek/2 k = 1,2,3, donde θ es

un parametro desconocido. Considerar que las

mediciones estan dadas por y1 = 1.5, y2 = 3.0

y y3 = 5.0. Encontrar el estimado de mınimos

cuadrados para θ. �

44

Est. Recursiva de Mınimos Cuadrados

Considerar que no se tiene la informacion

completa de las mediciones, y se busca ge-

nerar un estimado que se actualize con cada

nueva medicion ⇒ estimacion recursiva.

Ademas se requiere dar mayor peso a la infor-

macion de las mediciones actuales y menos

a las pasadas ⇒ factor de olvido λ.

Considerar la siguiente funcion de costo

mınθ

N∑

i=1

λN−i(yi − yi)2 0 < λ ≤ 1

∼ mınθ

(y−y)⊤

λN−1

λN−2

. . .

1

︸ ︷︷ ︸

Λ

(y−y)

con y = [y1 . . . yN ]⊤ y y = [y1 . . . yN ]⊤, ∴ la

solucion optima esta dada por

θ =(

H⊤ΛH)−1

H⊤Λy

45

Considerando que

H =

h⊤1...

h⊤N

hi ∈ R

K

⇒ el estimado optimo θ puede re-escribirse co-

mo

θ =

N∑

i=1

λN−ihih⊤i

−1 N∑

i=1

λN−ihiyi

Definir la matriz de covarianza como

PN ,N∑

i=1

λN−ihih⊤i = λPN−1 + hNh⊤

N

y el vector

ηN ,N∑

i=1

λN−ihiyi = ληN−1 + hNyN

⇒ El estimado optimo en la N-esima iteracion

esta dado por

θN = P−1N ηN

46

Enseguida se aplica el lema de la inversa de unmatriz:

(A+UBV)−1 = A−1 −A−1U(B−1 +VA−1U

)−1VA−1

donde A es invertible.

Entonces, la inversa de PN puede calcularse

por

P−1N = λ−1P−1

N−1 −λ−2P−1

N−1hNh⊤NP−1

N−1

1+ λ−1h⊤NP−1

N−1hN

Definir ΦN , P−1N y el vector de ganancia

KN ,λ−1P−1

N−1hN

1+ λ−1h⊤NP−1

N−1hN

⇒ ΦN = λ−1ΦN−1 − λ−1KNh⊤NΦN−1

Por lo que es facil verificar que

KN = ΦNhN

De esta manera, el estimado optimo puede es-

cribirse por

θN = ΦNηN = λΦNηN−1 +ΦNhN︸ ︷︷ ︸

KN

yN

47

Utilizando la expresion para ΦN se obtiene

θN = ΦN−1ηN−1︸ ︷︷ ︸

θN−1

−KNh⊤N ΦN−1ηN−1︸ ︷︷ ︸

θN−1

+KNyN

es decir

θN = θN−1 +KN

[

yN − h⊤N θN−1

]

︸ ︷︷ ︸

error a priori

ALGORITMO RECURSIVO DE MINIMOS

CUADRADOS (RLS):

Inicializacion: θ0 = 0, Φ0 = δ−1I y n = 1.

1: Calcular el vector de ganancia

Kn =λ−1Φn−1hn

1+ λ−1h⊤nΦn−1hn

2: Actualizar la inversa de la covarianza

Φn = λ−1(

I−Knh⊤n

)

Φn−1

3: Actualizar el estimado optimo

θn = θn−1 +Kn

[

yn − h⊤n θn−1

]

4: Tomar una nueva medicion y aumentar el

contador de iteraciones n = n+1.

48

PROPIEDADES:

I. La memoria del algoritmo RLS esta dada

aproximadamente por 11−λ.

II. Si λ = 1 ⇒ la memoria es infinita.

III. Observar que la actualizacion del estima-

do, se utiliza el error a priori (innovacion) yn−h⊤n θn−1.

IV. En la funcion de costo se emplean los erro-

res a posteriori yn − h⊤n θn.

V. El algoritmo RLS converge aproximadamen-

te en 2K iteraciones.

VI. El RLS puede presentar problemas de esta-

bilidad numerica (errores de redondeo, singu-

laridad de la matriz de covarianza, etc.).

49

Mınimos Cuadrados No-lineales

FORMULACION: Asumir ahora que se tie-

ne una ventana de N mediciones (y1, . . . , yN) y

que se modelan por medio de una funcion no-

lineal conocida f(·) de un vector de parame-

tros desconocidos θ (constantes)

Yi = f(hi, θ) + Vi i ∈ [1, N ]

donde hi son parametros o valores conocidos

y Vi representan muestras de ruido normal; es

decir utilizando notacion vectorial

Y = f(θ) +V

donde f(θ) = [f(h1, θ) . . . f(hN , θ)]⊤ y V =

[V1 . . . VN ]⊤ denota el vector de ruido. Por lo

que se busca encontrar el vector de parametros

estimados θ tal que

mınθ

1

2‖y − f(θ)‖2,

a traves de una busqueda iterativa.

50

Solucion: definiendo primero la estructura ite-

rativa de busqueda como

θm = θm−1 +∆θm m ≥ 1,

partiendo de un punto de inicio θ0 ∈ RK, y

considerar una aproximacion de Taylor para la

funcion no-lineal f(θ)

f(θm) ≈ f(θm−1) + Jm−1∆θm,

donde

Jm−1 =∂f

∂θ

∣∣∣∣∣θ=θm−1

=(

∇θf⊤)⊤∣∣∣∣θ=θm−1

∈ RN×K.

De manera que la funcion de costo a minimizar

iterativamente se define como

mın∆θm

Jm

donde

Jm =1

2‖y− fm−1−Jm−1∆θm‖2 =

1

2‖∆ym−1−Jm−1∆θm‖2

y ademas

fm−1 = f(θm−1)

∆ym−1 = y − fm−1.

51

En la m-esima iteracion, Jm es un funcion cuadrati-ca con respecto de ∆θm por lo que existe unasolucion unica, dada por

∆θm =(

J⊤m−1Jm−1

)−1J⊤m−1∆ym−1.

y se genera entonces una secuencia {θm} quetiende a un mınimo (local) que depende delpunto de inicio θ0, y la iteracion se detiene si‖∆θm‖ < ǫ donde ǫ > 0 denota el umbral deconvergencia.

De forma alternativa, la funcion de costo sepuede extender a

Jm =1

2(∆ym−1 − Jm−1∆θm)

⊤W(∆ym−1 − Jm−1∆θm)

+ λ∆θ⊤mR∆θm

donde W > 0 (W ∈ RN×N) y R > 0 (R ∈

RK×K) son matrices peso, y λ > 0 es un parame-

tro fijo o adaptivo que controla el paso de ajus-te en cada iteracion ⇒ Algoritmo de Levenberg-Marquardt (mınimos cuadrados amortiguado).

La solucion optima para esta nueva funcion decosto es

∆θm =(

J⊤m−1WJm−1 + λR)−1

J⊤m−1W∆ym−1,

donde usualmente R = I o R = diag(J⊤m−1Jm−1).

52

Ejemplo: considerar que se tienen las siguien-

tes 21 muestras experimentalesn xn yn n xn yn1 10 0.0405 11 20 3.61582 11 0.0853 12 21 5.40753 12 0.2505 13 22 3.78074 13 0.2819 14 23 2.38035 14 0.8654 15 24 1.63076 15 1.3559 16 25 0.88267 16 1.7332 17 26 0.31088 17 3.8922 18 27 0.20719 18 4.6613 19 28 0.075310 19 4.9641 20 29 0.0267

21 30 0.0084

1. Asumir un modelo polinomial de orden l

para la estimacion de cada muestra, es de-

cir

yn = θ0+θ1xn+θ2x2n+. . .+θlx

ln n ∈ [1,21]

determinar cuales serıan los parametros opti-

mos (θ0, . . . , θl) tal que se minimice el error

cuadratico

mın(θ0,...,θl)

21∑

n=1

(yi − yi)2

53

Graficar el error optimo en funcion del or-

den del polinomio l con l ∈ [1,15]. ¿Cual es

el orden que mejora la aproximacion a las

muestras?

2. Asumir ahora un modelo Gaussiano para

aproximar las muestras, es decir

yn = θ0 exp

(

− 1

2θ21(xn − θ2)

2

)

n ∈ [1,21]

determinar cuales serıan los parametros opti-

mos (θ0, θ1, θ2) por medio de una estrategia

de mınimos cuadrados no-lineal. ¿Cual es

el efecto de las condiciones iniciales en la

convergencia del algoritmo iterativo? Com-

parando el error de ajuste entre el enfoque

polinominal y el modelo Gaussiano, ¿cual

de los 2 enfoques provee un error menor?

Para ambos casos realizar la derivaciones analıti-

cas e implementar ambos algoritmos en Matlab.

Tarea # 3

Resolver los siguientes problemas del libro Prin-

ciples of Signal Detection and Parameter Esti-

mation, B. C. Levy.

4.2 (pag. 159)

4.5 (pag. 160)

4.7 (pag. 161)

4.9 (pag. 162)

4.11 (pag. 163)

4.13 (pag. 165)

Ademas del libro Optimal State Estimation (Dan

Simon, Ed. Wiley Inter-Science, 2006) resolver

54

3.7 y 3.8 (pag. 103)

3.13 (pag. 105)