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

\[\|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 [43]) 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

norm_dl1l2(x[, beta, axis])

Compute the difference of \(\ell_1\) and \(\ell_2\) norms, i.e. \(\| X \|_1 - \beta \| X \|_2\), for matrix \(X\).

prox_dl1l2(v, alpha[, beta, axis])

Compute the proximal operator of the difference of \(\ell_1\) and \(\ell_2\) norms, i.e. \(\alpha \left( \| X \|_1 - \beta \| X \|_2 \right)\) [34].

prox_sl1l2(v, alpha, beta[, axis])

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

norm_nuclear(X)

Compute the nuclear norm

prox_nuclear(V, alpha)

Proximal operator of the nuclear norm [11] 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
xarray_like

Multi-dimensional input array

axisint or tuple of ints, optional (default -1)

Axes of x to be grouped together to form the rows of the output 2d array.

Returns
xtrndarray

2D output array

rsituple

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
xtrarray_like

Two-dimensional input array

rsituple

A tuple containing the shape of the axis-permuted array and the permutation order applied in ndto2d.

Returns
xndarray

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
xarray_like

Input array \(\mathbf{x}\)

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

epsfloat, optional (default 0.0)

Absolute value threshold below which a number is considered to be zero.

Returns
nl0float 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 [32]) 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
varray_like

Input array \(\mathbf{v}\)

alphafloat or array_like

Parameter \(\alpha\)

Returns
xndarray

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
xarray_like

Input array \(\mathbf{x}\)

axisNone 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
nl1float 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
varray_like

Input array \(\mathbf{v}\)

alphafloat or array_like

Parameter \(\alpha\)

Returns
xndarray

Output array

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

Projection operator of the \(\ell_1\) norm.

Parameters
varray_like

Input array \(\mathbf{v}\)

gammafloat

Parameter \(\gamma\)

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

methodNone 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 [39].

  • ‘sortcumsum’

    The solution is computed via the method of [19].

Returns
xndarray

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
xarray_like

Input array \(\mathbf{x}\)

axisNone 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
nl2float 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
xarray_like

Input array \(\mathbf{x}\)

axisNone 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
nl2float 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
xarray_like

Input array \(X\)

axisNone 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
nl21float

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
varray_like

Input array \(\mathbf{v}\)

alphafloat or array_like

Parameter \(\alpha\)

axisNone 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
xndarray

Output array

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

Compute the projection operator of the \(\ell_2\) norm

\[\mathrm{proj}_{f, \gamma}(\mathbf{v}) = \mathrm{argmin}_{\mathbf{x}} (1/2) \| \mathbf{x} - \mathbf{v} \|_2^2 \; \text{ s.t. } \; \| \mathbf{x} \|_2 \leq \gamma \;,\]

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

Note that the projection operator of the \(\ell_2\) norm centered at \(\mathbf{s}\),

\[\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})\).

Parameters
varray_like

Input array \(\mathbf{v}\)

gammafloat

Parameter \(\gamma\)

axisNone 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
xndarray

Output array

sporco.prox.norm_dl1l2(x, beta=1.0, axis=None)[source]

Compute the difference of \(\ell_1\) and \(\ell_2\) norms, i.e. \(\| X \|_1 - \beta \| X \|_2\), for matrix \(X\).

Parameters
xarray_like

Input array \(X\)

betafloat, optional (default 1.0)

Parameter \(\beta \geq 0\)

axisNone or int or tuple of ints, optional (default None)

Axes of x over which to compute the \(\ell_1\) and \(\ell_2\) norms. 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
dl1l2float or ndarray

Difference of \(\ell_1\) and \(\ell_2\) norms of \(X\)

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

Compute the proximal operator of the difference of \(\ell_1\) and \(\ell_2\) norms, i.e. \(\alpha \left( \| X \|_1 - \beta \| X \|_2 \right)\) [34]. The function block for the axis=None case is a Python translation of the Matlab implementation by the authors of [34].

Parameters
varray_like

Input array \(\mathbf{v}\)

alphafloat

Parameter \(\alpha \geq 0\)

betafloat, optional (default 1.0)

Parameter \(1 \leq \beta \geq 0\)

axisNone or int, optional (default None)

Axis of v over which to compute the difference of \(\ell_1\) and \(\ell_2\) norms. If None, an entire multi-dimensional array is treated as a vector. If the axis is 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 components.

Returns
xndarray

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) [59] [15]

\[\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
varray_like

Input array \(\mathbf{v}\)

alphafloat or array_like

Parameter \(\alpha\)

betafloat or array_like

Parameter \(\beta\)

axisNone 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
xndarray

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
Xarray_like

Input array \(X\)

Returns
nnclfloat

Nuclear norm of X

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

Proximal operator of the nuclear norm [11] with parameter \(\alpha\).

Parameters
varray_like

Input array \(V\)

alphafloat

Parameter \(\alpha\)

Returns
Xndarray

Output array

sndarray

Singular values of X