Transcript MMSE-Estimation - Computer Science Department, Technion

Topics in MMSE Estimation for
Sparse Approximation*
Michael Elad
Joint work with
The Computer Science Department
The Technion – Israel Institute of technology
Haifa 32000, Israel
Irad Yavneh Matan Protter Javier Turek
The CS Department, The Technion
Part I - Motivation
Denoising By Averaging
Several Sparse
Representations
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
2
Sparse Representation Denoising
 Assume that we get a noisy
measurement vector
x
K
 Sparse representation modeling:
N
y  x  v  D  v
A fixed Dictionary
D
where is AWGN
 Our goal – recovery of x (or α).
α
 The common practice – Approximate
the solution of
min 

Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
0
0
s.t. D  y
2
2
 2
3
Orthogonal Matching Pursuit
OMP finds one atom at a time for min  0 s.t. D  y 2  2
0
2
approximating the solution of

Main Iteration
n 1
for 1  i  K
1. Compute E(i)  min z  di  r
Initialization
z
0
n  0,   0
r 0  y  D0  y
and S0   
n  n 1
2. Choose i0 s.t. 1  i  K , E(i0 )  E(i)
3. Update Sn : Sn  Sn 1  {i0 }
4. LS : n  min D  y s.t. sup p  Sn

5. Update Re sidual : rn  y  Dn
No
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
rn
2

Yes
Stop
4
Using several Representations
Consider the denoising problem
min 

0
0
s.t. D  y
2
2
2

and suppose that we can find a
group of J candidate solutions
 j jJ1
Basic Questions:
 What could we do with such a
set of competing solutions in
order to better denoise y?
 Why should this help?
 How shall we practically find
such a set of solutions?
such that
0




N
j 0


j 

2
2
 D j  y   


2
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
 Relevant work:
