[Boyd]_cvxslides
.pdf
total variation reconstruction example
|
|
|
|
|
2 |
|
|
|
|
i |
0 |
2 |
|
|
|
xˆ |
|
|
|
|
|
||
|
|
|
|
|
|
1 |
|
|
|
−2 |
|
|
|
|
|
||
x 0 |
|
|
|
|
0 |
|
|
|
|
2 |
|
|
|
|
|
|
|
−1 |
|
|
|
|
|
|
|
|
|
i |
|
−2 |
500 |
1000 |
1500 |
xˆ |
0 |
0 |
2000 |
|
|||
2 |
|
|
|
−2 |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
|
|
cor 0 |
|
|
|
i |
0 |
x |
|
|
|
xˆ |
|
|
|
|
|
||
−1 |
|
|
|
|
|
−2 |
|
|
|
−2 |
|
0 |
500 |
1000 |
1500 |
2000 |
0 |
|
|
i |
|
|
|
500 |
1000 |
1500 |
2000 |
500 |
1000 |
1500 |
2000 |
500 |
1000 |
1500 |
2000 |
i
original signal x and noisy |
three |
solutions on trade-o curve |
signal xcor |
kxˆ |
− xcork2 versus φquad(ˆx) |
quadratic smoothing smooths out noise and sharp transitions in signal
Approximation and fitting |
6–15 |
|
|
|
|
|
2 |
|
2 |
|
|
|
xˆ |
0 |
|
|
|
|
|
|
||
1 |
|
|
|
−2 |
||
|
|
|
|
|||
x 0 |
|
|
|
|
0 |
|
|
|
|
|
2 |
||
|
|
|
|
|
||
−1 |
|
|
|
|
|
|
−2 |
|
|
|
xˆ |
0 |
|
500 |
1000 |
1500 |
2000 |
|
||
0 |
|
|||||
2 |
|
|
|
−2 |
||
|
|
|
|
0 |
||
|
|
|
|
|
||
1 |
|
|
|
|
2 |
|
|
|
|
|
|
||
cor 0 |
|
|
|
xˆ |
|
|
x |
|
|
|
0 |
||
−1 |
|
|
|
|
|
|
−2 |
|
|
|
−2 |
||
500 |
1000 |
1500 |
2000 |
0 |
||
0 |
||||||
|
|
i |
|
|
|
|
500 |
1000 |
1500 |
2000 |
500 |
1000 |
1500 |
2000 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
500 |
1000 |
1500 |
2000 |
i
original signal x and noisy |
three solutions on trade-o curve |
signal xcor |
kxˆ − xcork2 versus φtv(ˆx) |
total variation smoothing preserves sharp transitions in signal
Approximation and fitting |
6–16 |
Robust approximation
minimize kAx − bk with uncertain A
two approaches:
•stochastic: assume A is random, minimize E kAx − bk
•worst-case: set A of possible values of A, minimize supA A kAx − bk
tractable only in special cases (certain norms k · k, distributions, sets A)
example: A(u) = A0 + uA1
•xnom minimizes kA0x − bk22
•xstoch minimizes E kA(u)x − bk22 with u uniform on [−1, 1]
•xwc minimizes sup−1≤u≤1 kA(u)x − bk22 figure shows r(u) = kA(u)x − bk2
Approximation and fitting
|
12 |
|
|
|
|
|
10 |
xnom |
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
u) |
6 |
xstoch |
|
|
|
r( |
|
|
|
|
|
|
xwc |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
0 |
|
|
|
|
|
−2 |
−1 |
0 |
1 |
2 |
|
|
|
u |
|
|
|
|
|
|
|
6–17 |
|
¯ |
|
T |
U = P |
stochastic robust LS with A = A + U, U random, E U = 0, E U |
|
|||
minimize |
¯ |
2 |
|
|
E k(A + U)x − bk2 |
|
|
||
• explicit expression for objective:
2 |
|
¯ |
|
|
|
2 |
|
|
|
E kAx − bk2 |
= E kAx − b + Uxk2 |
|
|
||||||
|
¯ |
2 |
+ E x |
T |
U |
T |
Ux |
||
|
= kAx − bk2 |
|
|
||||||
|
¯ |
2 |
+ x |
T |
P x |
|
|
||
|
= kAx − bk2 |
|
|
|
|||||
• hence, robust LS problem is equivalent to LS problem
¯ |
2 |
+ kP |
1/2 |
2 |
minimize kAx − bk2 |
|
xk2 |
||
• for P = δI, get Tikhonov regularized problem
¯ |
2 |
2 |
minimize kAx − bk2 |
+ δkxk2 |
|
Approximation and fitting |
6–18 |
|
¯ |
≤ 1} |
worst-case robust LS with A = {A + u1A1 + · · · + upAp | kuk2 |
||
minimize |
supA A kAx − bk22 = supkuk2≤1 kP (x)u + q(x)k22 |
|
where P (x) = |
A1x A2x · · · Apx , q(x) = Ax¯ − b |
|
• from page 5–14, strong duality holds between the following problems
maximize |
kP u + qk22 |
minimize |
t + λ |
|
|
|
|
|
|||
subject to |
u 2 |
|
1 |
|
|
I |
P |
q |
|
|
|
|
k k2 |
≤ |
|
subject to |
qT |
0 |
t |
0 |
|||
|
|
|
P T |
λI |
0 |
|
|
||||
• hence, robust LS problem is equivalent to SDP
minimize |
t + λ |
|
|
|
|
|
|
I |
P (x) |
q(x) |
|
|
|
|
|||
subject to |
|
P (x)T |
λI |
0 |
0 |
q(x)T |
0 |
t |
|||
Approximation and fitting |
6–19 |
example: histogram of residuals
r(u) = k(A0 + u1A1 + u2A2)x − bk2
with u uniformly distributed on unit disk, for three values of x
frequency
0.25 |
|
|
|
|
|
0.2 |
|
|
xrls |
|
|
0.15 |
|
|
|
|
|
0.1 |
|
|
|
|
|
|
|
|
xtik |
|
xls |
0.05 |
|
|
|
|
|
0 |
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
|
r(u) |
|
|
•xls minimizes kA0x − bk2
•xtik minimizes kA0x − bk22 + δkxk22 (Tikhonov solution)
•xrls minimizes supkuk2≤1 kA0x − bk22 + kxk22
Approximation and fitting |
6–20 |
Convex Optimization — Boyd & Vandenberghe
7.Statistical estimation
•maximum likelihood estimation
•optimal detector design
•experiment design
7–1
Parametric distribution estimation
•distribution estimation problem: estimate probability density p(y) of a random variable from observed values
•parametric distribution estimation: choose from a family of densities px(y), indexed by a parameter x
maximum likelihood estimation
maximize (over x) log px(y)
•y is observed value
•l(x) = log px(y) is called log-likelihood function
•can add constraints x C explicitly, or define px(y) = 0 for x 6 C
•a convex optimization problem if log px(y) is concave in x for fixed y
Statistical estimation |
7–2 |
Linear measurements with IID noise
linear measurement model
yi = aTi x + vi, i = 1, . . . , m
•x Rn is vector of unknown parameters
•vi is IID measurement noise, with density p(z)
•yi is measurement: y Rm has density px(y) =
maximum likelihood estimate: any solution x of
Qm p(yi − aT x)
i=1 i
maximize l(x) = Pm log p(yi − aT x)
i=1 i
(y is observed value)
Statistical estimation |
7–3 |
examples
• Gaussian noise N (0, σ2): p(z) = (2πσ2)−1/2e−z2/(2σ2),
l(x) = −m2 log(2πσ2) − 2σ12 Xm (aTi x − yi)2
i=1
ML estimate is LS solution
• Laplacian noise: p(z) = (1/(2a))e−|z|/a,
l(x) = −m log(2a) − a1 Xm |aTi x − yi|
i=1
ML estimate is ℓ1-norm solution
• uniform noise on [−a, a]:
l(x) = |
−m log(2a) |
|aiT x − yi| ≤ a, i = 1, . . . , m |
|
−∞ |
otherwise |
ML estimate is any x with |aTi x − yi| ≤ a
Statistical estimation |
7–4 |