5.4.5. L1-ball

For a given scalar \(\xi\ge0\), the L1-ball is a linear constraint defined as

\[ \mathcal{C}_{L_1} = \big\{ {\bf w} \in \mathbb{R}^{N} \;|\; \|{\bf w}\|_1 \le \xi \big\}, \]

where \(\|{\bf w}\|_1 = |w_1|+\dots+|w_N|\) is the L1-norm. The condition \(\xi \ge 0\) is required for this subset to be nonempty. The figure below shows how this constraint looks like in \(\mathbb{R}^{2}\) or in \(\mathbb{R}^{3}\).

L1-ball in 2D

L1-ball in 3D

5.4.5.1. Constrained optimization

Optimizing a function \(J({\bf w})\) subject to the L1-ball constraint can be expressed as

\[ \operatorname*{minimize}_{\textbf{w}\in\mathbb{R}^N}\;\; J({\bf w}) \quad{\rm s.t.}\quad \|{\bf w}\|_1 \le \xi. \]

The figure below visualizes such an optimization problem in \(\mathbb{R}^{2}\).

5.4.5.2. Orthogonal projection

The projection of a point \({\bf u}\in\mathbb{R}^{N}\) onto the L1-ball is the (unique) solution to the following problem

\[ \operatorname*{minimize}_{{\bf w}\in\mathbb{R}^N}\; \|{\bf w}-{\bf u}\|^2 \quad{\rm s.t.}\quad \|{\bf w}\|_1 \le \xi. \]

The solution can be computed as follows.

Projection onto the L1-ball

\[\begin{split} \mathcal{P}_{\mathcal{C}_{L_1}}({\bf u}) = \begin{cases} {\bf u} & \mathrm{if} \; \|{\bf u}\|_1 \le \xi \\ {\rm sign}({\bf u}) \circ \mathcal{P}_{\mathcal{C}_{\rm simplex}}\big({\rm abs}({\bf u})\big) & \mathrm{otherwise} \end{cases} \end{split}\]

Note: \({\rm sign}\), \({\rm abs}\), \(\circ\) are element-wise operations.

The next figure visualizes a point \({\bf u}\in \mathbb{R}^{2}\) (blue dot) along with its projection (red dot) onto this set.

5.4.5.3. Implementation

The python implementation is given below.

def project_l1ball(u, bound):
    
    assert bound >= 0, "The bound must be non-negative"
    
    if np.abs(u).sum() <= bound:
        p = u
    else:
        p = np.sign(u) * project_simplex(np.abs(u), bound)
        
    return p

Here is an example of use.

u = np.array([-1, 1])

p = project_l1ball(u, bound=1)