Python reference¶
The package fastprox: one-shot functions, which return the result, and
operator classes, which also give derivatives. The API guide
describes each operator's mathematics, parameters and derivatives; this page
is generated from the docstrings.
fastprox: exact proximal operators and projections with derivatives.
Every operator computes
along one axis of a float32 or float64 array, batched over the other axes.
Projections ignore gamma. Image operators (TVAniso) act on the last
two or three axes instead and are iterative: they report a duality gap.
One-shot functions (tv1d, project_simplex,
...) return the result; operator classes (TV1D, Simplex, ...) also give
Jacobian-vector and vector-Jacobian products for bilevel and implicit
differentiation::
op = fastprox.TV1D(weights=w)
z, ctx = op.prox(x, gamma, keep=True)
dz = op.jvp(ctx, dx)
gx, grads = op.vjp(ctx, g) # grads.gamma, grads.weights
Info
¶
Bases: NamedTuple
Certificate of a prox call: duality gap (0 for exact operators), iterations, and number of entries that sat on a tie.
IterInfo
¶
Bases: NamedTuple
Certificate of an iterative operator: the duality gap of the prox
problem at the returned point (summed over the batch;
\(\lVert z - z^* \rVert_2^2 \le 2\,\mathrm{gap}\) per image), the iterations
(the maximum over the batch), whether every image reached the tolerance,
the dual of shape (ndim, *x.shape), which
warm_start= accepts back, and (since 1.0) zerr, the certified
relative error of the worst image,
\(\max_i r_i + u(1 + r_i) \ge \lVert z_i - z_i^* \rVert_2 / \lVert x_i \rVert_2\) with
\(r_i = \sqrt{2\,\mathrm{gap}_i} / \lVert x_i \rVert_2\) and \(u\) the unit roundoff of
the output dtype, for the rounding of the array returned (since 1.0.1;
\(2u\) after prox_conj), in the units ztol= takes (0 for an image
of zeros). It holds to working precision: the gap is evaluated in
floating point. gap and zerr
are NaN when an image contains a NaN;
converged says whether no image stopped at max_iter (an image with
a NaN is not iterated and counts as finished).
DerivInfo
¶
Bases: NamedTuple
Report of the last derivative on a context (ctx.deriv; since 1.0
with four fields): the residual and iterations of an iterative solve
(isotropic TV's conjugate gradients; 0 for derivatives in closed form),
whether the derivative is exact at the saved point, and the smoothing
used where it is not. Anisotropic TV is exact once its polish certified
the regions, graph TV when no part was stopped by tol, tree TV and
the operators in closed form always; isotropic TV caps its curvature at
\(\gamma / \mu\) with \(\mu\) = smoothing (in the units of \(x\)), which
vanishes with the gap. ctx.refine or refine= make it exact or
nearly so. Exact means that the saved regions are those of the solution,
as certified at the saved point; it is not a bound in terms of the gap,
which alone does not certify a derivative (since 1.0.1: near a switch, a
tiny gap can come with wrong regions).
Grads(gamma: float, params: np.ndarray, fields: dict)
¶
Parameter gradients returned by :meth:Operator.vjp.
gamma is the gradient with respect to the step (with respect to \(\sigma\)
after prox_conj), params the flat gradient with respect to the
operator's parameter vector, and each named parameter is an attribute.
Context(op, ws, shape, dtype, axis, threads)
¶
Structure saved by prox(..., keep=True): the input to jvp and
vjp. Pass it back as ctx= to reuse its memory in the next call.
Calls on one context are serialised (since 1.0): for parallel derivatives
use one context per thread.
refine(ztol=None, *, tol=None, max_iter=100000, warn=True)
¶
Solves the kept call again, from its saved input and its dual as a
warm start, to ztol (or the gap tolerance tol; inside
:func:inner_accuracy its ztol by default), and returns the refined
\(z\) (since 1.0; iterative image operators). The derivatives then read
the refined point, which is what makes them exact or nearly so at a
loose first solve (ctx.deriv.exact, which then says whether the
refined point's regions are certified: near a switch between regions,
refining identifies them only once the margin of the switch exceeds
the remaining error), and ctx.info is the
refined call's. The \(z\) returned by the first call is not changed: use
the one returned here. Graph TV refines to tol=0, the exact
solution, for any ztol. A refine that stops at max_iter raises
:class:ConvergenceWarning unless warn=False.
jacobian_diag(branch=None, kink_tol=0.0)
¶
Diagonal of the Jacobian \(\partial z / \partial x\) at the saved point, for elementwise
operators (since 0.2): jvp(ctx, dx=ones), with branch and
kink_tol as in :meth:Operator.jvp, so at a kink it is the
chosen piece's slope. For the nonconvex maps an entry reads off its
SCD subspace: 0 where the entry is fixed at zero, 1 on a piece
without curvature (the identity, or soft's shift), and otherwise
the slope of the concave branch, \(b / (b - \gamma w)\) for MCP. After
prox_conj it is the diagonal of the conjugate prox's Jacobian.
Other operators raise ValueError: their Jacobian is not diagonal.
kinks(tol=0.0)
¶
Kink codes of the saved point, an int8 array of its shape (since
0.2; soft thresholding, l1 over a box, SCAD and MCP, and since 0.3 the
ties of l0, lq and the log penalty): 0 away from a kink, \(k \ge 1\) within
tol (absolute, in the units of the input) of the operator's
breakpoint \(k\), the nearest one (see fp_workspace_kinks in
fastprox.h for the numbering). Pass the entries to keep and the side
to jvp/vjp as branch. Since 0.3 also 1D TV (1 at the tail
of an edge whose dual is on its bound with no jump), anisotropic TV
(bit \(a\) for such an edge along axis \(a\)) and isotropic TV (1 at a pixel
with no gradient whose dual is on its sphere; no branch overrides).
Since 0.4 the box, the orthant, the simplex, the l1 ball, group l2
and graph and tree TV, whose kinks are their edges: their masks and
branches have the shape of x with the last axis of length
len(edges) (1 at an edge with no jump whose flow is on its
bound).
AccuracyWarning
¶
Bases: UserWarning
An iterative prox certified less accuracy than asked for (since 1.0):
inside :func:inner_accuracy, a call whose own tol or ztol is
looser than the block's, or one that stopped before it.
ConvergenceWarning
¶
Bases: AccuracyWarning
An iterative prox stopped at max_iter before its tolerance (since
1.0). The message gives zerr, the relative error of \(z\) that was
certified. solve(..., warn=False) silences one call; the standard
warning filters the rest.
Operator(handle)
¶
Base class: a compiled operator with fixed parameters.
Subclasses set _layout, a list of (name, length, scalar) entries
that split the flat parameter vector into named fields.
nparams: int
property
¶
Length of the parameter vector \(\theta\).
prox(x, gamma=1.0, *, axis=-1, out=None, threads=0, keep=False, ctx=None, copy=False)
¶
\(\operatorname{prox}_{\gamma g}(x)\). With keep=True returns (z, ctx).
gamma is a scalar, or (since 1.0) an array that broadcasts to the
batch shape (the shape of x without axis): one step per row.
Then jvp's dgamma moves every step, and vjp's
grads.gamma is the sum over rows of each row's gradient.
out may be x itself or any array that shares memory with it;
an overlapping input is copied first (since 1.0; the same for the
out of jvp and vjp). It must be writeable, without zero
strides.
value(x, *, axis=-1, tol=1e-06)
¶
The value \(g(x)\) (since 0.5): one per row along axis (per image
for the image operators), a float for a single row or else an array
of the batch shape. The indicator of a set is 0 when \(x\) lies in it,
each constraint violated by at most
\(\mathrm{tol} \cdot \max(1, \max_i \lvert x_i \rvert)\), and inf
otherwise; a row with a NaN gives NaN.
prox_conj(y, sigma=1.0, *, axis=-1, out=None, threads=0, keep=False, ctx=None, copy=False)
¶
\(\operatorname{prox}_{\sigma g^*}(y) = y - \sigma \operatorname{prox}_{g/\sigma}(y/\sigma)\) (Moreau) for a convex \(g\). For the nonconvex penalties the call returns the same formula, the Moreau residual, which is not the prox of \(g^*\) (their \(g^*\) is the indicator of \(\{0\}\)).
jvp(ctx: Context, dx=None, dgamma=0.0, dparams=None, *, out=None, tol=None, max_iter=_MAX_ITER, refine=None, branch=None, kink_tol=0.0)
¶
\(J_x \, dx + (\partial z / \partial \gamma) \, d\gamma + (\partial z / \partial \theta) \, d\theta\) at the saved point.
tol and max_iter (on every operator since 1.0) control iterative
derivative solves (isotropic TV: see :class:TVIso) and are accepted
and ignored by every other operator, whose derivatives are in closed
form. ctx.deriv is then a :class:DerivInfo: the solve's residual
and iterations, and whether the derivative is exact.
refine=ztol (since 1.0; iterative image operators, ignored by the
others) first calls ctx.refine(ztol): the derivative is then that
at the refined point. A derivative that is not exact, at a certified
error of \(z\) above 1e-4 (inside :func:inner_accuracy, above its
ztol), raises :class:AccuracyWarning once per point.
branch (soft thresholding, l1 over a box, SCAD and MCP; since 0.2):
-1, 0 or +1 per entry. At the entries within kink_tol of a
breakpoint (ctx.kinks(kink_tol) nonzero), -1 and +1 take the
piece on the \(x - \varepsilon\) and the \(x + \varepsilon\) side of it, so +1
matches the one-sided difference
\((\operatorname{prox}(x + h e_i) - \operatorname{prox}(x)) / h\); 0 and all
other entries keep the default rule.
vjp(ctx: Context, g, *, out=None, tol=None, max_iter=_MAX_ITER, refine=None, branch=None, kink_tol=0.0)
¶
(\(J_x^\top g\), Grads) at the saved point; tol, max_iter,
refine and branch as in :meth:jvp.
Soft(lam=1.0, weights=None)
¶
Bases: Operator
\(g(z) = \lambda \sum_i w_i \lvert z_i \rvert\) (soft thresholding).
Parameters: weights (scalar when not given); grads.lam is also provided.
ElasticNet(l1=1.0, l2=1.0)
¶
Bases: Operator
\(g(z) = \ell_1 \lVert z \rVert_1 + \tfrac{\ell_2}{2} \lVert z \rVert_2^2\). Parameters: l1, l2.
Huber(lam=1.0, delta=1.0)
¶
Bases: Operator
\(g(z) = \lambda \sum_i h_\delta(z_i)\), \(h_\delta(t) = t^2 / (2\delta)\) for \(\lvert t \rvert \le \delta\) and \(\lvert t \rvert - \delta/2\) otherwise. Parameters: lam, delta.
GroupL2(lam=1.0, groups=None, group_weights=None)
¶
Bases: Operator
\(g(z) = \lambda \sum_g c_g \lVert z_g \rVert_2\) along the axis. groups gives a
group id per entry (None: one group, the l2 norm). Parameters:
group_weights.
TreeL2(groups=(), group_weights=None, l1=0.0)
¶
Bases: Operator
\(g(z) = \ell_1 \lVert z \rVert_1 + \sum_g \eta_g \lVert z_g \rVert_2\) along the
axis, for groups that are pairwise nested or disjoint (a tree; Bach et al.
2012, (3.8)). groups is a sequence of index arrays, in any order; ValueError when two groups
overlap without nesting. group_weights: None (\(\eta = 1\)), a scalar, or one
per group. Parameters: l1, group_weights (\(\eta\)).
sparse_group(l1=1.0, lam=1.0, groups=None, group_weights=None)
classmethod
¶
The sparse group lasso \(\ell_1 \lVert z \rVert_1 + \lambda \sum_g c_g \lVert z_g \rVert_2\) for a group id per entry (as in GroupL2); \(\eta = \lambda c\).
Box(lower=-np.inf, upper=np.inf)
¶
Bases: Operator
Projection onto \(\mathrm{lower} \le z \le \mathrm{upper}\) (scalars or per-entry along the axis; infinities allowed). Parameters: lower, upper.
LogBarrier(lam=1.0)
¶
Bases: Operator
\(g(z) = -\lambda \sum_i \log z_i\), \(\lambda > 0\): \(z = (x + \sqrt{x^2 + 4 \gamma \lambda}) / 2\) (Beck, Lemma 6.5). Parameters: lam.
L1Box(lam=1.0, lower=-np.inf, upper=np.inf, weights=None)
¶
Bases: Operator
\(g(z) = \lambda \sum_i w_i \lvert z_i \rvert\) restricted to
\(\mathrm{lower} \le z \le \mathrm{upper}\):
\(z = \operatorname{clip}(\operatorname{soft}(x, \gamma \lambda w), \mathrm{lower}, \mathrm{upper})\)
(Beck, Example 6.23). The
weights and bounds are scalars or one entry per element along the axis.
Parameters: weights, lower, upper; grads.lam is also provided.
SOC()
¶
Bases: Operator
Projection onto the second-order cone \(\{(t, y) : \lVert y \rVert_2 \le t\}\) along the axis, with \(t\) the first entry (Beck, Example 6.37).
GroupHuber(lam=1.0, delta=1.0, groups=None, group_weights=None)
¶
Bases: _GroupRadial
\(g(z) = \lambda \sum_g c_g H_\delta(\lVert z_g \rVert_2)\), with \(H_\delta\) the Huber function of Huber: \(z_g = (1 - \gamma c_g \lambda / \max(\lVert x_g \rVert_2, \delta + \gamma c_g \lambda)) \, x_g\) (Beck, Example 6.66). Parameters: lam, delta, group_weights.
GroupSCAD(lam=1.0, a=3.7, groups=None, group_weights=None)
¶
Bases: _GroupRadial
Group SCAD: \(\sum_g c_g \operatorname{SCAD}(\lVert z_g \rVert_2)\) with threshold \(\lambda\) and concavity \(a > 1\); the prox needs \(a > 1 + \gamma \max c\) (ValueError otherwise). Parameters: lam, a, group_weights.
GroupMCP(lam=1.0, b=3.0, groups=None, group_weights=None)
¶
Bases: _GroupRadial
Group MCP: \(\sum_g c_g \operatorname{MCP}(\lVert z_g \rVert_2)\) with threshold \(\lambda\) and concavity \(b > 0\); the prox needs \(b > \gamma \max c\) (ValueError otherwise). Parameters: lam, b, group_weights.
L2Ball(radius=1.0)
¶
Bases: Operator
Projection onto \(\lVert z \rVert_2 \le \mathrm{radius}\) along the axis. Parameters: radius.
Simplex(radius=1.0)
¶
Bases: Operator
Projection onto \(\{z \ge 0, \sum_i z_i = \mathrm{radius}\}\) along the axis (Condat 2016). Parameters: radius.
L1Ball(radius=1.0, weights=None)
¶
Bases: Operator
Projection onto \(\sum_i w_i \lvert z_i \rvert \le \mathrm{radius}\) along the axis. Parameters: radius.
LInf(lam=1.0)
¶
Max(lam=1.0)
¶
Bases: Operator
\(g(z) = \lambda \max_i z_i\) along the axis: \(z = \min(x, \tau)\) by the Moreau identity with the simplex. Parameters: lam.
SumLargest(lam=1.0, k=1, absolute=False)
¶
Bases: Operator
\(g(z) = \lambda\) (sum of the \(k\) largest \(z_i\)) along the axis, \(k\) at most the axis length; with absolute=True the \(k\) largest \(\lvert z_i \rvert\) (any \(k\); \(k \ge n\) is \(\lambda \lVert z \rVert_1\)). Parameters: lam.
Hyperplane(a=None, b=0.0, lower=-np.inf, upper=np.inf)
¶
Bases: Operator
Projection onto \(\{a^\top z = b, \ \mathrm{lower} \le z \le \mathrm{upper}\}\) along the axis (Beck, Theorem 6.27): \(a\) is a scalar or one entry per element (None: all ones), the box as in Box (unbounded by default). Raises ValueError when the set is empty for the axis length. Parameters: b, a, lower, upper.
HalfSpace(a=None, b=0.0, lower=-np.inf, upper=np.inf)
¶
Bases: Hyperplane
Projection onto \(\{a^\top z \le b, \ \mathrm{lower} \le z \le \mathrm{upper}\}\) along the axis; the box projection when it satisfies the constraint, else as Hyperplane. Parameters: b, a, lower, upper.
Isotonic(weights=None, increasing=True)
¶
Bases: Operator
Projection onto the monotone cone along the axis (pool-adjacent- violators), minimising \(\sum_i w_i (z_i - x_i)^2\). Parameters: weights, all > 0 with min/max >= 1e-100 (since 1.0).
With unequal weights the fit is the projection in the metric \(W\), and
:meth:prox_conj raises ValueError (since 1.0.1): \(y - P(y)\) is not
the prox of the Euclidean conjugate, though \(W(y - P(y))\) lies in the
polar cone. Equal weights keep the conjugate.
SortedL1(weights)
¶
Bases: Operator
The sorted \(\ell_1\) norm (OWL, SLOPE; since 1.0) along the axis:
the magnitudes in decreasing order, with weights \(w_1 \ge w_2 \ge
\dots \ge 0\): one per entry of the axis, or a scalar (then it is
soft thresholding, bit for bit). By a sort and pool-adjacent-violators
(Bogdan et al., 2015), \(O(n \log n)\). On singular values it is the
weighted nuclear norm: :class:WeightedNuclearNorm. Parameters:
weights.
TV1D(weights=None, method='auto')
¶
Bases: Operator
\(g(z) = \sum_i w_i \lvert z_{i+1} - z_i \rvert\) along the axis (1D total
variation).
weights: scalar or one per edge (axis length - 1). method: "auto"
(Condat's algorithm, taut string when it backtracks too much), "condat"
or "taut_string". Parameters: weights.
TV1DBall(alpha=1.0, weights=None)
¶
Bases: Operator
Projection onto \(\{z : \sum_i w_i \lvert z_{i+1} - z_i \rvert \le \alpha\}\) along the axis (Beck, Theorem 6.30): \(x\) when inside, else the 1D TV prox at the step where the TV equals \(\alpha\). Weights as in TV1D. Parameters: alpha, weights.
TV1DL2(weights=None)
¶
Bases: Operator
\(g(z) = \lVert W D z \rVert_2 = \sqrt{\sum_i w_i^2 (z_{i+1} - z_i)^2}\) along the axis: 1D TV with the l2 norm of the differences (Newton on the dual trust-region problem, to rounding). Weights as in TV1D; a positive weight below 2^-511 times the largest raises ValueError (since 1.0.1). Parameters: weights.
TVAniso(ndim=2, weights=None, edge_weights=None)
¶
Bases: _ImageOperator
Anisotropic total variation of 2D or 3D images, on the last ndim
axes and batched over the others:
with optional edge weights \(\beta \ge 0\) (since 0.3; 1 without them) of shape
(ndim, *image shape), beta[a, p] weighting the edge from \(p\) to its
forward neighbour along \(a\) (the last entries along \(a\) are unused), for spatially
varying regularisation; the operator then takes only images of that
shape.
Iterative (accelerated dual block methods with exact 1D TV steps): each
image stops when its duality gap is at most \(\mathrm{tol} \cdot \lVert x \rVert_2^2 / 2\),
which certifies \(\lVert z - z^* \rVert_2 \le \sqrt{\mathrm{tol}}\,\lVert x \rVert_2\):
the default 1e-6 gives \(z\) to 1e-3 relative, tol=1e-10 to 1e-5.
ztol= (since 1.0) asks for that relative error directly, and
info.zerr reports the one certified for the array returned, its
rounding to the dtype included (since 1.0.1; see "Inexact proxes inside
outer solvers" in the API docs).
prox returns z (or (z, ctx) with keep=True, where
ctx.info is an :class:IterInfo). warm_start=dual starts from a
dual (IterInfo.dual); with ctx= and warm=True a call starts from
the dual of the previous call on that context. Parameters: weights (one
per axis, or a scalar for all), and edge_weights when given (a gradient of
their shape, zero at the unused entries).
GraphTV(n, edges, weights=None)
¶
Bases: _ImageOperator
Total variation on a graph, on the last axis (length n) and batched
over the others:
edges is an array of shape (m, 2) of node indices, \(u \ne v\) (repeated
edges add); weights a scalar or one per edge, all \(\ge 0\). By parametric
max-flow (Chambolle and Darbon; Hochbaum), each part of the graph cut at
its mean value: exact up to rounding where a part ends at a trivial cut,
else within \(\mathrm{tol} \cdot (\max x - \min x)\) at every node, so tol=0 (the
default) asks for the solution to rounding. ztol= (since 1.0) asks for
\(\lVert z - z^* \rVert_2 \le \mathrm{ztol}\,\lVert x \rVert_2\) per signal instead,
through that bound, and info.zerr is the error the gap certifies, as
for :class:TVAniso. info.gap is the duality
gap with the flow as the dual, info.iters the number of max-flow
solves; info.dual (shape (1, *x.shape)) is \(q\) with \(z = x - q\). Warm
starts have no effect. With tol=0 jvp and vjp are exact:
averages over the regions where \(z\) is constant. With tol > 0 the
solver may stop a part at its mean before it is split, and the
derivatives are those of the regions it stopped at, accurate only as far
as those regions are the solution's; use tol=0 when derivatives
matter. Parameters: weights.
Kinks (since 0.4) are edges: ctx.kinks and branch have the
shape of x with the last axis over the edges, in the order of
edges. An edge is at a kink when its ends are equal and the
solver's flow on it is on its bound (on a graph with cycles the flow is
not unique; this is the one behind info.gap). The mask is then the
edges biactive in that flow: on a graph with cycles it can flag edges
where the prox is smooth, and a branch override there may select no
piece the prox has (since 1.0.1). -1 joins its ends (the
default), +1 keeps them apart; a region splits only where every edge
across the split is kept apart.
TreeTV(n, edges, weights=None)
¶
Bases: GraphTV
Total variation on a tree or forest, on the last axis (length n)
and batched over the others: :class:GraphTV's penalty for edges
that form a forest (no cycles or repeated edges, any order and
orientation; a chain is a tree). By dynamic programming (Kolmogorov, Pock
and Rolinek), \(O(n \log n)\) and exact up to rounding; tol and
max_iter are ignored and info.iters is 1. info.gap,
info.dual, the derivatives and the kinks are those of
:class:GraphTV, with the flow unique on a forest. Parameters: weights.
TVIso(ndim=2, weights=None, pixel_weights=None)
¶
Bases: _ImageOperator
Isotropic total variation of 2D or 3D images, on the last ndim axes
and batched over the others:
with forward differences (zero past the last entry); the weights scale
each axis inside the norm (e.g. voxel spacing), and the optional pixel
weights \(\alpha \ge 0\) (since 0.3; 1 without them) each pixel's term, for
spatially varying regularisation. With pixel weights the operator takes
only images of their shape. Iterative (fast gradient
projection on the dual), with the gap, warm starts and keep as in
:class:TVAniso; the dual u (IterInfo.dual) has
\(\lVert u_p \rVert_2 \le \gamma \alpha_p\) and \(z = x - \sum_a w_a D_a^\top u_a\).
jvp and vjp solve a linear system by conjugate gradients to relative residual tol and record the residual
and iterations reached in ctx.deriv; by default (tol=None) they
stop at the relative error of \(z\) that the prox's gap certifies,
\(\sqrt{2\,\mathrm{gap}} / \lVert x \rVert_2\), and at \(10^{-10}\) at the tightest.
Parameters: weights, and pixel_weights when given (a gradient of their
shape).
L0(lam=1.0, weights=None)
¶
Bases: _Pointwise
\(g(z) = \lambda \sum_i w_i [z_i \ne 0]\) (hard thresholding at \(\sqrt{2 \gamma \lambda w_i}\)). The map jumps there, from 0 to the threshold, and the derivative at the jump is the selected branch's, a convention. Parameters: weights (the map is piecewise constant in them).
Lq(lam=1.0, q=0.5, weights=None)
¶
Bases: _Pointwise
\(g(z) = \lambda \sum_i w_i \lvert z_i \rvert^q\) with \(0 < q < 1\) (closed form
for \(q = 1/2\) and \(2/3\), safeguarded Newton otherwise). The map jumps from
0 to \(\beta = (2c(1 - q))^{1/(2-q)}\), \(c = \gamma\lambda w_i\), at
\(\lvert x_i \rvert = \beta + c q \beta^{q-1}\), and the derivative at the jump
is the selected branch's, a convention. Parameters: weights;
grads.lam is also provided.
SCAD(lam=1.0, a=3.7, weights=None)
¶
Bases: _Pointwise
\(g(z) = \sum_i w_i \operatorname{SCAD}(z_i)\), the SCAD penalty (Fan and Li 2001) with threshold \(\lambda\) and concavity \(a > 1\); entry \(i\) is the unweighted map at the step \(\gamma w_i\). The prox needs \(a > 1 + \gamma \max(w)\) (ValueError otherwise). Parameters: lam, a, and weights when given (a scalar or one per element along the axis).
MCP(lam=1.0, b=3.0, weights=None)
¶
Bases: _Pointwise
\(g(z) = \sum_i w_i \operatorname{MCP}(z_i)\), the minimax concave penalty (Zhang 2010) with threshold \(\lambda\) and concavity \(b > 0\) (\(w \operatorname{MCP}(\lambda, b) = \operatorname{MCP}(w \lambda, b/w)\)). The prox needs \(b > \gamma \max(w)\) (ValueError otherwise). Parameters: lam, b, and weights when given.
LogPenalty(lam=1.0, eps=1.0)
¶
Bases: _Pointwise
\(g(z) = \lambda \sum_i \log(1 + \lvert z_i \rvert / \varepsilon)\), \(\varepsilon > 0\). The map is Lipschitz for \(\gamma\lambda < \varepsilon^2\), Hölder-½ at \(\lvert x \rvert = \varepsilon\) for \(\gamma\lambda = \varepsilon^2\), and jumps at its tie above; there the derivative is the selected branch's, a convention. Parameters: lam, eps.
SpectralContext(op, u, s, vt, z, inner, shape)
¶
Structure saved by Spectral.prox(..., keep=True): the decomposition,
the prox of the spectrum, and the inner operator's context.
info: Info
property
¶
The inner prox call's certificate (ties on the spectrum).
Spectral(op: Operator, kind='svd')
¶
An operator on the singular values (kind="svd") or the eigenvalues
(kind="eigh", symmetric matrices) of each matrix of a batch (since 1.0):
\(g(X) = h(\sigma(X))\) with \(h\) the wrapped operator, so that
op must be absolutely symmetric for singular values (Soft gives the
nuclear norm, L1Ball the nuclear-norm ball, LInf the spectral
norm, a symmetric Box the spectral-norm ball, and the nonconvex maps
low-rank penalties) and permutation invariant for eigenvalues (also
NonNeg: the PSD cone, Simplex: the spectraplex, LogBarrier:
\(-\lambda \log\det\)). The decomposition and the matrix products are NumPy's
(numpy.linalg.svd, eigh); the derivatives come from the C core, also
where singular values repeat or sit on a threshold, where autograd through
an SVD fails. Between two distinct values the derivative holds their
divided difference, to rounding that grows as one over their gap (since
1.0.1 also across a breakpoint of the scalar map between them). An eigh input that is not symmetric is replaced by
\((X + X^\top)/2\).
prox(x, gamma=1.0, *, threads=0, keep=False, ctx=None, copy=False)
¶
\(\operatorname{prox}_{\gamma g}(X)\) of each matrix in the last two axes.
With keep=True returns (Z, ctx).
prox_from(u, s, vh, gamma=1.0, *, threads=0, keep=False, ctx=None)
¶
The prox from a decomposition the caller has: \(U\) (..., m, r), \(s\)
(..., r) and \(V^\top\) (..., r, n), as numpy.linalg.svd returns them
with full_matrices=False (for eigh: \(Q\), the eigenvalues and
\(Q^\top\)). It may hold only the leading triplets when the others map
to zero, as in singular value thresholding below \(\gamma\lambda\);
derivatives need the full thin decomposition.
value(x, *, tol=1e-06)
¶
\(g(X) = h(\sigma(X))\) per matrix: a float for one matrix, else an array of the batch shape.
jvp(ctx: SpectralContext, dx, dgamma=0.0, dparams=None, *, tol=None, max_iter=_MAX_ITER)
¶
The derivative of \(X \mapsto \operatorname{prox}_{\gamma g}(X)\) in the
direction dx, plus \(d\gamma\) and \(d\theta\) (the inner operator's
parameters) terms. tol and max_iter are accepted and ignored,
as by every closed-form operator (:meth:Operator.jvp).
vjp(ctx: SpectralContext, g, *, tol=None, max_iter=_MAX_ITER)
¶
(\(J^\top g\), Grads): the map is self-adjoint, and the gradients in
\(\gamma\) and the inner operator's parameters are those of the spectrum.
tol and max_iter as in :meth:jvp.
NuclearNorm(lam=1.0)
¶
Bases: Spectral
\(g(X) = \lambda \lVert X \rVert_* = \lambda \sum_i \sigma_i(X)\): singular
value thresholding (since 1.0). Its parameters are those of Soft.
WeightedNuclearNorm(weights, kind='svd')
¶
Bases: Spectral
\(g(X) = \sum_k w_k \sigma_k(X)\) with \(\sigma_1 \ge \sigma_2 \ge \dots\)
the singular values and weights \(w_1 \ge w_2 \ge \dots \ge 0\), one per
singular value (\(\min(m, n)\)) or a scalar (since 1.0): Spectral(SortedL1(w)),
convex. Nondecreasing weights (as in WNNM) give a nonconvex penalty and
are not supported. Its parameters are those of :class:SortedL1.
SpectralNormBall(radius=1.0)
¶
Bases: Spectral
The indicator of \(\{X : \sigma_{\max}(X) \le r\}\): singular values clipped at \(r\) (since 1.0).
PSD()
¶
Bases: Spectral
The indicator of the positive semidefinite cone: negative eigenvalues set to zero (since 1.0).
default_threads() -> int
¶
Threads used when threads=0: the environment variable
FASTPROX_NUM_THREADS, else the first number in OMP_NUM_THREADS, else
the CPUs this process may run on (read once). 1 for a serial build.
inner_accuracy(target, factor=0.1)
¶
Inner accuracy for the iterative operators of a block (since 1.0):
target is the accuracy the outer solver needs on \(z\), relative to the
prox's input, and every iterative call in the block that sets neither
tol nor ztol uses ztol = factor * target, so that the inner
error never decides the outer test.
with fp.inner_accuracy(1e-5): # ztol = 1e-6 for the calls below
z = op.prox(x, gamma)
A call whose own tol or ztol certifies less raises
:class:AccuracyWarning, and one that stops at max_iter
:class:ConvergenceWarning. Blocks nest, and the state is a context
variable: each thread and asyncio task has its own. Under jax.jit the
block in force when the function is traced applies. Yields the ztol.
soft_threshold(x, lam=1.0, gamma=1.0, *, weights=None, out=None, axis=-1, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i w_i \lvert z_i \rvert\).
elastic_net(x, l1=1.0, l2=1.0, gamma=1.0, *, out=None, threads=0, copy=False)
¶
prox of \(\gamma (\ell_1 \lVert z \rVert_1 + \tfrac{\ell_2}{2} \lVert z \rVert_2^2)\).
huber(x, lam=1.0, delta=1.0, gamma=1.0, *, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i h_\delta(z_i)\).
group_soft_threshold(x, lam=1.0, gamma=1.0, *, groups=None, group_weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_g c_g \lVert z_g \rVert_2\) along the axis.
prox_l2(x, lam=1.0, gamma=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \lVert z \rVert_2\) along the axis.
project_box(x, lower=-np.inf, upper=np.inf, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\mathrm{lower} \le z \le \mathrm{upper}\).
project_nonneg(x, *, out=None, threads=0, copy=False)
¶
Projection onto \(z \ge 0\).
project_l2_ball(x, radius=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\lVert z \rVert_2 \le \mathrm{radius}\) along the axis.
project_simplex(x, radius=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\{z \ge 0, \sum_i z_i = \mathrm{radius}\}\) along the axis.
project_l1_ball(x, radius=1.0, *, weights=None, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\sum_i w_i \lvert z_i \rvert \le \mathrm{radius}\) along the axis.
prox_linf(x, lam=1.0, gamma=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \lVert z \rVert_\infty\) along the axis.
prox_max(x, lam=1.0, gamma=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \max_i z_i\) along the axis.
prox_sum_largest(x, lam=1.0, k=1, gamma=1.0, *, absolute=False, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda\) (sum of the \(k\) largest \(z_i\), or \(\lvert z_i \rvert\)) along the axis.
project_hyperplane(x, a=None, b=0.0, lower=-np.inf, upper=np.inf, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\{a^\top z = b, \ \mathrm{lower} \le z \le \mathrm{upper}\}\) along the axis.
project_halfspace(x, a=None, b=0.0, lower=-np.inf, upper=np.inf, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\{a^\top z \le b, \ \mathrm{lower} \le z \le \mathrm{upper}\}\) along the axis.
isotonic(x, *, weights=None, increasing=True, axis=-1, out=None, threads=0, copy=False)
¶
Isotonic regression (projection onto the monotone cone) along the axis.
tv1d(x, gamma=1.0, *, weights=None, axis=-1, method='auto', out=None, threads=0, copy=False)
¶
prox of \(\gamma \sum_i w_i \lvert z_{i+1} - z_i \rvert\) along the axis.
tv1d_l2(x, gamma=1.0, *, weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \sqrt{\sum_i w_i^2 (z_{i+1} - z_i)^2}\) along the axis.
tv_aniso(x, gamma=1.0, *, weights=None, ndim=2, tol=None, ztol=None, max_iter=1000, warm_start=None, out=None, threads=0, copy=False, warn=True)
¶
prox of \(\gamma \sum_a w_a \mathrm{TV}_a\) on the last ndim (2 or 3) axes.
Returns (z, info); info.gap certifies the result and info.dual
can be passed back as warm_start.
tv_iso(x, gamma=1.0, *, weights=None, ndim=2, tol=None, ztol=None, max_iter=1000, warm_start=None, out=None, threads=0, copy=False, warn=True)
¶
prox of \(\gamma \sum_p \lVert (w_a D_a z)_p \rVert_2\) (isotropic TV) on the
last ndim (2 or 3) axes. Returns (z, info) as :func:tv_aniso.
graph_tv(x, edges, gamma=1.0, *, n=None, weights=None, tol=None, ztol=None, max_iter=1000, out=None, threads=0, copy=False, warn=True)
¶
prox of \(\gamma \sum_e w_e \lvert z_u - z_v \rvert\) over edges (pairs
\((u, v)\)) on the last axis. Returns (z, info) as :func:tv_aniso.
tree_tv(x, edges, gamma=1.0, *, n=None, weights=None, out=None, threads=0, copy=False)
¶
prox of \(\gamma \sum_e w_e \lvert z_u - z_v \rvert\) over edges (pairs
\((u, v)\)) that form a forest, on the last axis. Returns (z, info) as
:func:tv_aniso.
hard_threshold(x, lam=1.0, gamma=1.0, *, weights=None, tie='nonzero', out=None, axis=-1, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i w_i [z_i \ne 0]\).
lq(x, lam=1.0, q=0.5, gamma=1.0, *, weights=None, tie='nonzero', out=None, axis=-1, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i w_i \lvert z_i \rvert^q\), \(0 < q < 1\).
scad(x, lam=1.0, a=3.7, gamma=1.0, *, weights=None, out=None, axis=-1, threads=0, copy=False)
¶
prox of \(\gamma \sum_i w_i \operatorname{SCAD}(\lambda, a)(z_i)\); needs \(a > 1 + \gamma \max(w)\).
mcp(x, lam=1.0, b=3.0, gamma=1.0, *, weights=None, out=None, axis=-1, threads=0, copy=False)
¶
prox of \(\gamma \sum_i w_i \operatorname{MCP}(\lambda, b)(z_i)\); needs \(b > \gamma \max(w)\).
prox_log(x, lam=1.0, eps=1.0, gamma=1.0, *, tie='nonzero', out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i \log(1 + \lvert z_i \rvert / \varepsilon)\).
prox_log_barrier(x, lam=1.0, gamma=1.0, *, out=None, threads=0, copy=False)
¶
prox of \(-\gamma \lambda \sum_i \log z_i\).
prox_l1_box(x, lam=1.0, lower=-np.inf, upper=np.inf, gamma=1.0, *, weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_i w_i \lvert z_i \rvert\) over \(\mathrm{lower} \le z \le \mathrm{upper}\).
project_soc(x, *, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\{(t, y) : \lVert y \rVert_2 \le t\}\) along the axis, \(t\) the first entry.
group_huber(x, lam=1.0, delta=1.0, gamma=1.0, *, groups=None, group_weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \lambda \sum_g c_g H_\delta(\lVert z_g \rVert_2)\) along the axis.
group_scad(x, lam=1.0, a=3.7, gamma=1.0, *, groups=None, group_weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \sum_g c_g \operatorname{SCAD}(\lVert z_g \rVert_2)\) along the axis.
group_mcp(x, lam=1.0, b=3.0, gamma=1.0, *, groups=None, group_weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma \sum_g c_g \operatorname{MCP}(\lVert z_g \rVert_2)\) along the axis.
tree_soft_threshold(x, groups, group_weights=None, l1=0.0, gamma=1.0, *, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma (\ell_1 \lVert z \rVert_1 + \sum_g \eta_g \lVert z_g \rVert_2)\) for tree-structured groups.
sparse_group_soft_threshold(x, l1=1.0, lam=1.0, gamma=1.0, *, groups=None, group_weights=None, axis=-1, out=None, threads=0, copy=False)
¶
prox of \(\gamma (\ell_1 \lVert z \rVert_1 + \lambda \sum_g c_g \lVert z_g \rVert_2)\), one group id per entry.
project_tv1d_ball(x, alpha=1.0, *, weights=None, axis=-1, out=None, threads=0, copy=False)
¶
Projection onto \(\{z : \sum_i w_i \lvert z_{i+1} - z_i \rvert \le \alpha\}\) along the axis.