Group sparsity via linear-time projection

E. van den Berg, M. Schmidt, M. P. Friedlander, K. Murphy
Technical Report TR-2008-09, Department of Computer Science, University of British Columbia, 2008



We present an efficient spectral projected-gradient algorithm for optimization subject to a group l1-norm constraint. Our approach is based on a novel linear-time algorithm for Euclidean projection onto the l1- and group l1-norm constraints. Numerical experiments on large data sets suggest that the proposed method is substantially more efficient and scalable than existing methods.


  author  =  {E. van den Berg and M. Schmidt and M. P. Friedlander and K. Murphy},
  title   =  {Group sparsity via linear-time projection},
  year    = 2008,
  month   = {June},
  note    = {Tech. Rep. TR-2008-09, Dept. of Computer Science, UBC}