# In pursuit of a root

Title | In pursuit of a root |

Publication Type | Report |

Year of Publication | 2007 |

Authors | Ewout van den Berg, Michael P. Friedlander |

Document Number | TR-EOAS-2007-19 |

Month | 06 |

Institution | Department of Computer Science |

City | University of British Columbia, Vancouver |

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

URL | http://www.optimization-online.org/DB_HTML/2007/06/1708.html |

Citation Key | vandenberg07TRipr |