Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse

The minimum lscr 1 -norm solution to an underdetermined system of linear equations y = Ax is often, remarkably, also the sparsest solution to that system. This sparsity-seeking property is of interest in signal processing and information transmission. However, general-purpose optimizers are much too slow for lscr 1 minimization in many large-scale applications.In this paper, the Homotopy method, originally proposed by Osborne et al. and Efron et al., is applied to the underdetermined lscr 1 -minimization problem min par x par 1 subject to y = Ax . Homotopy is shown to run much more rapidly than general-purpose LP solvers when sufficient sparsity is present. Indeed, the method often has the following k -step…