2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – lodhb
    Apr 15, 2013 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Ross B.
    Apr 15, 2013 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .