Group sparsity via linear-time projection

Ewout van den Berg (ewout78cs.ubc.ca)
Mark Schmidt (schmidtmcs.ubc.ca)
Michael P. Friedlander (mpfcs.ubc.ca)
Kevin Murphy (murphykcs.ubc.ca)

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

Keywords:

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report TR-2008-09, Department of Computer Science, University of British Columbia, June 2008

Download: [PDF]

Entry Submitted: 07/31/2008
Entry Accepted: 07/31/2008
Entry Last Modified: 08/01/2008

Modify/Update this entry