---
title: "A Fast Dual Projected Newton Method for l1-Regularized Least Squares"
authors:
  - "Pinghua Gong"
  - "Changshui Zhang"
doi: "10.5591/978-1-57735-516-8/IJCAI11-216"
url: "https://ijcai.org/proceedings/2011/216"
pdf: "https://ijcai.org/proceedings/2011/0216.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1275-1279"
track: ""
keywords:
---

# A Fast Dual Projected Newton Method for l1-Regularized Least Squares

Pinghua Gong, Changshui Zhang

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1275-1279. DOI: [10.5591/978-1-57735-516-8/IJCAI11-216](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-216)

## 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.