E. van den Berg and M. P. Friedlander

Tech. Rep. TR-2007-19, Dept of Computer Science, University of British Columbia, June 2007
PDF

A later and more complete version of this paper is available.

## Abstract

The basis pursuit technique is used to find a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise fits the least-squares problem only approximately, and a single parameter determines a curve that traces the trade-off between the least-squares fit and the one-norm of the solution. We show that the function that describes this curve is convex and continuously differentiable over all points of interest. The dual solution of a least-squares problem with an explicit one-norm constraint gives function and derivative information needed for a root-finding method. As a result, we can compute arbitrary points on this curve. Numerical experiments demonstrate that our method, which relies on only matrix-vector operations, scales well to large problems.

## BibTeX

```
@techreport{BergFrie:2007,
Address = {University of British Columbia, Vancouver},
Author = {E. {van den} Berg and M. P. Friedlander},
Institution = {Department of Computer Science},
Month = {June},
Number = {TR-2007-19},
Title = {In pursuit of a root},
Type = {Tech. Rep.},
Url = {http://www.optimization-online.org/DB_HTML/2007/06/1708.html},
Year = 2007
}
```