# sporco.prox¶

Norms and their associated proximal maps and projections

The $$p$$-norm of a vector is defined as

$\| \mathbf{x} \|_p = \left( \sum_i | x_i |^p \right)^{1/p}$

where $$x_i$$ is element $$i$$ of vector $$\mathbf{x}$$. The max norm is a special case

$\| \mathbf{x} \|_{\infty} = \max_i | x_i | \;\;.$

The mixed matrix norm $$\|X\|_{p,q}$$ is defined here as [23]

$\|X\|_{p,q} = \left( \sum_i \left( \sum_j |X_{i,j}|^p \right)^{q/p} \right)^{1/q} = \left( \sum_i \| \mathbf{x}_i \|_p^q \right)^{1/q}$

where $$\mathbf{x}_i$$ is row $$i$$ of matrix $$X$$. Note that some authors (e.g., see [30]) use a notation that reverses the positions of $$p$$ and $$q$$.

The proximal operator of function $$f$$ with parameter $$\alpha$$ is defined as

$\mathrm{prox}_{\alpha f}(\mathbf{v}) = \mathrm{argmin}_{\mathbf{x}} \left\{ (1/2) \| \mathbf{x} - \mathbf{v} \|_2^2 + \alpha f(\mathbf{x}) \right\} \;\;.$

The projection operator of function $$f$$ is defined as

$\begin{split}\mathrm{proj}_{f,\gamma}(\mathbf{v}) &= \mathrm{argmin}_{\mathbf{x}} (1/2) \| \mathbf{x} - \mathbf{v} \|_2^2 \; \text{ s.t. } \; f(\mathbf{x}) \leq \gamma \\ &= \mathrm{prox}_g(\mathbf{v})\end{split}$

where $$g(\mathbf{v}) = \iota_C(\mathbf{v})$$, with $$\iota_C$$ denoting the indicator function of set $$C = \{ \mathbf{x} \; | \; f(\mathbf{x}) \leq \gamma \}$$.

Functions

 ndto2d(x[, axis]) Convert a multi-dimensional array into a 2d array, with the axes specified by the axis parameter flattened into an index along rows, and the remaining axes flattened into an index along the columns. ndfrom2d(xtr, rsi) Undo the array shape conversion applied by ndto2d, returning the input 2D array to its original shape. norm_l0(x[, axis, eps]) Compute the $$\ell_0$$ “norm” (it is not really a norm) prox_l0(v, alpha) Compute the proximal operator of the $$\ell_0$$ “norm” (hard thresholding) norm_l1(x[, axis]) Compute the $$\ell_1$$ norm prox_l1(v, alpha) Compute the proximal operator of the $$\ell_1$$ norm (scalar shrinkage/soft thresholding) proj_l1(v, gamma[, axis, method]) Projection operator of the $$\ell_1$$ norm. norm_2l2(x[, axis]) Compute the squared $$\ell_2$$ norm norm_l2(x[, axis]) Compute the $$\ell_2$$ norm norm_l21(x[, axis]) Compute the $$\ell_{2,1}$$ mixed norm prox_l2(v, alpha[, axis]) Compute the proximal operator of the $$\ell_2$$ norm (vector shrinkage/soft thresholding) proj_l2(v, gamma[, axis]) Compute the projection operator of the $$\ell_2$$ norm. prox_sl1l2(v, alpha, beta[, axis]) Compute the proximal operator of the sum of $$\ell_1$$ and $$\ell_2$$ norms (compound shrinkage/soft thresholding) [44] [10] norm_nuclear(X) Compute the nuclear norm prox_nuclear(V, alpha) Proximal operator of the nuclear norm [7] with parameter $$\alpha$$.

## Function Descriptions¶

sporco.prox.ndto2d(x, axis=-1)[source]

Convert a multi-dimensional array into a 2d array, with the axes specified by the axis parameter flattened into an index along rows, and the remaining axes flattened into an index along the columns. This operation can not be properly achieved by a simple reshape operation since a reshape would shuffle element order if the axes to be grouped together were not consecutive: this is avoided by first permuting the axes so that the grouped axes are consecutive.

Parameters: x : array_like Multi-dimensional input array axis : int or tuple of ints, optional (default -1) Axes of x to be grouped together to form the rows of the output 2d array. xtr : ndarray 2D output array rsi : tuple A tuple containing the details of transformation applied in the conversion to 2D
sporco.prox.ndfrom2d(xtr, rsi)[source]

Undo the array shape conversion applied by ndto2d, returning the input 2D array to its original shape.

Parameters: xtr : array_like Two-dimensional input array rsi : tuple A tuple containing the shape of the axis-permuted array and the permutation order applied in ndto2d. x : ndarray Multi-dimensional output array
sporco.prox.norm_l0(x, axis=None, eps=0.0)[source]

