Projection onto $\ell^{2,1}$ ball

Question

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve $$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 \right)^{1/2} \leq 1$$ for a matrix $u \in \mathbb{R}^{n \times m}$ efficiently?

Answer 1

Since the projection on to the $\ell_{1,2}$ ball doesn't have a simple solution, I would be surprised if there is one for the $\ell_{2,1}$ ball. The difficulty is that this case involves the squared $\ell_1$ norm rather than the simple $\ell_2$ norm. Maybe the following can be helpful if you would like to avoid splitting the problem.

First, note that your constraint can be equivalently expressed as $$ \|u\|_{2,1}^2 = \sum_i \|u_{i}\|_1^2 \leq 1,$$ where $u_i$ is the $i$th row of $u$. Introducing a Lagrange multiplier $\lambda\geq 0$, the metric projection problem can be formulated as $$\min_{u}\sup_\lambda \frac12\|u-f\|_{2,2}^2 + \lambda (\|u\|_{2,1}^2 -1).$$ Assume now that $\|f\|_{2,1}>1$ (otherwise we would have $u=f$), hence we can assume that for the minimizers $\|u\|_{2,1} = 1$ (the necessary optimality with respect to $\lambda$) and $\lambda >0$ holds (needs to be shown using a proof by contradiction, see below). For optimality with respect to $u$, first note that the reformulated minimization problem completely decouples for the $u_i$. Hence, for every $i$, we have the optimality condition $$0\in \partial\left(\frac12\|u_i-f_i\|_2^2 + \lambda \|u_i\|_1^2\right).$$ Applying a sum rule ($0$ is a regular point), this is equivalent with $$\frac1\lambda (f_i -u_i) \in \partial(\|\cdot\|_1^2)(u_i) = 2 \|u_i\|_1 \partial(\|\cdot\|_1)(u_i)$$ (using the fact that the subdifferential of one-half of the squared norm is the duality mapping, see Schirotzek, Nonsmooth Analysis, Remark 4.6.3). If $f_i\neq 0$, then $\|u_i\|_1\neq 0$ (otherwise we obtain a contradiction). Now we use the equivalence for every $\gamma>0$ $$-p\in\partial F(u) \Leftrightarrow u = \mathrm{prox}_{\gamma F}(u-\gamma p),$$ where the proximal mapping for the $1$-norm is the soft-thresholding operator $$\mathrm{prox}_{\gamma\|\cdot\|_1}(w) = S_\gamma(w) = (|w|-\gamma)^+\mathrm{sign}(w)$$ with $(w)^+ = \max\{0,w\}$ (all of which is to be understood componentwise if $w$ is a vector). Setting $\gamma = 2\lambda \|u_i\|_1$, we thus obtain the relations $$ \begin{aligned} &u_i = (|f_i|-2\lambda \|u_i\|_1)^+\mathrm{sign}(f_i) \qquad \text{for all }i,\\ &\sum_i \|u_i\|_1^2 = 1. \end{aligned} $$ (Here you get the desired contradiction: if $\lambda =0$, then $u_i = f_i$, which violates the second condition.)

Inserting the first relations into the second, you can solve for given $u_i$ for $\lambda$ via root finding, and for given $\lambda$, you can apply a fixed point iteration to (hopefully) compute $u_i$.