[Leung & Barron
(’06)] [Larsson & Selen (’07)] [Schintter
et. al. (`08)] [Elad and Yavneh (’08)]
[Giraud (‘08)] [Protter et. al. (‘10)] …
5
Generating Many Representations
Our* Answer: Randomizing the OMP
Main Iteration
n 1
for 1  i  K
1. Compute E(i)  min z  di  r
Initialization
z
0
n  0,   0
r 0  y  D0  y
and S0   
n  n 1
2. Choose i0 with
s.t. probabilit
1  i  K , yE(i
 E(i) c  E(i)
0 )exp
n
n 1
3. Update
Sn : Slets
S
 {i0parameter
}
For now,
set the
c
4. LSmanually
: n  min for
D best
 y sperformance.
.t. sup p  Sn
Later weshall define
a way to set
5. Update Re sidual : rn  y  Dn
it automatically
No
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
* Larsson and Schnitter
propose a more
Yes
and
rn   complicatedStop
deterministic tree
2
pruning method
6
Lets Try
Proposed Experiment :
100
 Form a random D.
 Multiply by a sparse vector α0 ( 0
0
0
D
+=
v
 10 ).
 Add Gaussian iid noise (σ=1) and obtain y .
y
200
0
 Solve the problem
min 

0
0
s.t. D  y
2
 100
2
OMP
using OMP, and obtain  .
 Use RandOMP and obtain

RandOMP
j

1000
j 1
.
 Lets look at the obtained representations …
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
7
Some Observations
350
Random-OMP cardinalities
OMP cardinality
150
300
Random-OMP error
OMP error
We see that
100
̂
Histogram
Histogram
250
0
0
50
200
D̂  y
150
• The OMP gives
the sparsest
solution
2
2
100
50
0
0
10
20
Candinality
30
0
85
40
300
2
D
ˆ  D0
200
y  D 0
150
100
2
0.3
Noise Attenuation
Histogram
105
0.35
Random-OMP denoising
OMP denoising
250
2
2
Random-OMP denoising
OMP denoising
0.25
0.1
0.2
0.3
Noise Attenuation
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
0.4
0.15
0.05
0
• Nevertheless, it
is not the most
effective for
denoising.
• The cardinality of
a representation
does not reveal
its efficiency.
0.2
0.1
50
0
0
90
95
100
Representation Error
5
10
Cardinality
15
20
8
The Surprise … (to some of us)
Lets propose the average
1 1000 RandOMP

j
ˆ

1000 j 1
3
as our representation
1
Averaged Rep.
Original Rep.
OMP Rep.
value
2
0
-1
This representation IS
NOT SPARSE AT ALL but
its noise attenuation is:
0.06 (OMP gives 0.16)
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
-2
-3
0
50
100
index
150
200
9
Repeat this Experiment …
• Dictionary (random) of
size N=100, K=200
0.5
0.45
• σx=1 and ε=10
• We run OMP for denoising.
• We run RandOMP J=1000
times and average
1 J
RandOMP

ˆ   j
J j1
• Denoising is assessed by
2
2
2
y  D 0
2
D
ˆ  D 0
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
RandOMP Denoising Factor
• True support of α is 10
0.4
0.35
0.3
OMP versus RandOMP results
Mean Point
Cases of zero
solution, where
2
y 2  100
0.25
0.2
0.15
0.1
0.05
0
0
0.1
0.2
0.3
0.4
OMP Denoising Factor
0.5
10
Part II - Explanation
It is Time to be
More Precise
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
11
Our Signal Model
x
K
 Assume that α is built by:
 Choosing the support s with
probability P(s) from all the 2K
possibilities Ω.
N
A fixed Dictionary
D
 D is fixed and known.
α
 Lets assume that P(iS)=Pi
are drawn independently.
 Choosing the αs coefficients using
iid Gaussian entries N 0, 2x .


 The ideal signal is x=Dα=Dsαs.
The p.d.f. P(α) and P(x) are clear and known
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
12
Adding Noise
x
K
Noise Assumed:
+
N
A fixed Dictionary
D
α
v
y
The noise v is additive
white Gaussian vector
with probability Pv(v)
 x  y 2


P y x   C  exp 
2 
2



The conditional p.d.f.’s P(y|), P(|y), and even
P(y|s), P(s|y), are all clear and well-defined
(although they may appear nasty).
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
13
The Key – The Posterior P(|y)
We have
access to
MAP*
MAP

ˆ
 ArgMax P( | y)

P  | y 
Oracle
MMSE
known
support s
̂
oracle
MMSE
̂
 E   | y
* Actually,
there is a delicate
with this definition,
 The estimation of x is done
by estimating
α andproblem
multiplication
by D.
due to the unavoidable mixture of continuous and discrete
 These two estimators are PDF’s.
impossible
to compute,
as we
showsupport
next. S.
The solution
is to estimate
the MAP’s
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
14
Lets Start with The Oracle *
P | y , s   P s | y  
Py |  s P s 
 y D  2
s s 

P y |  s   exp

2
2




Py 
  2


P s   exp s 
2
 2 x 
2
 y D  2
s 
s s

P  s | y   exp

2
2 
2
2 x 



1 T
1 

ˆ s   2 Ds Ds  2 I
 x 
 
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
1
1

DsT y
2

Q s1 hs
Comments:
• This estimate is both
the MAP and MMSE.
• The oracle estimate
of x is obtained by
multiplication by Ds.
* When s is known
15
The MAP Estimation
ŝ
P(y | s) 
MAP
 ArgMax P(s | y)  ArgMax
s
s
 P(y | s,  )P( )d
s
s
 ....
s
s
P(y | s)P(s)
P(y)
Based on our prior for
generating the support
P  s    Pi  1  Pj 
T 1

 hs Qs hs log(det(Qs ))  is js
|s|
  x  exp 


2
2


ŝ
MAP
 hsT Qs1 hs log(det(Qs )) 
Pi
 ArgMax exp 


2
s
 2
 is  x
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
 1  P 
js
j
16
The MAP Estimation
 hsT Qs1 hs log(det(Qs ))




2
MAP
 2

ŝ
 ArgMax 

s
  log  Pi   log 1  P  

  
j



is
 x  js
Implications:
 The MAP estimator requires to test all the possible supports for the
maximization. For the found support, the oracle formula is used.
 In typical problems, this process is impossible as there is a
combinatorial set of possibilities.
 This is why we rarely use exact MAP, and we typically replace it with
approximation algorithms (e.g., OMP).
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
17
The MMSE Estimation
MMSE

 E | y   P(s | y)  E | y , s
ˆ
s
This is the oracle for s, as we
have seen before
 hsT Qs1 hs log(det(QEs ))
| y , s Pi   Q 1 h

ˆ s 1  Psj s
 exp 

 
2
2
 is  x js

P(s | y)  P(s)  P(y | s)  ...


ˆ
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
MMSE



  P (s | y )  
ˆs
s
18
The MMSE Estimation
MMSE

 E | y   P(s | y)  E | y , s
ˆ
s
Implications:

ˆ
MMSE
  P (s | y )  
ˆs
s
 The best estimator (in terms of L2 error) is a weighted average of
many sparse representations!!!
 As in the MAP case, in typical problems one cannot compute this
expression, as the summation is over a combinatorial set of
possibilities. We should propose approximations here as well.
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
19
The Case of |s|=1 and Pi=P
 hsT Qs1 hs log(det(Qs )) 
Pi
P(s | y)  exp 


2
2

 is  x
 1
2x
T
2
 exp  2  2
 (y di ) 
2
This is our
 2  x  

c in the
Random-OMP
 Based on this we can propose a greedy
algorithm for both MAP and MMSE:
 1  P 
js
j
The i-th
atom in D
 MAP – choose the atom with the largest inner product (out of K), and
do so one at a time, while freezing the previous ones (almost OMP).
 MMSE – draw at random an atom in a greedy algorithm, based on the
above probability set, getting close to P(s|y) in the overall draw
(almost RandOMP).
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
20
The following results
correspond to a small
dictionary (10×16),
where the combinatorial
formulas can be
evaluated as well.
Parameters:
• N,K: 10×16
• P=0.1
(varying cardinality)
• σx=1
• J=50 (RandOMP)
• Averaged over 1000
experiments
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
Relative Representation Mean-Squared-Error
Comparative Results
1
Oracle
MMSE
MAP
OMP
Rand-OMP
0.8
0.6
0.4
0.2
0
0.2
0.4
0.6

0.8
1
21
Part III – Diving In
A Closer Look At the
Unitary Case
T
T
DD  D D  I
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
22
Few Basic Observations
Let us denote   D T y
2  2x
1 T
1
Qs  2 Ds Ds  2 I 
I
2 2

x
 x
1 T
1
D
y


s
2
2 s


2

oracle

 Qs1 hs  2 x 2  s  c 2  s
ˆs
  x
hs 
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
(The Oracle)
23
Back to the MAP Estimation
 hsT Qs1 hs log(det(Qs )) 
Pi
P  S | y   exp 


2
 2
 is  x
T
s
h Qs1 hs c 2
 2 s
2

2
2
 1  P 
j
js
log(det(Qs ))
1
 S log
2
1  c 2 2x


 c 2 2  Pi 1  c 2
P  S | y    exp  2 i 
  qi
is
is

 1  Pi
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
24
The MAP Estimator
ŜMAP is obtained by
maximizing the expression
 c 2 2  Pi 1  c 2
qi  exp  2 i 

 1  Pi
P  S | y    qi
is
3
Thus, every i such that
qi>1 should be in the
support, which leads to

ˆ MAP
i
MAP
1
i
2
 2
1  Pi
2

2
c i i  c 2 log

Pi 1  c 2

Otherwise
 0
2
0
-1
-2
-3
-3
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
P=0.1
=0.3
x=1
-2
-1
0

1
2
3
25
The MMSE Estimation
Some algebra
and we get that
MMSE
i

ˆ
3
2
i
MMSE
1
P=0.1
=0.3
x=1
0
-1
-2
-3
-3
-2
-1
 c 2 2  Pi 1  c 2
qi  exp  2 i 

 1  Pi
0

Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
1
2
3
qi 2

c i
1  qi
gi
This result leads to a dense
representation vector. The
curve is a smoothed version
of the MAP one.
26
What About the Error ?


E 
ˆ
oracle
MMSE
E 
ˆ


2
2
2
2


n

E 
ˆ

2
2

qi
1  qi
   ...   c  g
 trace Q
1
s
2
2
i
i 1
 
2
MMSE
oracle 

1
  P  s | y  trace Qs  

ˆ
ˆs

2


s
n
n
i 1
i 1

 ...   c 22gi   c 4i2 gi  gi2
MAP
gi 
MAP
 
ˆ
MMSE

ˆ
n
2
2

E 
ˆ
n
MMSE




 ...   c  gi   c 4i2 gi  IMAP
(1  2gi )
i
i 1
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
2
2
i 1

27
A Synthetic Experiment
Relative Mean-Squared-Error
0.25
The following
results correspond
to a dictionary of
size (100×100)
Empirical Oracle
Theoretical Oracle
Empirical MMSE
Theoretical MMSE
Empirical MAP
Theoretical MAP
0.2
Parameters:
• n,K: 100×100
0.15
• P=0.1
• σx=1
• Averaged over
1000 experiments
The average errors
are shown relative
to n2
0.1
0.05
0
0
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
0.2
0.4
0.6
0.8
1

1.2
1.4
1.6
1.8
2
28
Part IV - Theory
Estimation Errors
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
29
Useful Lemma
Let (ak,bk) k=1,2, … ,n be
We are interested in this
pairs of positive real numbers. result because :
Let m be the index of a pair
E 
   c  g
ˆ
such that
a
a

E 
ˆ
E 
ˆ

     c  g   c  g  g 
     c  g   c   g  I (1  2g ) 
k
k
bk

m
bm
.
n
Then
 ak
k 1
n
b
k 1
k
a
 m .
bm
Equality is obtained only if all
the ratios ak/bk are equal.
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
2
2
2
2
2
2
i
i 1
n
2
MMSE
MAP
n
2
oracle
2
n
2
i
i 1
n
i 1
2
i 1
n
2
i
i 1
4 2
i
4 2
i
i
i
2
i
MAP
i
i
This
leads
to …
30
Theorem 1 – MMSE Error
Pk 1  c 2
Define Gk 
. Choose m such that k, Gm  Gk .
1  Pk
Pk  P 

E 
ˆ
MMSE
E 
ˆ
oracle

 

2
2
2
2

1
1

2log

4Gm


 1 2

Gm e
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
e 2
Gm 
4
Otherwise
K
 1
this error ratio
bound becomes

E 
ˆ
MMSE
E 
ˆ
oracle
  Const  logK
 

2
2
2
2
31
Theorem 2 – MAP Error
Pk 1  c 2
Define Gk 
. Choose m such that k, Gm  Gk .
1  Pk
Pk  P 

E 
ˆ
MAP
E 
ˆ
oracle

 

2
2
2
2
1

1  2log G

m

 1 2

Gme
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
Gm  e 1
Otherwise
K
 1
this error ratio
bound becomes

E 
ˆ
MMSE
E 
ˆ
oracle
  Const  logK
 

2
2
2
2
32
The Bounds’ Factors vs. P
Parameters:
25
• P=[0,1]
• σx=1
20
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
Bound Factor
• =0.3
Notice that the
tendency of the
two estimators
to align for P0
is not reflected
in these bounds.
1

1

2log

Gm


 1 2

Gme
15
10
5
0 -4
10

1
1  2log 4G

m

 1 2

Gm e

10
-3
Gm  e 1
Otherwise
e 2
Gm 
4
Otherwise
10
P
-2
10
-1
10
0
33
Part V – We Are Done
Summary and
Conclusions
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
34
Today We Have Seen that …
Sparsity and
Redundancy are
used for denoising
of signals/images
MAP and MMSE enjoy
a closed-form, exact
and cheap formulae.
Their error is bounded
and tightly related to
the oracle’s error
How ?
Unitary
case?
By finding the sparsest
representation and
using it to recover the
clean signal
Yes! Averaging
several rep’s
lead to better
denoising, as it
approximates
the MMSE
Can
we do
better?
More on these (including the slides and the relevant papers) can be found in
http://www.cs.technion.ac.il/~elad
Topics in MMSE Estimation
For Sparse Approximation
By: Michael Elad
35