Compute the $$\ell_0$$ “norm” (it is not really a norm)

$\begin{split}\| \mathbf{x} \|_0 = \sum_i \left\{ \begin{array}{ccc} 0 & \text{if} & x_i = 0 \\ 1 &\text{if} & x_i \neq 0 \end{array} \right.\end{split}$

where $$x_i$$ is element $$i$$ of vector $$\mathbf{x}$$.

Parameters: x : array_like Input array $$\mathbf{x}$$ axis : None or int or tuple of ints, optional (default None) Axes of x over which to compute the $$\ell_0$$ “norm”. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct values are computed over the indices of the remaining axes of input array x. eps : float, optional (default 0.0) Absolute value threshold below which a number is considered to be zero. nl0 : float or ndarray Norm of x, or array of norms treating specified axes of x as a vector
sporco.prox.prox_l0(v, alpha)[source]

Compute the proximal operator of the $$\ell_0$$ “norm” (hard thresholding)

$\begin{split}\mathrm{prox}_{\alpha f}(v) = \mathcal{S}_{0,\alpha}(\mathbf{v}) = \left\{ \begin{array}{ccc} 0 & \text{if} & | v | < \sqrt{2 \alpha} \\ v &\text{if} & | v | \geq \sqrt{2 \alpha} \end{array} \right. \;,\end{split}$

where $$f(\mathbf{x}) = \|\mathbf{x}\|_0$$. The approach taken here is to start with the definition of the $$\ell_0$$ “norm” and derive the corresponding proximal operator. Note, however, that some authors (e.g. see Sec. 2.3 of [24]) start by defining the hard thresholding rule and then derive the corresponding penalty function, which leads to a simpler form for the thresholding rule and a more complicated form for the penalty function.

Unlike the corresponding norm_l0, there is no need for an axis parameter since the proximal operator of the $$\ell_0$$ norm is the same when taken independently over each element, or over their sum.

Parameters: v : array_like Input array $$\mathbf{v}$$ alpha : float or array_like Parameter $$\alpha$$ x : ndarray Output array
sporco.prox.norm_l1(x, axis=None)[source]

Compute the $$\ell_1$$ norm

$\| \mathbf{x} \|_1 = \sum_i | x_i |$

where $$x_i$$ is element $$i$$ of vector $$\mathbf{x}$$.

Parameters: x : array_like Input array $$\mathbf{x}$$ axis : None or int or tuple of ints, optional (default None) Axes of x over which to compute the $$\ell_1$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct values are computed over the indices of the remaining axes of input array x. nl1 : float or ndarray Norm of x, or array of norms treating specified axes of x as a vector
sporco.prox.prox_l1(v, alpha)[source]

Compute the proximal operator of the $$\ell_1$$ norm (scalar shrinkage/soft thresholding)

$\mathrm{prox}_{\alpha f}(\mathbf{v}) = \mathcal{S}_{1,\alpha}(\mathbf{v}) = \mathrm{sign}(\mathbf{v}) \odot \max(0, |\mathbf{v}| - \alpha)$

where $$f(\mathbf{x}) = \|\mathbf{x}\|_1$$.

Unlike the corresponding norm_l1, there is no need for an axis parameter since the proximal operator of the $$\ell_1$$ norm is the same when taken independently over each element, or over their sum.

Parameters: v : array_like Input array $$\mathbf{v}$$ alpha : float or array_like Parameter $$\alpha$$ x : ndarray Output array
sporco.prox.proj_l1(v, gamma, axis=None, method=None)[source]

Projection operator of the $$\ell_1$$ norm.

Parameters: v : array_like Input array $$\mathbf{v}$$ gamma : float Parameter $$\gamma$$ axis : None or int or tuple of ints, optional (default None) Axes of v over which to compute the $$\ell_1$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct norm values are computed over the indices of the remaining axes of input array v. method : None or str, optional (default None) Solver method to use. If None, the most appropriate choice is made based on the axis parameter. Valid methods are ‘scalarroot’ The solution is computed via the method of Sec. 6.5.2 in [27]. ‘sortcumsum’ The solution is computed via the method of [12]. x : ndarray Output array
sporco.prox.norm_2l2(x, axis=None)[source]

Compute the squared $$\ell_2$$ norm

$\| \mathbf{x} \|_2^2 = \sum_i x_i^2$

where $$x_i$$ is element $$i$$ of vector $$\mathbf{x}$$.

Parameters: x : array_like Input array $$\mathbf{x}$$ axis : None or int or tuple of ints, optional (default None) Axes of x over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct values are computed over the indices of the remaining axes of input array x. nl2 : float or ndarray Norm of x, or array of norms treating specified axes of x as a vector
sporco.prox.norm_l2(x, axis=None)[source]

Compute the $$\ell_2$$ norm

$\| \mathbf{x} \|_2 = \sqrt{ \sum_i x_i^2 }$

where $$x_i$$ is element $$i$$ of vector $$\mathbf{x}$$.

Parameters: x : array_like Input array $$\mathbf{x}$$ axis : None or int or tuple of ints, optional (default None) Axes of x over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct values are computed over the indices of the remaining axes of input array x. nl2 : float or ndarray Norm of x, or array of norms treating specified axes of x as a vector.
sporco.prox.norm_l21(x, axis=-1)[source]

Compute the $$\ell_{2,1}$$ mixed norm

$\| X \|_{2,1} = \sum_i \sqrt{ \sum_j X_{i,j}^2 }$

where $$X_{i,j}$$ is element $$i,j$$ of matrix $$X$$.

Parameters: x : array_like Input array $$X$$ axis : None or int or tuple of ints, optional (default -1) Axes of x over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector, in which case the result is just the $$\ell_2$$ norm. If axes are specified, then the sum over the $$\ell_2$$ norm values is computed over the indices of the remaining axes of input array x. nl21 : float Norm of $$X$$
sporco.prox.prox_l2(v, alpha, axis=None)[source]

Compute the proximal operator of the $$\ell_2$$ norm (vector shrinkage/soft thresholding)

$\mathrm{prox}_{\alpha f}(\mathbf{v}) = \mathcal{S}_{2,\alpha} (\mathbf{v}) = \frac{\mathbf{v}} {\|\mathbf{v}\|_2} \max(0, \|\mathbf{v}\|_2 - \alpha) \;,$

where $$f(\mathbf{x}) = \|\mathbf{x}\|_2$$.

Parameters: v : array_like Input array $$\mathbf{v}$$ alpha : float or array_like Parameter $$\alpha$$ axis : None or int or tuple of ints, optional (default None) Axes of v over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct norm values are computed over the indices of the remaining axes of input array v, which is equivalent to the proximal operator of the sum over these values (i.e. an $$\ell_{2,1}$$ norm). x : ndarray Output array
sporco.prox.proj_l2(v, gamma, axis=None)[source]

Compute the projection operator of the $$\ell_2$$ norm.

The projection operator of the uncentered $$\ell_2$$ norm,

$\mathrm{argmin}_{\mathbf{x}} (1/2) \| \mathbf{x} - \mathbf{v} \|_2^2 \; \text{ s.t. } \; \| \mathbf{x} - \mathbf{s} \|_2 \leq \gamma$

can be computed as $$\mathbf{s} + \mathrm{proj}_{f,\gamma} (\mathbf{v} - \mathbf{s})$$ where $$f(\mathbf{x}) = \| \mathbf{x} \|_2$$.

Parameters: v : array_like Input array $$\mathbf{v}$$ gamma : float Parameter $$\gamma$$ axis : None or int or tuple of ints, optional (default None) Axes of v over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct norm values are computed over the indices of the remaining axes of input array v. x : ndarray Output array
sporco.prox.prox_sl1l2(v, alpha, beta, axis=None)[source]

Compute the proximal operator of the sum of $$\ell_1$$ and $$\ell_2$$ norms (compound shrinkage/soft thresholding) [44] [10]

$\mathrm{prox}_{f}(\mathbf{v}) = \mathcal{S}_{1,2,\alpha,\beta}(\mathbf{v}) = \mathcal{S}_{2,\beta}(\mathcal{S}_{1,\alpha}(\mathbf{v}))$

where $$f(\mathbf{x}) = \alpha \|\mathbf{x}\|_1 + \beta \|\mathbf{x}\|_2$$, with $$\alpha \geq 0$$, $$\beta \geq 0$$.

Parameters: v : array_like Input array $$\mathbf{v}$$ alpha : float or array_like Parameter $$\alpha$$ beta : float or array_like Parameter $$\beta$$ axis : None or int or tuple of ints, optional (default None) Axes of v over which to compute the $$\ell_2$$ norm. If None, an entire multi-dimensional array is treated as a vector. If axes are specified, then distinct norm values are computed over the indices of the remaining axes of input array v, which is equivalent to the proximal operator of the sum over these values (i.e. an $$\ell_{2,1}$$ norm). x : ndarray Output array
sporco.prox.norm_nuclear(X)[source]

Compute the nuclear norm

$\| X \|_* = \sum_i \sigma_i$

where $$\sigma_i$$ are the singular values of matrix $$X$$.

Parameters: X : array_like Input array $$X$$ nncl : float Nuclear norm of X
sporco.prox.prox_nuclear(V, alpha)[source]

Proximal operator of the nuclear norm [7] with parameter $$\alpha$$.

Parameters: v : array_like Input array $$V$$ alpha : float Parameter $$\alpha$$ X : ndarray Output array s : ndarray Singular values of X