Computing a Sparse Projection into a Box

Abstract

We describe a procedure to compute a projection of $w\in {\mathbb{R}}^n$ into the intersection of the so-called \emph{zero-norm} ball $k{\mathbb{B}}_0$ of radius $k$, i.e., the set of $k$-sparse vectors, with a box centered at a point of $k{\mathbb{B}}_0$. The need for such projection arises in the context of certain trust-region methods for nonsmooth regularized optimization. Although the set into which we wish to project is nonconvex, we show that a solution may be found in $O(n\log (n))$ operations. We describe our Julia implementation and illustrate our procedure in the context of two trust-region methods for nonsmooth regularized optimization.

12 pages, 5 figures