Convex Optimization Chapter 6

Approximation and Fitting

• Norm approximation aims to minimize the difference between a linear transformation of a variable and a target vector, represented as ( \min kAx - bk ).
• Solution interpretation for ( x^* = \arg\min_x kAx - bk ):
  • Geometric: ( Ax^* ) is the point in the range of ( A ) closest to ( b ).
  • Estimation: In a linear measurement model ( y = Ax + v ), ( y ) represents observed measurements with ( v ) as measurement error; ( x^* ) provides the best estimate of ( x ).
  • Optimal Design: Design variables ( x ) yield outputs ( Ax ); ( x^* ) represents the best design to approximate the desired output ( b ).

Examples of Norm Approximation

• Least-Squares Approximation ( (k · k_2) ):

  • Satisfies normal equations ( A^T A x = A^T b ).
  • If ( A ) has full rank ( n ), solution is ( x^* = (A^T A)^{-1} A^T b ).

• Chebyshev Approximation ( (k · k_\infty) ):

  • Solved through linear programming to minimize ( t ) subject to ( -t \leq Ax - b \leq t ).

• Sum of Absolute Residuals Approximation ( (k · k_1) ):

  • Also solvable via linear programming, minimizing ( 1^T y ) with constraints ( -y \leq Ax - b \leq y ).

Penalty Function Approximation

• Formulated as ( \min \phi(r_1) + · · · + \phi(r_m) ) with ( r = Ax - b ), where ( \phi ) is a convex penalty function.

Types of Penalty Functions

• Quadratic Penalty: ( \phi(u) = u^2 )
• Deadzone-Linear Penalty: ( \phi(u) = \max{0, |u| - a} ) creates a linear growth after a certain threshold.
• Log-Barrier Penalty: ( \phi(u) = -a^2 \log(1 - (u/a)^2) ) is applicable within limits and infinite otherwise.

Characteristics of Penalty Functions

• The shape of the penalty function significantly influences the distribution of residuals encountered in approximations.

Huber Penalty Function

• Defined with parameter ( M ):
  • ( \phi_{hub}(u) = \begin{cases} u^2 & |u| \leq M \ M(2|u| - M) & |u| > M \end{cases} )
• Offers linear growth for large ( |u| ), making the approximation robust to outliers compared to simple quadratic penalties.