Norm Approximation & Regularization

Least squares is one choice of norm among several, and the choice decides who wins: the cluster or the outlier.

The idea

Definition (Norm approximation problem).

Given data $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$ and a norm $\|\cdot\|$ on $\mathbb{R}^{m}$, the norm approximation problem is to minimize $\|Ax - b\|$ over $x \in \mathbb{R}^{n}$: to make the residual $r = Ax - b$ as small as possible, measured in that norm.

The three standard choices are $\|r\|_{2} = \sqrt{\sum_{i} r_{i}^{2}}$, $\|r\|_{1} = \sum_{i} |r_{i}|$ and $\|r\|_{\infty} = \max_{i} |r_{i}|$.

Least Squares is the case of $\|r\|_{2}$; nothing about approximating $b$ by $Ax$ forces that choice. The problem is convex in every norm, since norms are convex functions and composing with an affine map preserves convexity.

The choice of norm is a modelling decision about which errors matter. Squaring in $\|r\|_{2}$ makes one large residual cost far more than several small ones, so a single wild measurement pulls the fit a long way toward itself. The sum of absolute values $\|r\|_{1}$ charges every unit of error the same. The maximum $\|r\|_{\infty}$ counts only the worst residual. On the same data the three give genuinely different answers; the unit balls in the figure record the difference — a diamond for $\ell_{1}$, a disc for $\ell_{2}$, a square for $\ell_{\infty}$.

Regularization is a second modelling decision: add a penalty on the size of $x$ and minimize $\|Ax - b\| + \gamma\|x\|$. Raising $\gamma$ trades a larger residual for a smaller solution, and the penalty norm matters as well — an $\ell_{1}$ penalty drives coordinates of $x$ to exactly zero, while an $\ell_{2}$ penalty only shrinks them.

Ways to work on it

• Walkthrough. Fit the same data under different norms and see how the choice of norm shapes the solution.
• Proof. Why _1 regularization produces coordinates that are exactly zero and _2 does not.
• Practice. Fit small examples under different norms and regularization penalties.
• Hardest. Find the exact regularization strength at which a fitted coefficient becomes zero.

Not sure where to start? Take the ten-question placement test.