球的投影没有封闭形式的表达式；它也不是一个组件操作。原则上，对于上的投影由 其中是软阈值（或软收缩）算子，对于是由 和$\ell^1$$\alpha B_{\ell^1}$$\alpha>0$

$$\Pi(x) = \begin{cases} x & \|x\|_1 \leq \alpha \\ S_{\lambda(x)}(x) & \|x\|_1>\alpha\end{cases}$$ $S_\lambda$$\lambda>0$ $$[S_\lambda(x)]_i = \begin{cases} x_i-\lambda & x_i\geq \lambda\\ 0 & |x_i| \leq \lambda \\ x_i+\lambda & x_i\leq -\lambda \end{cases}$$ $\lambda(x)>0$必须选择使得或者，等效地， 这是一个标量（但不可微）求根问题，可以使用二分法解决，该算法在 Maziar Sanjabi 的答案中的链接中给出（这是一种基于对向量的分量进行分区的有效实现）或半光滑牛顿法方法（或其任何组合）。$\|S_{\lambda(x)}x\|_1=\alpha$ $$\sum_i \max\{|x_i|-\lambda(x),0\} = \alpha.$$ $x$

所以你想解决

$$\min_{\|p\|_1 \leq 1} f(q).$$ 与。如果是对称正半定的，这是一个具有凸约束的平滑凸目标，因此，这可以通过迭代 的投影梯度来完成 其中上的正交投影。这个预测可以很快计算出来，并且基本上每年都会重新发现这个算法。Maziar Sanjabi 已经给出了一个很好的来源的链接。是步长，您可以使用t_n$f(p)=(p-q)^TA(p-q)$$A$ $$p^{n+1} = P(p^n - t_n 2A(p^n-q))$$ $P$$\{\|p\|_1\leq 1\}$$t_n$$t_n = 1/(2\|A\|)$（如果我没有记错的话）。如果这很慢，那么廉价的加速就是加速投影梯度下降（又名 FISTA 或 Nesterov 的加速梯度法）。

您可以使用以下论文中的算法将梯度更新投影到 l1 范数球： https ://stanford.edu/~jduchi/projects/DuchiShSiCh08.pdf