ECE 531: Detection and Estimation Theory
Natasha Devroye
devroye@ece.uic.edu
http://www.ece.uic.edu/~devroye
Spring 2011
Example of detection
Example of estimation
Goals
• infer value of unknown state of nature based on noisy observations
Mathematically, optimally
Noise
Transmission /
Nature Processing
measurement
phenomenon model of observation decision rule
experiment or transmission estimation function
process
the ``truth’’
mapping from
observation space
model of hypothesis
H to decisions/
estimates
Detection example 1: digital communications
Noise
Source Encoder Channel Decoder Destination
10001010100010
Detect?
Detection example 2: Radar communication
Send
Receive
Hypothesis
Detect?
Hypothesis
Further examples
• Sonar: enemy submarine
• Image processing: detect an aircraft from infrared images
• Biomedicine: cardiac arryhthmia from heartbeat sound wave
• Control: detect occurrence of abrupt change in system to be controlled
• Seismology: detect presence of oil deposit
Difference between detection and estimation?
• Detection:
Discrete set of hypotheses
Right or wrong
• Estimation:
Continuos set of hypotheses
Almost always wrong - minimize error instead
Estimation example 1: communications
• Pulse amplitude modulation (PAM)
Analog source Sampler Transmitter
Receiver?
Estimation example 2: Radar
Send
Receive
Hypothesis
Estimate?
Hypothesis
Our methods
• Will treat everything generally, with a unified mathematical representation
• Bias towards Gaussian noise and linear observation - parameter models
• Examples mainly drawn from communications / radar
Aside: “Classical” vs. “Bayesian”
Classical
• Hypotheses/parameters are fixed, non-random
Bayesian
• Hypotheses/parameters are treated as random variables with
assumed priors (or a priori distributions)
Other useful references:
Course
Harry Textbook:
L. Van Fundamentals
Trees, Detection, of Statistical
Estimation, Signal Processing,
and Modulation Theory, PartVolume
I, II, 1:
III,Estimation
IV Theory, by
H.Steven M.Poor,
Vincent Kay, Introduction
Prentice Hall, to 1993
Signaland (possibly)
Detection andFundamentals
Estimation of Statistical Signal Processing,
Volume
Louis 2: Detection
L. Scharf Theory,
and Cedric by Steven
Demeure, M. Kay,
Statistical Prentice
Signal Hall 1998.
Processing: Detection, Estimation, and Time
OtherAnalysis
Series useful references:
Carl Helstrom,
Harry Elements
L. Van Trees, of SignalEstimation,
Detection, Detection and Estimation.
ModulationIt's out ofPart
Theory, print, so here's
I, II, III, IVmy pdf copy.
H. Vincent Poor, Introduction to Signal Detection and Estimation
Course outline
Notes:
Louis IL.will
main
Series
follow
Scharf
points
andthe courseDemeure,
Cedric textbooksStatistical
fairly closely, using
Signal a mixtureDetection,
Processing: of slides (highlighting
Estimation, and
and with nice illustrations) and more in-depth blackboard derivations/proofs in class. I
Analysis
the Time
will
Carlpost a pdf version
Helstrom, of the
Elements of slides
SignalasDetection
they becomeand ready here, but
Estimation. It'sthe
outderivations
of print, sowill be my
here's givenpdfincopy.
class only.
Notes:
Fundamentals I will follow
of Statistical theProcessing,
Signal course textbooks
Volume 1:fairly closely,
Estimation usingbya Steven
Theory, mixtureM.ofKay,slides (highlighting
Prentice Hall, 1993the
Topics: Estimation
main points Theory:
and with nice illustrations) and more in-depth blackboard derivations/proofs in class. I
General
will postMinimum Variance
a pdf version Unbiased
of the slides asEstimation,
they become Ch.2, 5 here, but the derivations will be given in
ready
Cramer-Rao
class only. Lower Bound, Ch.3
Linear Models+Unbiased Estimators, Ch.4, 6
Maximum LikelihoodTheory:
Topics: Estimation Estimation, Ch.7
Least squares estimation,
General Minimum Variance Ch.8Unbiased Estimation, Ch.2, 5
Bayesian Estimation, Ch.10-12
Cramer-Rao Lower Bound, Ch.3
Kalman
Detection filtering Estimators, Ch.4, 6
Theory:
Linear Models+Unbiased
Statistical
Maximum Detection
LikelihoodTheory, Ch.3 Ch.7
Estimation,
Deterministic
Fundamentals Signals,
of Statistical Ch.4
Signal Processing, Volume 2: Detection Theory, by Steven M. Kay, Prentice Hall 1998.
Least squares estimation, Ch.8
Random Signals, Ch.5
Bayesian Estimation, Ch.10-12
Statistical Detection Theory 2, Ch.6
Detection Theory:
Non-parametric and robust detection
Statistical Detection Theory, Ch.3
Deterministic Signals, Ch.4
Grading: Weekly homeworks (15%), Exam 1 = max(Exam1, Exam 2, Final) (20%), Exam 2 =
Random Signals, Ch.5
max(Exam 2, Final) (20%), Project (15%), Final exam (30%).
Statistical Detection Theory 2, Ch.6
Non-parametric and robust detection
Grading: Weekly homeworks (15%), Exam 1 = max(Exam1, Exam 2, Final) (20%), Exam 2 =
1 of 3 1/11/10 8:50 PM
max(Exam 2, Final) (20%), Project (15%), Final exam (30%).
1 of 3 1/11/10 8:50 PM
Estimation: General Minimum Variance Unbiased Estimation
• Bias: (expected value of estimator - true value of data)
• MVUE:
Estimation: Cramer-Rao lower bound
• Lower bound on variance of ANY unbiased estimator!
• Usage:
• assert whether an estimator is MVUE
• benchmark against which to measure the performance of
an unbiased estimator
• feasibility studies
Noise
• Depends on?
Transmission /
Nature Processing
measurement
Estimation: linear models
• What’s a linear model and why is it useful?
• What can be said?
• Best Linear Unbiased Estimators (BLUE)
Estimation: Maximum Likelihood Estimation
• Alternative to MVUE which is hard to find in general
• Easy to compute - very widely used and practical
• What is the MLE?
• Properties?
Estimation: Least Squares
• Alternative estimator with no general optimality properties, but nice and
intuitive and no probabilistic assumptions on data are made - only need a
signal model
• Advantages?
• Disadvantages?
Estimation: Bayesian Estimation
• Parameter to be estimated is assumed to be random, according to some prior
distribution which models our knowledge of it
• Bayesian Minimum Mean Squared Error (MMSE):
• Applications to Gaussian noise / linear model
Estimation: Bayesian Estimation
• General risk functions - arbitrary “cost” functions
• Maximum a posteriori (MAP) estimation
• Linear MMSE: constrain estimator to be linear - very practical
Estimation: Kalman filtering
• recursive filter for estimating internal state of linear dynamical system from a
series of noisy measurements
• example: tracking a moving target using radar measurements
noisy measurements
linear dynamical system
estimate the position and/or velocity
Estimation: Kalman filtering
• recursive filter for estimating internal state of linear dynamical system from a
series of noisy measurements
• than can recursively estimate/predict and update the state covariances as:
Other useful references:
Course
Harry Textbook:
L. Van Fundamentals
Trees, Detection, of Statistical
Estimation, Signal Processing,
and Modulation Theory, PartVolume
I, II, 1:
III,Estimation
IV Theory, by
H.Steven M.Poor,
Vincent Kay, Introduction
Prentice Hall, to 1993
Signaland (possibly)
Detection andFundamentals
Estimation of Statistical Signal Processing,
Volume
Louis 2: Detection
L. Scharf Theory,
and Cedric by Steven
Demeure, M. Kay,
Statistical Prentice
Signal Hall 1998.
Processing: Detection, Estimation, and Time
OtherAnalysis
Series useful references:
Carl Helstrom,
Harry Elements
L. Van Trees, of SignalEstimation,
Detection, Detection and Estimation.
ModulationIt's out ofPart
Theory, print, so here's
I, II, III, IVmy pdf copy.
H. Vincent Poor, Introduction to Signal Detection and Estimation
Course outline
Notes:
Louis IL.will
main
Series
follow
Scharf
points
andthe courseDemeure,
Cedric textbooksStatistical
fairly closely, using
Signal a mixtureDetection,
Processing: of slides (highlighting
Estimation, and
and with nice illustrations) and more in-depth blackboard derivations/proofs in class. I
Analysis
the Time
will
Carlpost a pdf version
Helstrom, of the
Elements of slides
SignalasDetection
they becomeand ready here, but
Estimation. It'sthe
outderivations
of print, sowill be my
here's givenpdfincopy.
class only.
Notes:
Fundamentals I will follow
of Statistical theProcessing,
Signal course textbooks
Volume 1:fairly closely,
Estimation usingbya Steven
Theory, mixtureM.ofKay,slides (highlighting
Prentice Hall, 1993the
Topics: Estimation
main points Theory:
and with nice illustrations) and more in-depth blackboard derivations/proofs in class. I
General
will postMinimum Variance
a pdf version Unbiased
of the slides asEstimation,
they become Ch.2, 5 here, but the derivations will be given in
ready
Cramer-Rao
class only. Lower Bound, Ch.3
Linear Models+Unbiased Estimators, Ch.4, 6
Maximum LikelihoodTheory:
Topics: Estimation Estimation, Ch.7
Least squares estimation,
General Minimum Variance Ch.8Unbiased Estimation, Ch.2, 5
Bayesian Estimation, Ch.10-12
Cramer-Rao Lower Bound, Ch.3
Detection Theory:
Linear Models+Unbiased Estimators, Ch.4, 6
Statistical
Maximum Detection
LikelihoodTheory, Ch.3 Ch.7
Estimation,
Deterministic
Fundamentals Signals,
of Statistical Ch.4
Signal Processing, Volume 2: Detection Theory, by Steven M. Kay, Prentice Hall 1998.
Least squares estimation, Ch.8
Random Signals, Ch.5
Bayesian Estimation, Ch.10-12
Statistical Detection Theory 2, Ch.6
Detection Theory:
Non-parametric and robust detection
Statistical Detection Theory, Ch.3
Deterministic Signals, Ch.4
Grading: Weekly homeworks (15%), Exam 1 = max(Exam1, Exam 2, Final) (20%), Exam 2 =
Random Signals, Ch.5
max(Exam 2, Final) (20%), Project (15%), Final exam (30%).
Statistical Detection Theory 2, Ch.6
Non-parametric and robust detection
Grading: Weekly homeworks (15%), Exam 1 = max(Exam1, Exam 2, Final) (20%), Exam 2 =
1 of 3 1/11/10 8:50 PM
max(Exam 2, Final) (20%), Project (15%), Final exam (30%).
1 of 3 1/11/10 8:50 PM
Detection: Statistical Detection Theory
• Binary hypothesis testing
Hypothesis
Hypothesis
Detection: Statistical Detection Theory
• Binary hypothesis testing
Detection: Statistical Detection Theory
PD
PFA
Detection: Deterministic Signals
• How to detect known signals in noise?
• The famous matched filter!
T(x)
x[n] X
s[n]
• Generalized matched filter
• > 2 hypotheses
Detection: Random Signals
• What if s[n] is random?
• Key idea behind estimator-correlator:
• Linear model simplifies things again...
Detection: Statistical Decision Theory II
• model for the pdfs under 2 hypotheses are unknown
• Uniformly most powerful test
• Generalized likelihood ratio test
• Bayesian approach
• Wald test
• Rao test
Course structure
http://www.ece.uic.edu/~devroye/courses/ECE531/
