Convex Optimization — Boyd & Vandenberghe 6. Approximation and fitting • norm approximation • least-norm problems • regularized approximation • robust approximation 6–1Norm approximation minimize �Ax − b� (A ∈ Rm×n with m ≥ n, � · � is a norm on Rm) ⋆interpretations of solution x = argminx �Ax − b�: 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 Approximation and fitting 6–2examples • least-squares approximation (� · �2): solution satisfies normal equations ATAx = ATb (x ⋆ = (ATA)−1ATb if rank A = n) • Chebyshev approximation (� · �∞): can be solved as an LP minimize t subject to −t1 � Ax − b � t1 • sum of absolute residuals approximation (�·�1): can be solved as an LP minimize 1Ty subject to −y � Ax − b � y Approximation and fitting 6–3� Penalty function approximation minimize φ(r1) + + φ(rm)··· subject to r = Ax − b (A ∈ Rm×n , φ : R R is a convex penalty function) →examples 2 • quadratic: φ(u) = u deadzone-linear quadratic log barrier −1.5 −1 −0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 deadzone-linear with width a:• φ(u) = max{0, |u| − a} φ(u) • log-barrier with limit a: u φ(u) = −a2 log(1 − (u/a)2) |u| < a ∞ otherwise Approximation and fitting 6–4example (m = 100, n = 30): histogram of residuals for penalties φ(u) = |u|, φ(u) = u 2 , φ(u) = max{0, |u|−a}, φ(u) = −log (1−u 2) 40 0 Deadzone p = 2 p = 1 −2 −10 1 2 10 0 −2 −10 1 2 20 0 −2 −10 1 2 Log barrier 0 10 −2 −10 1 2 r shape of penalty function has large effect on distribution of residuals Approximation and fitting 6–5repla ements� c Huber penalty function (with parameter M) u uφhub(u) = 2 | | ≤ M M(2|u| − M) |u| > M linear growth for large u makes approximation less sensitive to outliers −1.5 −1 −0.5 0 0.5 1 1.5 0 0.5 1 1.5 2 f(t) 20 10 0 φhub(u) −10 −20 −10 −5 0 5 10 u t • left: Huber penalty for M = 1 • right: affi ne function f(t) = α + βt fitted to 42 points ti, yi (circles) using quadratic (dashed) and Huber (solid) penalty Approximation and fitting 6–6Least-norm problems minimize �x�subject to Ax = b (A ∈ Rm×n with m ≤ n, � · � is a norm on Rn) ⋆interpretations of solution x = argminAx=b �x�: ⋆geometric: x is point in affine set {x Ax = b} with minimum • distance to 0 |⋆ • estimation: b = Ax are (perfect) measurements of x; x is smallest (’most plausible’) estimate consistent with measurements • design: x are design variables (inputs); b are required results (outputs) ⋆ x is smallest (’most efficient’) design that satisfies requirements Approximation and fitting 6–7examples • least-squares solution of linear equations (� · �2): can be solved via optimality conditions 2x + ATν = 0, Ax = b • minimum sum of absolute values (� · �1): can be solved as an LP minimize 1Ty subject to −y � x � y, Ax = b ⋆tends to produce sparse solution x extension: least-penalty problem minimize φ(x1) + + φ(xn)··· subject to Ax = b φ : R R is convex penalty function →Approximation and fitting 6–8Regularized approximation minimize (w.r.t. R2 ) (�Ax − b�, �x�)+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 �x� 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 Approximation and fitting 6–9� � � � � �� � � Scalarized problem minimize �Ax − b� + γ�x� • solution for γ > 0 traces out optimal trade-off curve other common method: minimize �Ax − b�2 + δ�x�2 with δ > 0• Tikhonov regularization minimize �Ax − b�can be solved as a least-squares problem 22 2δ+ � �x2 2 � A b � minimize � √δI x − 0 2 solution x ⋆ = (ATA + δI)−1ATb Approximation and fitting 6–10� Optimal input design linear dynamical system with impulse response h: t y(t) = h(τ)u(t − τ), t = 0, 1, . . . , N τ=0 input design problem: multicriterion problem with 3 objectives 1. tracking error with desired output ydes: Jtrack = �N (y(t) − ydes(t))2 t=0�N2. input magnitude: Jmag = t=0 u(t)2 3. input variation: Jder = �N−1(u(t + 1) − u(t))2 t=0 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) Approximation and fitting 6–110 5 0 example: 3 solutions on optimal trade-off curve u(t) (top) δ = 0, small η; (middle) δ = 0, larger η; (bottom) large δ 1 0.5 y(t) 0 −5 −0.5 −1−10 0 50 100 150 200 0 50 100 150 200 tt 4 1 2 0.5 y(t) u(t) 0 −0.5−2 −1−4 0 50 100 150 200 0 50 100 150 200 y(t) tt 4 1 2 0.5 −0.5−2 −1 −4 0 50 100 150 200 0 50 100 150 200 tt Approximation and fitting 6–12 u(t) 0 0� � Signal reconstruction minimize (w.r.t. R2 xcor�2, φ(ˆx)) +) (�xˆ −• 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: n−1 n−1 φquad(ˆx) = (ˆxi+1 − xˆi)2 , φtv(ˆx) = |xˆi+1 − xˆi|i=1 i=1 Approximation and fitting 6–130 0.5