Description

6. Approximation and fitting
• norm approximation
• least-norm problems
• regularized approximation
• robust approximation
Norm approximation minimize kAx − bk
(A ∈ Rm×n with m ≥ n, k · k is a norm on Rm)
interpretations of solution x⋆ = argminx kAx − bk:
• geometric: Ax⋆ is point in R(A) closest to b • estimation: linear measurement model
y = Ax + v
y are measurements, x is unknown, v is measurement error given y = b, best guess of x is x⋆
• optimal design: x are design variables (input), Ax is result (output) x⋆ is design that best approximates desired result b
examples
• least-squares approximation (k · k2): solution satisfies normal equations
ATAx = ATb
(x⋆ = (ATA)−1ATb if rankA = n)
• Chebyshev approximation (k · k∞): can be solved as an LP
minimize t
subject to
• sum of absolute residuals approximation (k·k1): can be solved as an LP
minimize 1Ty
subject to
Penalty function approximation
subject tominimize rφ(=r1Ax) +−···b+ φ(rm)
(A ∈ Rm×n, φ : R → R is a convex penalty function)
examples
• quadratic: φ(u) = u2
• deadzone-linear with width a:
φ(u) = max{0,|u| − a} 0.5
• log-barrier with limit a:
|otherwiseu| < a
example (m = 100, n = 30): histogram of residuals for penalties

shape of penalty function has large effect on distribution of residuals Huber penalty function (with parameter M)

linear growth for large u makes approximation less sensitive to outliers

−1.5 −1 −0.5 0 0.5 1 1.5 −10 −5 0 5 10 u t
• left: Huber penalty for M = 1
• right: affine function f(t) = α + βt fitted to 42 points ti, yi (circles) using quadratic (dashed) and Huber (solid) penalty
Least-norm problems
subject tominimize kxk= b
Ax
(A ∈ Rm×n with m ≤ n, k · k is a norm on Rn)
interpretations of solution x⋆ = argminAx=b kxk:
• geometric:distance to 0x⋆ is point in affine set {x | Ax = b} with minimum
• (estimation:’most plausible’) estimate consistent with measurementsb = Ax are (perfect) measurements of x; x⋆ is smallest
• design: x are design variables (inputs); b are required results (outputs) x⋆ is smallest (’most efficient’) design that satisfies requirements examples
• least-squares solution of linear equations (k · k2): can be solved via optimality conditions
2x + ATν = 0, Ax = b
• minimum sum of absolute values (k · k1): can be solved as an LP
minimize 1Ty
subject to
tends to produce sparse solution x⋆ extension: least-penalty problem
minimize φ(x1) + ··· + φ(xn) subject to Ax = b
φ : R → R is convex penalty function
Regularized approximation
minimize (w.r.t. R
A ∈ Rm×n, norms on Rm and Rn can be different
interpretation: find good approximation Ax ≈ b with small x
• estimation: linear measurement model y = Ax + v, with prior knowledge that kxk is small
• optimal design: small x is cheaper or more efficient, or the linear model y = Ax is only valid for small x
• robust approximation: good approximation Ax ≈ b with small x is less sensitive to errors in A than good approximation with large x
Scalarized problem
minimize kAx − bk + γkxk
• solution for γ > 0 traces out optimal trade-off curve
• other common method: minimize kAx − bk2 + δkxk2 with δ > 0
Tikhonov regularization
minimize kAx − bk22 + δkxk22
can be solved as a least-squares problem
minimize
solution x⋆ = (ATA + δI)−1ATb
Optimal input design
linear dynamical system with impulse response h:

input design problem: multicriterion problem with 3 objectives
1. tracking error with desired output ydes: Jtrack
2. input magnitude:
3. input variation:
track desired output using a small and slowly varying input signal regularized least-squares formulation
minimize Jtrack + δJder + ηJmag
for fixed δ,η, a least-squares problem in u(0), . . . , u(N) example: 3 solutions on optimal trade-off curve
(top) δ = 0, small η; (middle) δ = 0, larger η; (bottom) large δ

t t

t t

t t
Signal reconstruction
minimize (w.r.t. R
• x ∈ Rn is unknown signal
• xcor = x + v is (known) corrupted version of x, with additive noise v
• variable xˆ (reconstructed signal) is estimate of x
• φ : Rn → R is regularization function or smoothing objective examples: quadratic smoothing, total variation smoothing:

quadratic smoothing example
0 1000 2000 3000 4000 1000 2000 3000 4000 i i
original signal x and noisy three solutions on trade-off curve signal xcor kxˆ − xcork2 versus φquad(xˆ)
total variation reconstruction example
−1
0 500 1000 1500 2000 500 1000 1500 2000 i i
original signal x and noisy three solutions on trade-off curve signal xcor kxˆ − xcork2 versus φquad(xˆ)
quadratic smoothing smooths out noise and sharp transitions in signal

original signal x and noisy signal xcor

three solutions on trade-off curve
kxˆ − xcork2 versus φtv(xˆ)

total variation smoothing preserves sharp transitions in signal
Robust approximation
minimize kAx − bk with uncertain A
two approaches:
• stochastic: assume A is random, minimize EkAx − bk
• worst-case: set A of possible values of A, minimize supA∈AkAx − bk tractable only in special cases (certain norms k · k, distributions, sets A)
example: A(u) = A0 + uA1
• xnom minimizes kA0x − bk22
• xwithstochuminimizesuniform onE[k−A1(,u1])x − bk22
• xwc minimizes sup−1≤u≤1 kA(u)x − bk22
figure shows r(u) = kA(u)x − bk2 −0 2 −1 0 1 2
u
stochastic robust LS with A = A¯+U, U random, EU = 0, EUTU = P
minimize Ek(A¯ + U)x − bk22
• explicit expression for objective:
EkAx − bk22 = EkAx¯ − b + Uxk22
= kAx¯ − bk22 + ExTUTUx
= kAx¯ − bk22 + xTPx
• hence, robust LS problem is equivalent to LS problem
minimize kAx¯ − bk22 + kP1/2xk22
• for P = δI, get Tikhonov regularized problem
minimize kAx¯ − bk22 + δkxk22
worst-case robust LS with A = {A¯ + u1A1 + ··· + upAp | kuk2 ≤ 1} minimize supA∈AkAx − bk22 = supkuk2≤1 kP(x)u + q(x)k22 where
• from page 5–14, strong duality holds between the following problems
maximize kPu + qk22 minimize t + λ
subject to kuk22 ≤ 1
subject to
• hence, robust LS problem is equivalent to SDP
minimize t + λ
subject to
example: histogram of residuals
r(u) = k(A0 + u1A1 + u2A2)x − bk2
with u uniformly distributed on unit disk, for three values of x

• xls minimizes kA0x − bk2
• xtik minimizes kA0x − bk22 + kxk22 (Tikhonov solution)
• xwc minimizes supkuk2≤1 kA0x − bk22 + kxk22