A fast dual projected Newton method for l 1 -regularized least squares

Pinghua Gong, Changshui Zhang

Abstract

L1-regularized least squares, with the ability of discovering sparse representations, is quite prevalent in the field of machine learning, statistics and signal processing. In this paper, we propose a novel algorithm called Dual Projected Newton Method (DPNM) to solve the l1-regularized least squares problem. In DPNM, we first derive a new dual problem as a box constrained quadratic programming. Then, a projected Newton method is utilized to solve the dual problem, achieving a quadratic convergence rate. Moreover, we propose to utilize some practical techniques, thus it greatly reduces the computational cost and makes DPNM more efficient. Experimental results on six real-world data sets indicate that DPNM is very efficient for solving the l1-regularized least squares problem, by comparing it with state of the art methods.
BibTeX
@inproceedings{gong2011fast,
  author = {Pinghua Gong and Changshui Zhang},
  title = {{A fast dual projected Newton method for l 1 -regularized least squares}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
}

Loading related content...

Figure