= Sparse optimization
{wiki}
<Sparse optimization> seeks solutions with few nonzero coordinates, either as an explicit objective or through a penalty. Minimizing the number of nonzero entries, written $\|x\|_0$, is combinatorial; replacing it by the <L1 norm> often gives a tractable <convex optimization> problem.
For example, <basis pursuit> minimizes $\|x\|_1$ subject to $Ax=b$, while <Lasso> minimizes a squared residual plus $\lambda\|x\|_1$. The penalty favors exact zero coordinates because it has a corner at zero. Recovery of the sparsest explanation needs assumptions on $A$; an <L1 norm> objective alone does not establish it. These methods connect <variable selection> with <compressed sensing>.
Back to article page