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
|
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. |
|
Undo the array shape conversion applied by |
|
Compute the \(\ell_0\) "norm" (it is not really a norm) |
|
Compute the proximal operator of the \(\ell_0\) "norm" (hard thresholding) |
|
Compute the \(\ell_1\) norm |
|
Compute the proximal operator of the \(\ell_1\) norm (scalar shrinkage/soft thresholding) |
|
Projection operator of the \(\ell_1\) norm. |
|
Compute the squared \(\ell_2\) norm |
|
Compute the \(\ell_2\) norm |
|
Compute the \(\ell_{2,1}\) mixed norm |
|
Compute the proximal operator of the \(\ell_2\) norm (vector shrinkage/soft thresholding) |
|
Compute the projection operator of the \(\ell_2\) norm |
|
Compute the difference of \(\ell_1\) and \(\ell_2\) norms, i.e. \(\| X \|_1 - \beta \| X \|_2\), for matrix \(X\). |
|
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]. |
|
Compute the proximal operator of the sum of \(\ell_1\) and \(\ell_2\) norms (compound shrinkage/soft thresholding) [59] [15] |
|
Compute the nuclear norm |
|
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
- 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