[BANANA] LA/Opt Seminar on Wednesday (Michael Saunders)

[Michael A. Saunders]

   Linear Algebra and Optimization Seminar (CME510)
   iCME, Stanford University
   http://icme.stanford.edu/seminars/seminars.php

   4:15pm Wed Jan 23, 2008
   Rm 317 Wallenberg Hall (Bldg 160)
   (Same building as last quarter, but different room)

   COMPUTING SPARSE PAGERANK VECTORS BY BASIS PURSUIT

   Michael Saunders
   SOL, Stanford University
   http://www.stanford.edu/~saunders/

Many applications involve linear systems Ax ~= b in which an
approximate solution x is required to be sparse.  Lasso and
Basis Pursuit DeNoising were developed for this purpose.
They balance the 1-norm of x against the size of the
residual, and they allow A to be rectangular.  Related
procedures include LARS, Homotopy, and the Dantzig Selector.

The PageRank eigenvector problem involves a square system
Ax = b in which x is sometimes naturally sparse (depending
on b).  We conduct an empirical study of BPDN in this
context.  We use an active-set method designed for the dual
of the BPDN problem, and find that it tends to extract the
important elements of x in a greedy fashion.  The test
examples come from the Stanford and Berkeley webs.

Acknowledgements to Sou-Cheng Choi, Michael Friedlander,
David Gleich, and Holly Jin.