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 [20]

\[\|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 use a notation that reverses the positions of \(p\) and \(q\).

The proximal operator of function \(f\) is defined as

\[\mathrm{prox}_f(\mathbf{v}) = \mathrm{argmin}_{\mathbf{x}} \left\{ (1/2) \| \mathbf{x} - \mathbf{v} \|_2^2 + 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) Proximal operator of the \(\ell_0\) “norm” (hard thresholding)
norm_l1(x[, axis]) Compute the \(\ell_1\) norm
prox_l1(v, alpha) Proximal operator of the \(\ell_1\) norm (scalar shrinkage/soft thresholding)
proj_l1(v, gamma[, axis, method]) Projection operator of the \(\ell_1\) norm.
_proj_l1_scalar_root(v, gamma) Projection operator of the \(\ell_1\) norm.
_proj_l1_sortsum(v, gamma[, axis]) 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]) Proximal operator of the \(\ell_2\) norm (vector shrinkage/soft thresholding)
proj_l2(v, gamma[, axis]) Projection operator of the \(\ell_2\) norm.
prox_l1l2(v, alpha, beta[, axis]) Proximal operator of the \(\ell_1\) plus \(\ell_2\) norm (compound shrinkage/soft thresholding) [38] [10]
norm_nuclear(x) Compute the nuclear norm
prox_nuclear(v, alpha) Proximal operator of the nuclear norm [7].

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.

Returns:
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.

Returns:
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.

Returns:
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]

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}\]

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\)

Returns:
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.

Returns:
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]

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\)

Returns:
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 [23].
  • ‘sortcumsum’
    The solution is computed via the method of [12].
Returns:
x : ndarray

Output array

sporco.prox._proj_l1_scalar_root(v, gamma)[source]

Projection operator of the \(\ell_1\) norm. The solution is computed via the method of Sec. 6.5.2 in [23].

There is no axis parameter since the algorithm for computing the solution treats the input v as a single vector.

Parameters:
v : array_like

Input array \(\mathbf{v}\)

gamma : float

Parameter \(\gamma\)

Returns:
x : ndarray

Output array

sporco.prox._proj_l1_sortsum(v, gamma, axis=None)[source]

Projection operator of the \(\ell_1\) norm. The solution is computed via the method of [12].

Parameters:
v : array_like

Input array \(\mathbf{v}\)

gamma : float

Parameter \(\gamma\)

axis : None or int, 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. Note: specifying a tuple of ints is not supported by this function.

Returns:
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.

Returns:
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.

Returns:
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.

Returns:
nl21 : float

Norm of \(X\)

sporco.prox.prox_l2(v, alpha, axis=None)[source]

Proximal operator of the \(\ell_2\) norm (vector shrinkage/soft thresholding)

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

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).

Returns:
x : ndarray

Output array

sporco.prox.proj_l2(v, gamma, axis=None)[source]

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.

Returns:
x : ndarray

Output array

sporco.prox.prox_l1l2(v, alpha, beta, axis=None)[source]

Proximal operator of the \(\ell_1\) plus \(\ell_2\) norm (compound shrinkage/soft thresholding) [38] [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\).

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).

Returns:
x : ndarray

Output array

sporco.prox.norm_nuclear(x)[source]

Compute the nuclear norm

\[\| X \|_1 = \sum_i \sigma_i\]

where \(\sigma_i\) are the singular values of matrix \(X\).

Parameters:
x : array_like

Input array \(X\)

Returns:
nncl : float

Norm of x

sporco.prox.prox_nuclear(v, alpha)[source]

Proximal operator of the nuclear norm [7].

Parameters:
v : array_like

Input array \(V\)

alpha : float

Parameter \(\alpha\)

Returns:
x : ndarray

Output array

s : ndarray

Singular values of x