# On norm selection for the solution of an overdetermined linear system

I am considering the following linear system:

$Ax = b$

Where:

• $A$ is $9000 \times 139$
• $x$ is $139 \times 1$ and sparse
• $b$ is $9000 \times 1$

Most of the resources I have found online point to using a least squares method, whereby we look for the (set of) optimum vector(s) $x^*$ minimizing the L2 norm of the error vector $Ax-b$. Formally, this translates into the following optimization problem:

$x^* \in \displaystyle\arg \min_{x} ||Ax-b||_2$

My question is: is this the best way to solve my problem? Why is the least squares method with its L2-norm so popular? Might other norms than the L2-norm be considered?

$L_2$-minimization has some nice mathematical properties, as its square is differentiable and it has links to minimizing expected value. $L_1$-optimization has connections with robust estimation. However, if in your case you want a sparse solution, $L_1$-regularization of $x$ could give you a sparse $x^*$ -- i.e. minimize $||Ax-b||_2 - \gamma||x||_1$. See Chapter 6 of Boyd & Vandenberge for more information (http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf).
• Great answer, thanks! Is there any reason why we might want to choose a norm other than L1,L2 or L∞? For example: the "best" norm $p$ (possibly $> 2$) for the given problem, obtained e.g. via the condition number of A? Apr 15, 2013 at 21:14
• I have not run into any applications myself, but here is an interesting related discussion: mathoverflow.net/questions/28147/…. In particuar, some stochastic optimization concerning the $p$th moment of a random variable could be applicable. Apr 15, 2013 at 22:39