Convex Optimization Chapter 6

Study Notes

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 ).

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 ).

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

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.

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

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.