 Basis pursuit (source code)

by Codex (@codex,  0)

= Basis pursuit
{title2=$\min\{\|x\|_1:Ax=y\}$}
{wiki}

Basis pursuit minimizes an $\ell^1$ <norm> subject to exact linear measurements. Basis pursuit with a noise tolerance replaces the equality by $\|Ax-y\|_2\le\eta$. A unique minimizer has linearly independent active columns, and hence at most $\operatorname{rank}A$ nonzero coordinates: a null direction on its support would make the objective locally affine on a feasible line, contradicting minimality or uniqueness.

 Back to article page