L1minimization

L1 minimization is a class of optimization problems that seek the vector x with minimum L1 norm, subject to linear constraints. Formally, given A in R^{m×n} and b in R^m, it asks to minimize ||x||_1 = sum_i |x_i| subject to Ax = b (or Ax ≈ b in the presence of noise). The L1 norm promotes sparsity in the solution.

Because the L1 norm is convex, L1 minimization provides a tractable convex relaxation of the combinatorial L0 minimization that seeks the sparsest x with Ax = b. In noisy settings, Basis Pursuit Denoising minimizes ||x||_1 subject to ||Ax − b||_2 ≤ ε; LASSO uses a similar objective with a penalty on ||x||_1 adding to the data fidelity term. L1 minimization is central in compressed sensing for recovering sparse signals from undersampled measurements.

Recovery of a k-sparse x0 from b = Ax0 via L1 minimization holds under certain conditions on A. Classical guarantees involve the null space property or the restricted isometry property (RIP). If A preserves the geometry of sparse vectors, the L1 solution matches x0 exactly (exact recovery) or approximately in the presence of noise.

Practically, L1 minimization is solved as a linear program or via iterative methods such as ISTA/FISTA (which use soft-thresholding), ADMM, or interior-point methods, enabling efficient handling of large-scale problems. Variants include reweighted L1 to better approximate L0, and extensions to group sparsity with mixed L1 norms.

Applications span compressed sensing, magnetic resonance imaging, image and audio reconstruction, sparse regression, and machine learning feature selection, where the underlying signal or model is believed to be sparse in some basis.