Sparse optimization seeks solutions with few nonzero coordinates, either as an explicit objective or through a penalty. Minimizing the number of nonzero entries, written , is combinatorial; replacing it by the L1 norm often gives a tractable convex optimization problem.
For example, basis pursuit minimizes subject to , while Lasso minimizes a squared residual plus . The penalty favors exact zero coordinates because it has a corner at zero. Recovery of the sparsest explanation needs assumptions on ; an L1 norm objective alone does not establish it. These methods connect variable selection with compressed sensing.
New to topics? Read the docs here!