norm approximation

Consider an error minimization task \(\min \norm{Ax - b}\) (\(Ax\) as the “predictions”, and \(b\) is the “data”). Some interpretation—

  • approximation: \(Ax^{*}\) is the best approximation of the vector \(b\) by linear combinations of columns of \(A\)
  • geometric: \(Ax^{*}\) is a point in \(\mathcal{R}\qty(A)\) closest to \(b\)
  • estimation: linear measurement model \(y = Ax + v\)
    • you took a measurement \(y\), \(A\) is the theoretical measurement, \(v\) is the measurement error
    • implausibility of making \(v\) error is \(\norm{v}\)
    • given \(y = b\) (what you measured), most plausible \(x\) is \(x^{*}\)
  • optimal design: \(x\) are design variables, \(Ax\) is the result; \(x^{*}\) is the design that best approximates desired \(b\)

Penalty Function Approximation

Suppose you are optimizing some design \(x\) with respect to some dynamics \(A\). Suppose your design residual is \(r = Ax - b\). And you have some kind of penalty function to describe how comfortable you are with various errors: \(\phi\qty(r_1) + … + \phi\qty(r_{n})\).

\begin{align} \min_{x}\quad & \phi\qty(r_{1}) + \dots + \phi\qty(r_{n}) \\ \textrm{s.t.} \quad & r = Ax - b \end{align}

Huber Penalty Function

A quadratic at a small residuals (chiller about small residuals), and a linear to large functions.

\begin{equation} \theta_{\text{hub}}\qty(u) = \begin{cases} u^{2}, | u | \leq M\\ M\qty(2 |u| - M), |u| > M \end{cases} \end{equation}

  • “robust penalty”

Least Norm Problem

\begin{align} \min_{x}\quad & \norm{x} \\ \textrm{s.t.} \quad & Ax = b \end{align}

  • geometric: \(x^{*}\) is the smallest point in the solution set
  • estimation: \(b = Ax\) are perfect measurements of \(x\), and we want the most plausible \(x\), calling \(\norm{x}\) the impossibility of \(x\)
  • design: \(x\) are design variables and \(b\) are required results

Robust Approximation

Minimize \(\norm{Ax - b}\) with uncertain \(A\); two approaches—

  1. stochastic: minimize \(\mathbb{E}\norm{Ax -b }\)
  2. worst-case: set \(\mathcal{A}\) of possible values of \(A\), minimize \(\text{sup}_{A \in A} \norm{Ax - b}\)