introducing new variables

Consider the original problem:

\begin{align} \min_{x}\quad & \norm{Ax - b} \end{align}

Now, we can reformulate and write \(y = Ax - b\). Now, remember the conjugate of the norm is:

\begin{equation} \norm{z} = \begin{cases} 0, \norm{z} \leq 1\\ \infty \end{cases} \end{equation}

And remember the dual is some massaging of the conjugate. And thus we can formulate a “norm conjugate”:

\begin{align} \max_{v}\quad & b^{T}v \\ \textrm{s.t.} \quad & A^{T}v = 0 \\ & \norm{v} \leq 1 \end{align}