The Lawson-Hanson Algorithm with Deviation Maximization: Finite Convergence and Sparse Recovery

In this work we devise a new version of the Lawson-Hanson with Devia- tion Maximization (LHDM) algorithm, a block method for the solution of NonNegative Least Squares (NNLS). It is shown that the new algorithm here presented convergences in a finite number of steps under suitable conditions. An extensive campaign of experiments is performed in order to evaluate the performance gain with respect to the standard Lawson-Hanson algorithm. We also explore the sparse recovery ability of LHDM, comparing it against several l1-minimization solvers in terms of solution quality and time-to-solution on a large set of dense instances.