Examples¶
Short scripts that use the Python package; each prints what it checks and runs in about a second. From a clone of the repository:
uv run python examples/basic_usage.py
uv run --group examples python examples/tv_denoising.py # with a plot (matplotlib)
The test suite runs every script, so they stay in step with the API.
basic_usage.py¶
One-shot functions, operator objects, axis, dtypes, out=, the conjugate prox, threads
On GitHub · uv run python examples/basic_usage.py
Source
"""Basic usage: one-shot functions, operator objects, axes, dtypes and threads.
Every function computes prox_{gamma g}(x) = argmin_z g(z) + ||z - x||^2 / (2 gamma)
along one axis of an array (the last by default), independently for each row.
uv run python examples/basic_usage.py
"""
import numpy as np
import fastprox as fp
def main():
rng = np.random.default_rng(0)
x = rng.normal(size=(3, 6))
# -- One-shot functions --------------------------------------------------
print("soft thresholding (lam = 0.5):\n", fp.soft_threshold(x, lam=0.5).round(3))
p = fp.project_simplex(x, radius=1.0)
print("simplex projection: rows sum to", p.sum(axis=1), " min entry", p.min())
b = fp.project_l2_ball(x, radius=1.0)
print("l2 ball projection: row norms", np.linalg.norm(b, axis=1).round(6))
print("isotonic regression of [3, 1, 2, 5, 4]:", fp.isotonic([3.0, 1, 2, 5, 4]))
print("1D TV of [0, 0, 5, 5, 5] with gamma = 1:", fp.tv1d([0.0, 0, 5, 5, 5], gamma=1.0))
# -- Axis: the same operator along columns instead of rows ---------------
pc = fp.project_simplex(x, axis=0)
print("simplex along axis 0: columns sum to", pc.sum(axis=0))
# Strided views are used as they are, without a copy.
print("every other column:", fp.project_simplex(x[:, ::2]).sum(axis=1))
# -- dtypes and output buffers --------------------------------------------
x32 = x.astype(np.float32)
print("float32 in, float32 out:", fp.tv1d(x32, gamma=0.5).dtype)
try:
fp.tv1d(np.arange(5)) # integers are not converted silently
except TypeError as e:
print("TypeError:", e)
print("with copy=True:", fp.tv1d(np.arange(5), gamma=0.5, copy=True))
out = np.empty_like(x)
fp.soft_threshold(x, lam=0.5, out=out) # write into a preallocated buffer
y = x.copy()
fp.soft_threshold(y, lam=0.5, out=y) # or in place
print("out= and in place agree:", np.array_equal(out, y))
# -- Operator objects: fixed parameters, prox and conjugate prox ----------
op = fp.TV1D(weights=0.8)
z = op.prox(x, 0.5)
print(op, "matches tv1d:", np.array_equal(z, fp.tv1d(x, 0.5, weights=0.8)))
# Moreau identity: x = prox_{gamma g}(x) + gamma prox_{g*/gamma}(x / gamma).
gamma = 0.5
r = op.prox(x, gamma) + gamma * op.prox_conj(x / gamma, 1 / gamma)
print("Moreau identity residual:", np.abs(r - x).max())
# -- Threads: rows run in parallel, with identical results for any count --
big = rng.normal(size=(256, 4096))
one = fp.tv1d(big, gamma=2.0, threads=1)
many = fp.tv1d(big, gamma=2.0, threads=4)
print(f"default threads: {fp.default_threads()}; "
f"1 vs 4 threads bit-identical: {np.array_equal(one, many)}")
if __name__ == "__main__":
main()
tv_denoising.py¶
1D TV denoising for a range of γ, and a batch of signals in one call
On GitHub · uv run python examples/tv_denoising.py
Source
"""Denoise a piecewise-constant signal with 1D total variation.
z = argmin_z gamma * sum_i |z_{i+1} - z_i| + ||z - y||^2 / 2
Small gamma leaves noise in; large gamma merges steps and shrinks their
height. Plots the result if matplotlib is installed:
uv run --group examples python examples/tv_denoising.py
"""
import numpy as np
import fastprox as fp
def make_signal(rng, n=1000, sigma=0.5):
jumps = np.sort(rng.choice(np.arange(50, n - 50, 25), size=8, replace=False))
x = np.zeros(n)
for j in jumps:
x[j:] += rng.normal(scale=2.0)
return x, x + sigma * rng.normal(size=n)
def main(plot=True):
rng = np.random.default_rng(1)
x, y = make_signal(rng)
print(" gamma RMSE pieces")
results = {}
for gamma in (0.5, 2.0, 8.0, 32.0, 128.0):
z = fp.tv1d(y, gamma=gamma)
pieces = 1 + np.count_nonzero(np.diff(z))
rmse = np.sqrt(np.mean((z - x) ** 2))
results[gamma] = z
print(f"{gamma:6.1f} {rmse:7.4f} {pieces:7d}")
print(f"noisy {np.sqrt(np.mean((y - x) ** 2)):7.4f} "
f"(clean signal has {1 + np.count_nonzero(np.diff(x))} pieces)")
# Many signals at once: each row is denoised independently, in parallel.
batch = np.stack([make_signal(rng)[1] for _ in range(64)])
zb = fp.tv1d(batch, gamma=8.0)
print("batch of", zb.shape[0], "signals: row 0 matches a single call:",
np.array_equal(zb[0], fp.tv1d(batch[0], gamma=8.0)))
if plot:
try:
import matplotlib.pyplot as plt
except ImportError:
print("(install matplotlib, e.g. `uv run --group examples ...`, to see a plot)")
return
fig, ax = plt.subplots(figsize=(10, 4))
ax.plot(y, color="0.75", lw=0.8, label="noisy")
ax.plot(x, "k", lw=1.5, label="clean")
for gamma in (2.0, 32.0):
ax.plot(results[gamma], lw=1.2, label=f"TV, gamma = {gamma:g}")
ax.legend()
ax.set_title("1D total variation denoising")
fig.tight_layout()
plt.show()
if __name__ == "__main__":
main()
proximal_gradient.py¶
FISTA for the lasso, and a batch of simplex-constrained least-squares problems
On GitHub · uv run python examples/proximal_gradient.py
Source
"""Proximal gradient methods with fastprox as the prox step.
1. Lasso, min_x ||A x - b||^2 / 2 + lam ||x||_1, by FISTA with soft thresholding.
2. Least squares over the simplex, min_{x in simplex} ||A x - b||^2 / 2,
by accelerated projected gradient, solving a batch of problems at once:
each row of X is a separate problem and one call projects all of them.
Both stop on the fixed-point residual ||x - prox_{t g}(x - t grad f(x))|| / t,
which is zero exactly at a solution.
uv run python examples/proximal_gradient.py
"""
import numpy as np
import fastprox as fp
def fista(grad, prox, x0, t, iters=500, tol=1e-8):
"""FISTA (Beck and Teboulle, 2009) with step t <= 1/L."""
x = y = x0
s = 1.0
for k in range(iters):
x_new = prox(y - t * grad(y), t)
s_new = (1 + np.sqrt(1 + 4 * s * s)) / 2
y = x_new + ((s - 1) / s_new) * (x_new - x)
x, s = x_new, s_new
res = np.linalg.norm(x - prox(x - t * grad(x), t)) / t
if res < tol:
break
return x, k + 1, res
def lasso(rng):
m, n, k = 100, 300, 10
A = rng.normal(size=(m, n)) / np.sqrt(m)
x_true = np.zeros(n)
x_true[rng.choice(n, k, replace=False)] = rng.normal(scale=3.0, size=k)
b = A @ x_true + 0.01 * rng.normal(size=m)
lam = 0.02
t = 1 / np.linalg.norm(A, 2) ** 2
x, iters, res = fista(lambda x: A.T @ (A @ x - b),
lambda v, t: fp.soft_threshold(v, lam=lam, gamma=t),
np.zeros(n), t, iters=5000)
print(f"lasso: {iters} iterations, residual {res:.1e}")
print(f" support found {np.flatnonzero(x).size} entries, "
f"true support recovered: {set(np.flatnonzero(x_true)) <= set(np.flatnonzero(x))}")
print(f" relative error {np.linalg.norm(x - x_true) / np.linalg.norm(x_true):.3f}")
def simplex_least_squares(rng):
# 32 problems sharing A: each row of B is a mixture to unmix into weights on
# the 20 columns of A (nonnegative, summing to 1).
m, n, p = 50, 20, 32
A = rng.uniform(size=(m, n))
W_true = fp.project_simplex(rng.normal(scale=2.0, size=(p, n)))
B = W_true @ A.T + 0.01 * rng.normal(size=(p, m))
t = 1 / np.linalg.norm(A, 2) ** 2
W, iters, res = fista(lambda W: (W @ A.T - B) @ A,
lambda V, t: fp.project_simplex(V),
np.full((p, n), 1 / n), t, iters=5000, tol=1e-6)
print(f"simplex least squares, {p} problems at once: {iters} iterations, "
f"residual {res:.1e}")
print(f" rows sum to 1: {np.allclose(W.sum(axis=1), 1)}, min entry {W.min():.1e}, "
f"max error vs true weights {np.abs(W - W_true).max():.3f}")
def main():
rng = np.random.default_rng(0)
lasso(rng)
simplex_least_squares(rng)
if __name__ == "__main__":
main()
derivatives.py¶
JVP and VJP in x, γ and the parameters, checked against finite differences and for adjointness
On GitHub · uv run python examples/derivatives.py
Source
"""Derivatives of a prox: JVP, VJP and parameter gradients.
``op.prox(x, gamma, keep=True)`` saves the structure of the solution in a
context. From it, ``op.jvp`` applies the Jacobian of z = prox_{gamma g}(x) to
directions in x, gamma and the operator's parameters, and ``op.vjp`` applies
its transpose. Both are exact for the saved structure (an element of the
generalised Jacobian at kinks, see docs/api.md) and cost about one pass over
the data. This script checks them against finite differences.
uv run python examples/derivatives.py
"""
import numpy as np
import fastprox as fp
def main():
rng = np.random.default_rng(0)
n = 100
x = np.cumsum(rng.normal(size=(8, n)), axis=1) # 8 random walks, one per row
w = rng.uniform(0.5, 2.0, size=n - 1) # one TV weight per edge
gamma = 1.5
op = fp.TV1D(weights=w)
z, ctx = op.prox(x, gamma, keep=True)
print(op, "parameters:", op.nparams, " certificate:", ctx.info)
# -- JVP: derivative of z along a direction in (x, gamma, w) ------------
dx = rng.normal(size=x.shape)
dgamma = 0.3
dw = rng.normal(size=w.shape)
dz = op.jvp(ctx, dx=dx, dgamma=dgamma, dparams={"weights": dw})
eps = 1e-6
def prox_at(s):
return fp.TV1D(weights=w + s * dw).prox(x + s * dx, gamma + s * dgamma)
fd = (prox_at(eps) - prox_at(-eps)) / (2 * eps)
print(f"JVP vs finite differences: max error {np.abs(dz - fd).max():.1e}")
# -- VJP: gradients of a scalar loss L(z) -------------------------------
target = rng.normal(size=x.shape)
g = z - target # dL/dz for L = ||z - target||^2 / 2
gx, grads = op.vjp(ctx, g=g)
print(grads.weights.shape, "edge-weight gradients; dL/dgamma =", f"{grads.gamma:.4f}")
# Adjointness: <g, J d> = <J^T g, d> for the same direction d.
lhs = np.vdot(g, dz)
rhs = np.vdot(gx, dx) + grads.gamma * dgamma + np.vdot(grads.weights, dw)
print(f"<g, J d> = {lhs:.10f}\n<J^T g, d> = {rhs:.10f}")
# -- Repeated calls: pass ctx back to reuse its memory ------------------
for gamma in (0.5, 1.0, 2.0):
z, ctx = op.prox(x, gamma, keep=True, ctx=ctx)
_, grads = op.vjp(ctx, g=z - target)
print(f"gamma = {gamma}: loss {0.5 * np.sum((z - target) ** 2):9.3f}, "
f"dL/dgamma {grads.gamma:9.3f}")
# -- Other operators: the same calls, named parameter gradients ---------
v = rng.normal(size=(4, 20))
for op in (fp.Simplex(radius=2.0), fp.Soft(lam=0.5), fp.Huber(lam=1.0, delta=0.5)):
z, ctx = op.prox(v, 1.0, keep=True)
_, grads = op.vjp(ctx, g=np.ones_like(v))
print(f"{op!r:28} {grads}")
if __name__ == "__main__":
main()
bilevel_learning.py¶
Learning γ, then one TV weight per edge, from clean/noisy pairs by gradients through the prox
On GitHub · uv run python examples/bilevel_learning.py
Source
"""Learn TV regularisation weights from data (bilevel learning).
Training pairs are noisy and clean piecewise-constant signals whose jumps sit
at the same positions in every signal (a sensor whose state switches at known
times, say). The lower level denoises each signal with weighted 1D TV,
z(w) = argmin_z sum_i w_i |z_{i+1} - z_i| + ||z - y||^2 / 2,
and the upper level fits the weights to the clean signals,
min_{w >= 0} L(w) = mean over signals of ||z(w) - x||^2 / 2.
The gradient of L comes from one VJP of the prox: with g = dL/dz, ``op.vjp``
returns g^T dz/dw summed over the batch. We first learn one scalar step (as a
user would tune gamma), then one weight per edge by projected gradient.
uv run python examples/bilevel_learning.py
"""
import numpy as np
import fastprox as fp
N, M = 200, 512 # signal length, training signals
JUMPS = [40, 75, 120, 160]
def make_signals(rng, m, sigma=0.3):
"""m clean signals with jumps at JUMPS (random levels) and noisy copies."""
edges = [0, *JUMPS, N]
levels = rng.normal(size=(m, len(edges) - 1))
x = np.concatenate([np.repeat(levels[:, [k]], edges[k + 1] - edges[k], axis=1)
for k in range(len(edges) - 1)], axis=1)
return x, x + sigma * rng.normal(size=x.shape)
def loss(z, x):
return 0.5 * np.mean(np.sum((z - x) ** 2, axis=1))
def loss_and_grad(op, gamma, y, x):
"""L at (op, gamma) and its VJP: (L, grads) with grads.gamma, grads.weights."""
z, ctx = op.prox(y, gamma, keep=True)
_, grads = op.vjp(ctx, g=(z - x) / len(x))
return loss(z, x), grads
def main():
rng = np.random.default_rng(0)
x_train, y_train = make_signals(rng, M)
x_test, y_test = make_signals(rng, M)
print(f"noisy input: test loss {loss(y_test, x_test):8.4f}")
# 1. One scalar step, gradient descent on t = log(gamma) to keep gamma > 0.
op = fp.TV1D()
t = np.log(0.1)
for _ in range(30):
_, grads = loss_and_grad(op, np.exp(t), y_train, x_train)
t -= 0.5 * grads.gamma * np.exp(t) # dL/dt = dL/dgamma * gamma
gamma = float(np.exp(t))
test_scalar = loss(op.prox(y_test, gamma), x_test)
print(f"learned gamma: test loss {test_scalar:8.4f} (gamma = {gamma:.3f})")
# Check against a grid search on the training loss.
grid = np.linspace(0.5 * gamma, 1.5 * gamma, 101)
best = grid[np.argmin([loss(fp.tv1d(y_train, g), x_train) for g in grid])]
print(f"grid search: best gamma {best:.3f}")
# 2. One weight per edge, starting from the scalar, projected onto w >= 0.
w = np.full(N - 1, gamma)
for _ in range(300):
_, grads = loss_and_grad(fp.TV1D(weights=w), 1.0, y_train, x_train)
w = fp.project_nonneg(w - 2.0 * grads.weights)
test_edges = loss(fp.TV1D(weights=w).prox(y_test, 1.0), x_test)
print(f"learned weights: test loss {test_edges:8.4f}")
# The smallest weights should sit on the jumps (edge i joins samples i, i+1).
found = sorted(int(i) + 1 for i in np.argsort(w)[:len(JUMPS)])
print(f"lowest weights at: {found} (jumps at {JUMPS})")
print(f"median weight {np.median(w):.3f}, on the jumps {w[np.array(JUMPS) - 1].round(3)}")
return w
if __name__ == "__main__":
main()
image_denoising.py¶
Isotropic and anisotropic TV of images (0.2): gap certificates, warm starts, a batch, and learning γ through the VJP of an iterative operator
On GitHub · uv run python examples/image_denoising.py
Source
"""Denoise images with isotropic and anisotropic total variation (since 0.2).
z = argmin_z gamma * TV(z) + ||z - y||^2 / 2
Anisotropic TV sums |differences| along each axis; isotropic TV sums the
length of the gradient at each pixel, so it does not favour edges aligned
with the axes. Both are iterative: each call returns a duality gap that
certifies the result, ||z - z*||^2 <= 2 * gap, and a dual that warm-starts
the next call. The last part learns gamma from clean/noisy pairs with the
VJP of the prox, which solves for the derivative of the solution instead of
differentiating through the iterations. Plots the results if matplotlib is
installed:
uv run --group examples python examples/image_denoising.py
"""
import time
import numpy as np
import fastprox as fp
SIGMA = 0.3 # noise level
def make_image(rng, n=128):
"""A tilted square and a disk with random positions and levels."""
i, j = np.mgrid[0:n, 0:n] / n
img = np.zeros((n, n))
ci, cj = rng.uniform(0.3, 0.7, size=2)
u, v = (i - ci + j - cj) / np.sqrt(2), (i - ci - j + cj) / np.sqrt(2)
img[(np.abs(u) < 0.18) & (np.abs(v) < 0.18)] = rng.uniform(0.5, 1.0)
di, dj = rng.uniform(0.2, 0.8, size=2)
img[(i - di) ** 2 + (j - dj) ** 2 < 0.12 ** 2] = rng.uniform(-1.0, -0.5)
return img
def psnr(z, x):
return 10 * np.log10(np.ptp(x) ** 2 / np.mean((z - x) ** 2))
def loss(z, x):
return 0.5 * np.mean((z - x) ** 2)
def main(plot=True):
rng = np.random.default_rng(0)
x = make_image(rng)
y = x + SIGMA * rng.normal(size=x.shape)
gamma = 0.3
print(f"noisy: PSNR {psnr(y, x):5.2f} dB")
# 1. One image, both models. The gap bounds the distance to the exact
# solution; divided by the pixel count it bounds the RMS error.
results = {}
for name, solve in (("isotropic", fp.tv_iso), ("anisotropic", fp.tv_aniso)):
t = time.perf_counter()
z, info = solve(y, gamma=gamma, tol=1e-5)
t = time.perf_counter() - t
results[name] = z
print(f"{name:12s} PSNR {psnr(z, x):5.2f} dB {info.iters:4d} iterations, "
f"{1e3 * t:4.0f} ms RMS error <= {np.sqrt(2 * info.gap / z.size):.0e}, "
f"converged: {info.converged}")
# 2. Nearby problems, e.g. a fine sweep over gamma: starting each call from
# the previous dual saves iterations (the dual is projected onto the new
# constraint |u_p| <= gamma, so any dual is a valid start).
gammas = np.linspace(0.25, 0.35, 8)
cold = sum(fp.tv_iso(y, gamma=g, tol=1e-5)[1].iters for g in gammas)
dual, warm = None, 0
for g in gammas:
_, info = fp.tv_iso(y, gamma=g, tol=1e-5, warm_start=dual)
dual, warm = info.dual, warm + info.iters
print(f"sweep of {len(gammas)} gammas: {cold} iterations cold, {warm} warm-started")
# 3. A batch: leading axes are independent images, solved in parallel.
batch = np.stack([make_image(rng) for _ in range(16)])
noisy = batch + SIGMA * rng.normal(size=batch.shape)
t = time.perf_counter()
zb, info = fp.tv_iso(noisy, gamma=gamma, tol=1e-5)
t = time.perf_counter() - t
print(f"batch of {len(batch)} images in {1e3 * t:.0f} ms: "
f"PSNR {psnr(noisy, batch):5.2f} -> {psnr(zb, batch):5.2f} dB, "
f"converged: {info.converged}")
# 4. Learn gamma from training pairs (bilevel): minimise L(gamma) =
# mean (z(gamma) - x)^2 / 2 by gradient descent on log(gamma). One VJP
# gives dL/dgamma; warm=True starts each prox from the previous dual.
train = np.stack([make_image(rng, 64) for _ in range(4)])
ytrain = train + SIGMA * rng.normal(size=train.shape)
op = fp.TVIso(ndim=2)
s, ctx = np.log(0.05), None
for _ in range(10):
z, ctx = op.prox(ytrain, np.exp(s), keep=True, ctx=ctx, tol=1e-8, max_iter=10 ** 5, warm=True)
_, grads = op.vjp(ctx, g=(z - train) / z.size)
s -= 100.0 * grads.gamma * np.exp(s) # dL/dlog(gamma) = gamma dL/dgamma
learned = float(np.exp(s))
residual, cg_iters = ctx.deriv.residual, ctx.deriv.iters
grid = learned * np.geomspace(0.5, 2.0, 15)
losses = [loss(fp.tv_iso(ytrain, gamma=g, tol=1e-6, max_iter=10 ** 5)[0], train) for g in grid]
best = grid[np.argmin(losses)]
print(f"learned gamma {learned:.3f} (grid search: {best:.3f}); last VJP: "
f"{cg_iters} CG iterations, relative residual {residual:.0e}")
if plot:
try:
import matplotlib.pyplot as plt
except ImportError:
print("(install matplotlib, e.g. `uv run --group examples ...`, to see a plot)")
return
panels = [("clean", x), ("noisy", y), *((f"{k} TV", v) for k, v in results.items())]
fig, axes = plt.subplots(1, 4, figsize=(12, 3.4))
for ax, (title, im) in zip(axes, panels):
ax.imshow(im, cmap="gray", vmin=-1.2, vmax=1.2)
ax.set_title(title)
ax.axis("off")
fig.tight_layout()
plt.show()
return learned, best
if __name__ == "__main__":
main()
group_sparsity.py¶
Lasso, group lasso, sparse group lasso, group MCP and SCAD (0.2) on grouped regression with λ chosen on a validation set, and hierarchical sparsity with tree-structured groups
On GitHub · uv run python examples/group_sparsity.py
Source
"""Select groups of features: lasso, group lasso, sparse group lasso, group
MCP and SCAD, and hierarchical (tree) sparsity (since 0.2).
The 400 features of a regression come in 40 groups of 10 (the levels of a
categorical variable, the genes of a pathway, the lags of a series). Only 4
groups matter, and within each only 4 of the 10 features. Each penalty g is
fitted by
min_x ||A x - b||^2 / 2 + g(x)
with FISTA (plain proximal gradient for the nonconvex ones) along a path of
lam, and lam is chosen on a validation set of 1000 samples:
- the lasso finds the features but spreads extras over many groups;
- the group lasso selects whole groups, so every feature of a group enters;
- the sparse group lasso, l1 + group l2 (``TreeL2.sparse_group``), is sparse
at both levels;
- group MCP and SCAD, started from the group lasso, drop the spurious groups
and the shrinkage bias, though like the group lasso they keep every
feature of a selected group.
The last part uses nested groups: with one group per node of a tree holding
the node and its descendants, a node can be nonzero only if its parent is
(Jenatton, Mairal, Obozinski and Bach, JMLR 12, 2011).
uv run python examples/group_sparsity.py
"""
import numpy as np
import fastprox as fp
N, NVAL, G, S = 150, 1000, 40, 10 # samples, validation samples, groups, group size
GROUPS = np.arange(G * S) // S # group id of each feature
LAMS = np.geomspace(3.0, 0.005, 20)
def make_problem(rng):
x0 = np.zeros(G * S)
for g in rng.choice(G, 4, replace=False):
idx = g * S + rng.choice(S, 4, replace=False)
x0[idx] = rng.choice([-1, 1], 4) * rng.uniform(1, 2, 4)
A = rng.normal(size=(N, G * S)) / np.sqrt(N)
Av = rng.normal(size=(NVAL, G * S)) / np.sqrt(N)
b = A @ x0 + 0.1 * rng.normal(size=N)
bv = Av @ x0 + 0.1 * rng.normal(size=NVAL)
return A, b, Av, bv, x0
def fit(op, A, b, x, iters=400, momentum=True):
"""FISTA, or proximal gradient with momentum=False."""
t = 1.0 / np.linalg.norm(A, 2) ** 2
y, s = x.copy(), 1.0
for _ in range(iters):
x_new = op.prox(y - t * (A.T @ (A @ y - b)), t)
s_new = (1 + np.sqrt(1 + 4 * s * s)) / 2 if momentum else 1.0
y = x_new + (s - 1) / s_new * (x_new - x)
x, s = x_new, s_new
return x
def path(make_op, A, b, Av, bv, x, momentum=True, warm=True):
"""Fit along LAMS, each from the previous solution (warm) or from x; return
(lam, x) with the best validation error."""
best = (np.inf, None, None)
start = x
for lam in LAMS:
x = fit(make_op(lam), A, b, x if warm else start.copy(), momentum=momentum)
err = np.mean((Av @ x - bv) ** 2)
if err < best[0]:
best = (err, lam, x.copy())
return best[1], best[2]
def report(name, lam, x, x0):
true = np.unique(GROUPS[x0 != 0])
found = np.unique(GROUPS[x != 0])
extra_groups = len(np.setdiff1d(found, true))
extra = np.sum((x != 0) & (x0 == 0))
missed = np.sum((x == 0) & (x0 != 0))
err = np.linalg.norm(x - x0) / np.linalg.norm(x0)
print(f"{name:20s} {lam:6.3f} {extra_groups:6d} {extra:7d} {missed:6d} {err:8.3f}")
return extra_groups, extra, err
def main():
rng = np.random.default_rng(0)
A, b, Av, bv, x0 = make_problem(rng)
zero = np.zeros_like(x0)
print(f"{'penalty':20s} {'lam':>6s} {'extra':>6s} {'extra':>7s} {'missed':>6s} "
f"{'rel. err':>8s}")
print(f"{'':20s} {'':6s} {'groups':>6s} {'feat.':>7s} {'feat.':>6s}")
results = {}
convex = {
"lasso": lambda lam: fp.Soft(lam),
"group lasso": lambda lam: fp.GroupL2(lam, GROUPS),
"sparse group lasso": lambda lam: fp.TreeL2.sparse_group(l1=lam / 2, lam=lam / 2,
groups=GROUPS),
}
for name, make_op in convex.items():
lam, x = path(make_op, A, b, Av, bv, zero)
results[name] = report(name, lam, x, x0)
if name == "group lasso":
x_group = x
# Nonconvex: each lam starts from the group lasso solution.
nonconvex = {
"group MCP": lambda lam: fp.GroupMCP(lam, b=3.0, groups=GROUPS),
"group SCAD": lambda lam: fp.GroupSCAD(lam, a=3.7, groups=GROUPS),
}
for name, make_op in nonconvex.items():
lam, x = path(make_op, A, b, Av, bv, x_group, momentum=False, warm=False)
results[name] = report(name, lam, x, x0)
# Hierarchical sparsity on a binary tree of 15 nodes in heap order (the
# children of node i are 2i + 1 and 2i + 2), e.g. wavelet coefficients.
# One group per node: the node and all its descendants. The weights are
# set so both keep about the same share of nodes.
def subtree(i):
return [i] if i >= 15 else [i, *subtree(2 * i + 1), *subtree(2 * i + 2)]
tree = [[j for j in subtree(i) if j < 15] for i in range(15)]
parent = (np.arange(1, 15) - 1) // 2
x = rng.normal(size=(10000, 15)) # 10000 rows, one call each
z_tree = fp.tree_soft_threshold(x, tree, group_weights=0.8)
z_l1 = fp.soft_threshold(x, lam=1.0)
print("\nnodes kept, and rows where a kept node has a zero parent:")
for name, z in (("l1", z_l1), ("tree", z_tree)):
orphans = np.any((z[:, 1:] != 0) & (z[:, parent] == 0), axis=1)
print(f" {name:5s} {np.mean(z != 0):5.1%} kept, {np.mean(orphans):6.1%} of rows")
return results
if __name__ == "__main__":
main()
weighted_glasso.py¶
Weighted graphical lasso by ADMM (0.2): the −log det step as eigh plus LogBarrier, the penalty step as weighted Soft or weighted MCP on the packed upper triangle; the graphical lasso against adaptive weights and weighted MCP, with a KKT check
On GitHub · uv run python examples/weighted_glasso.py
Source
"""Weighted graphical lasso by ADMM (since 0.2).
A sparse precision matrix Theta0 (a chain of 40 variables plus a few long
range edges) is estimated from n = 120 samples, with S their covariance,
by solving
min_Theta -log det Theta + tr(S Theta) + sum_{i != j} w_ij rho(Theta_ij)
(w symmetric, the diagonal unpenalised) for three penalties: the graphical
lasso (rho = lam |t|, w = 1), the adaptive graphical lasso (w_ij from a
first estimate, small where it found a strong edge) and a weighted MCP with
the same weights. The weights remove most spurious edges, and MCP, which
stops shrinking large entries, then lowers the estimation error. Over
twelve random problems the weights halved the spurious edges or better every
time (at the cost of up to four more missed edges in some), and MCP lowered
the error further in nine.
ADMM (Boyd et al., Distributed Optimization and Statistical Learning via
ADMM, 2011, Section 6.5) alternates
Theta <- prox of -log det (step 1/r) at Z - U - S/r: eigh, then
LogBarrier on the eigenvalues, (d + sqrt(d^2 + 4/r)) / 2
Z <- prox of the penalty at Theta + U: weighted Soft or weighted
MCP at the step 1/r on the packed upper triangle (each pair
appears twice in the penalty and in ||Theta + U - Z||_F^2)
U <- U + Theta - Z
Matrix prox maps stay out of the C library until version 2; here the
eigendecomposition is numpy's and fastprox maps the eigenvalues. For the
convex problems the KKT conditions are checked at the end. With MCP the
problem is not convex and ADMM is a heuristic; started from the adaptive
solution, it converges here.
uv run python examples/weighted_glasso.py
"""
import numpy as np
import fastprox as fp
P, N_SAMPLES = 40, 120
def make_problem(rng):
theta = np.eye(P)
for i in range(P - 1): # a chain
theta[i, i + 1] = theta[i + 1, i] = 0.4
for _ in range(8): # and long-range edges
i, j = rng.choice(P, 2, replace=False)
theta[i, j] = theta[j, i] = rng.choice([-1, 1]) * 0.3
theta += (0.25 - min(0.0, np.linalg.eigvalsh(theta).min())) * np.eye(P)
# x = L^{-T} g with Theta = L L^T has covariance Theta^{-1}. The Cholesky
# factor is unique, so every platform draws the same samples
# (multivariate_normal factors by SVD, whose signs depend on LAPACK).
L = np.linalg.cholesky(theta)
x = np.linalg.solve(L.T, rng.standard_normal((P, N_SAMPLES))).T
return theta, np.cov(x, rowvar=False, bias=True)
IU = np.triu_indices(P, 1)
def admm(S, penalty, r=4.0, theta=None, tol=1e-7, max_iter=5000):
"""ADMM for min -log det Theta + tr(S Theta) + penalty(upper triangle);
penalty is an elementwise fastprox operator on the packed upper triangle."""
barrier = fp.LogBarrier(1.0)
Z = np.eye(P) if theta is None else theta.copy()
U = np.zeros((P, P))
for it in range(max_iter):
d, Q = np.linalg.eigh(Z - U - S / r)
Theta = (Q * barrier.prox(d, 1.0 / r)) @ Q.T
Zold = Z
V = Theta + U
Z = V.copy()
Z[IU] = penalty.prox(V[IU], 1.0 / r)
Z.T[IU] = Z[IU]
U += Theta - Z
primal = np.linalg.norm(Theta - Z)
dual = r * np.linalg.norm(Z - Zold)
if max(primal, dual) <= tol * max(1.0, np.linalg.norm(Z)):
break
return Z, it + 1
def kkt_residual(S, theta, lam, w):
"""Largest violation of S - Theta^{-1} + G = 0 with G_ii = 0 and
G_ij in lam w_ij d|Theta_ij| for i != j, the optimality conditions of
the weighted graphical lasso."""
R = S - np.linalg.inv(theta)
g, t, lw = -R[IU], theta[IU], lam * w
viol = np.where(t != 0, np.abs(g - lw * np.sign(t)), np.maximum(np.abs(g) - lw, 0.0))
return max(np.abs(np.diag(R)).max(), viol.max())
def report(name, theta, theta0, iters):
found, true = theta[IU] != 0, theta0[IU] != 0
err = np.linalg.norm(theta - theta0) / np.linalg.norm(theta0)
extra, missed = int(np.sum(found & ~true)), int(np.sum(~found & true))
print(f"{name:28s} {iters:6d} {extra:6d} {missed:7d} {err:9.3f}")
return extra, missed, err
def main():
rng = np.random.default_rng(4)
theta0, S = make_problem(rng)
m = IU[0].size
print(f"{P} variables, {np.sum(theta0[IU] != 0)} edges of {m}, {N_SAMPLES} samples")
print(f"{'estimator':28s} {'iters':>6s} {'extra':>6s} {'missed':>7s} {'rel. err':>9s}")
res, kkt = {}, {}
# The graphical lasso keeps the true edges only at a lam that also keeps
# spurious ones; a larger lam drops true edges and shrinks the rest more.
glasso = {}
for lam in (0.2, 0.25):
glasso[lam], it = admm(S, fp.Soft(lam))
res[f"glasso {lam}"] = report(f"graphical lasso, lam {lam}", glasso[lam], theta0, it)
kkt[f"glasso {lam}"] = kkt_residual(S, glasso[lam], lam, np.ones(m))
# Adaptive weights from the first estimate (lam 0.2): 1 where it found
# no edge, small where it found a strong one; a bounded variant of the
# weights 1/|theta_ij| of Fan, Feng and Wu (Ann. Appl. Stat. 3(2), 2009,
# 521-541).
first = glasso[0.2]
eps = 0.1
w = eps / (np.abs(first[IU]) + eps)
lam = 0.3
adaptive, it = admm(S, fp.Soft(lam, w), theta=first)
res["adaptive"] = report(f"adaptive lasso, lam {lam}", adaptive, theta0, it)
kkt["adaptive"] = kkt_residual(S, adaptive, lam, w)
# Weighted MCP with the same weights: threshold lam w_ij and no penalty
# beyond b lam, so the edges it keeps are not shrunk. Its prox at the
# step 1/r needs b > max(w) / r.
b = 2.0
mcp, it = admm(S, fp.MCP(lam, b, w), theta=adaptive)
res["mcp"] = report(f"weighted MCP, lam {lam}, b {b}", mcp, theta0, it)
print("KKT residual of the convex solves: "
+ ", ".join(f"{k} {v:.1e}" for k, v in kkt.items()))
res["kkt"] = kkt
return res
if __name__ == "__main__":
main()
autodiff_frameworks.py¶
The operators in PyTorch and JAX (0.3): one TV weight per edge as an nn.Parameter trained by Adam, and γ of isotropic TV learned with jax.jit(jax.value_and_grad(...)) (needs --group interop)
On GitHub · uv run python examples/autodiff_frameworks.py
Source
"""The operators inside PyTorch and JAX programs (0.3).
``fastprox.torch.prox`` and ``fastprox.jax.prox`` make any operator a
differentiable function of its input, its step and its parameters, with the
gradients from the library's VJP (no unrolled iterations). Two small
learning problems:
1. PyTorch: one TV weight per edge for denoising piecewise-constant signals
(the setting of bilevel_learning.py), as an ``nn.Parameter`` trained by
Adam on minibatches; w = softplus(theta) keeps the weights positive.
2. JAX: the step gamma of isotropic TV for denoising images, by gradient
descent on log(gamma) with ``jax.jit(jax.value_and_grad(...))``.
Needs PyTorch and JAX (``uv run --group interop python
examples/autodiff_frameworks.py``); without them it says so and stops.
"""
import numpy as np
import fastprox as fp
N, JUMPS = 120, [30, 55, 90]
def signals(rng, m, sigma=0.3):
edges = [0, *JUMPS, N]
levels = rng.normal(size=(m, len(edges) - 1))
x = np.concatenate([np.repeat(levels[:, [k]], edges[k + 1] - edges[k], 1) for k in range(len(edges) - 1)], 1)
return x, x + sigma * rng.normal(size=x.shape)
def torch_part(rng):
import torch
import fastprox.torch as fpt
x_train, y_train = (torch.tensor(a) for a in signals(rng, 512))
x_test, y_test = (torch.tensor(a) for a in signals(rng, 512))
theta = torch.nn.Parameter(torch.full((N - 1,), -1.0, dtype=torch.float64))
opt = torch.optim.Adam([theta], lr=0.05)
def loss(x, y):
z = fpt.prox(fp.TV1D, y, 1.0, weights=torch.nn.functional.softplus(theta))
return 0.5 * ((z - x) ** 2).sum(1).mean()
with torch.no_grad():
before = loss(x_test, y_test).item()
for step in range(200):
idx = torch.randint(0, 512, (64,), generator=torch.Generator().manual_seed(step))
opt.zero_grad()
loss(x_train[idx], y_train[idx]).backward()
opt.step()
with torch.no_grad():
after = loss(x_test, y_test).item()
w = torch.nn.functional.softplus(theta).detach().numpy()
found = sorted(int(i) + 1 for i in np.argsort(w)[:len(JUMPS)])
print(f"PyTorch: test loss {before:.4f} -> {after:.4f}; lowest weights at {found} (jumps at {JUMPS})")
return before, after, found
def jax_part(rng):
import jax
import jax.numpy as jnp
import fastprox.jax as fpj
h = 48
a, b = np.mgrid[0:h, 0:h] / h
clean = ((a - 0.5) ** 2 + (b - 0.45) ** 2 < 0.08) + 0.5 * (b > 0.7)
x = jnp.asarray(np.stack([clean, clean.T]))
y = x + 0.2 * jnp.asarray(rng.normal(size=x.shape), jnp.float32)
x = x.astype(jnp.float32)
@jax.jit
def loss_and_grad(t):
f = lambda t: 0.5 * jnp.sum((fpj.prox(fp.TVIso(), y, jnp.exp(t), tol=1e-8, max_iter=10 ** 5) - x) ** 2)
return jax.value_and_grad(f)(t)
t = jnp.log(0.02).astype(jnp.float32)
first, _ = loss_and_grad(t)
for _ in range(60):
val, g = loss_and_grad(t)
t = t - 5e-3 * g
gamma = float(jnp.exp(t))
grid = np.geomspace(gamma / 2, gamma * 2, 21)
best = grid[np.argmin([float(0.5 * jnp.sum((fp.TVIso().prox(np.asarray(y), g, tol=1e-7,
max_iter=10 ** 5) - x) ** 2))
for g in grid])]
print(f"JAX: loss {float(first):.2f} -> {float(val):.2f}; gamma {gamma:.4f} (grid search {best:.4f})")
return gamma, best
def main():
try:
import jax # noqa: F401
import torch # noqa: F401
except ImportError:
print("PyTorch and JAX are not installed: uv run --group interop python examples/autodiff_frameworks.py")
return None
rng = np.random.default_rng(0)
return torch_part(rng), jax_part(rng)
if __name__ == "__main__":
main()
deepinv_tv.py¶
fastprox.torch.tv_iso/tv_aniso in place of DeepInverse's TVDenoiser/TVL1Denoiser (0.3): the same results, warm starts in an inpainting loop, gradients in the image and a per-sample step (needs --group interop --with deepinv; about 6 s)
On GitHub · uv run python examples/deepinv_tv.py
Source
"""fastprox's device TV in place of DeepInverse's TV denoisers (0.3).
DeepInverse's ``TVDenoiser`` and ``TVL1Denoiser`` compute the prox of
isotropic and anisotropic TV of batches (B, C, H, W) with the step ``ths``,
as ``fastprox.torch.tv_iso`` and ``tv_aniso`` do (docs/deepinv.md). This
script checks, on two noisy images with one step per sample:
1. that both give the same image when run to convergence;
2. warm starts inside an iterative algorithm (proximal gradient for
inpainting): DeepInverse keeps its last iterates in the denoiser and
stops on the relative change of x, fastprox takes the dual of the
previous call and stops on the duality gap. Against the same loop with
exact proxes, DeepInverse's defaults end a few hundredths away (the
relative-change test stops early from a warm start), fastprox at
tol = 1e-6 about 1e-3;
3. gradients in the image and in the per-sample step, which fastprox
computes by implicit differentiation instead of through the iterations.
Needs PyTorch and DeepInverse (``uv run --group interop --with deepinv python
examples/deepinv_tv.py``); without them it says so and stops.
"""
import numpy as np
import fastprox as fp
def images(rng, n=32, b=2):
a, c = np.mgrid[0:n, 0:n] / n
clean = ((a - 0.5) ** 2 + (c - 0.45) ** 2 < 0.08) + 0.5 * (c > 0.7)
return np.stack([clean + 0.1 * rng.normal(size=(n, n)) for _ in range(b)])[:, None]
def main():
try:
import torch
from deepinv.models import TVDenoiser, TVL1Denoiser
except ImportError:
print("PyTorch and DeepInverse are not installed: "
"uv run --group interop --with deepinv python examples/deepinv_tv.py")
return None
import fastprox.torch as fpt
rng = np.random.default_rng(0)
y = torch.tensor(images(rng)) # (B, C, H, W), float64
ths = torch.tensor([0.05, 0.1], dtype=y.dtype) # one step per sample
# 1. The same problems.
diffs = {}
for name, den, tv in (("TVDenoiser / tv_iso", TVDenoiser, fpt.tv_iso),
("TVL1Denoiser / tv_aniso", TVL1Denoiser, fpt.tv_aniso)):
zd = den(n_it_max=5000, crit=1e-10)(y, ths)
z = tv(y, ths[:, None], tol=1e-10, max_iter=10 ** 6) # ths broadcasts to the batch shape (B, C)
diffs[name] = float((z - zd).abs().max())
print(f"{name:24s} max difference {diffs[name]:.1e}")
# 2. Warm starts in proximal gradient for inpainting, x <- prox(x - (M x - b)),
# against the same loop with exact proxes (the C kernel, image by image).
mask = torch.tensor(rng.uniform(size=y.shape) < 0.5)
b = torch.where(mask, y, 0.0)
step = lambda x: x - torch.where(mask, x - b, 0.0)
den = TVDenoiser() # defaults; keeps x2, u2 between calls
exact = fp.TVIso()
x_e, x_d, x_f, dual_e, dual, iters = b.clone(), b.clone(), b.clone(), [None, None], None, []
for _ in range(30):
v = step(x_e).numpy()
for i in range(2):
z, inf = exact.solve(v[i, 0], float(ths[i]), tol=1e-12, max_iter=10 ** 6, warm_start=dual_e[i])
x_e[i, 0], dual_e[i] = torch.from_numpy(z), inf.dual
x_d = den(step(x_d), ths)
x_f, info = fpt.tv_iso(step(x_f), ths[:, None], tol=1e-6, warm_start=dual, return_info=True)
dual = info.dual # (2, B, C, H, W): the next call's start
iters.append(info.iters)
err_d, err_f = float((x_d - x_e).abs().max()), float((x_f - x_e).abs().max())
print(f"inpainting, 30 steps, distance to exact proxes: DeepInverse {err_d:.1e}, fastprox {err_f:.1e} "
f"({iters[0]} iterations in the first prox, {iters[-1]} in the last)")
# 3. Gradients of <prox(y), c> in y and in the per-sample step.
c = torch.tensor(rng.normal(size=y.shape))
grads = {}
for name, f in (("fastprox", lambda yy, g: fpt.tv_iso(yy, g[:, None], tol=1e-12, max_iter=10 ** 6)),
("DeepInverse", lambda yy, g: TVDenoiser(n_it_max=1500, crit=0.0)(yy, g))):
yy, g = y.clone().requires_grad_(), ths.clone().requires_grad_()
gy, gg = torch.autograd.grad((f(yy, g) * c).sum(), (yy, g))
grads[name] = (gy, gg)
(gy, gg), (gy_d, gg_d) = grads["fastprox"], grads["DeepInverse"]
rel = float((gy - gy_d).norm() / gy_d.norm())
print(f"gradients: in y, relative difference {rel:.1e}; in ths, fastprox {gg.tolist()} "
f"against unrolled {gg_d.tolist()}")
return diffs, (err_d, err_f), rel, (gg, gg_d)
if __name__ == "__main__":
main()
pyproximal_tv.py¶
fastprox operators in PyProximal's solvers (since 0.5): isotropic TV deblurring by accelerated proximal gradient, with ProxOp(fp.TVIso(), dims, warm=True) against pyproximal.TV (needs --group interop)
On GitHub · uv run python examples/pyproximal_tv.py
Source
"""fastprox operators inside PyProximal's solvers (since 0.5).
``fastprox.pyproximal.ProxOp`` makes any operator a ``pyproximal.ProxOperator``.
Here isotropic TV deblurs an image with PyProximal's accelerated proximal
gradient:
min_x 1/2 ||H x - b||^2 + lam TV(x),
H a Gaussian blur (PyLops), b the blurred image plus noise. The TV prox is
fastprox's, stopped on its duality gap and warm-started from one iteration
to the next; the same solve with PyProximal's own ``TV`` (a fixed number of
inner iterations) is shown for comparison.
Needs PyProximal (``uv run --group interop python examples/pyproximal_tv.py``);
without it the script says so and stops.
"""
import time
import numpy as np
import fastprox as fp
H, W, LAM, ITERS = 64, 64, 0.02, 100
def image():
a, b = np.mgrid[0:H, 0:W] / H
x = np.where((a - 0.4) ** 2 + (b - 0.5) ** 2 < 0.06, 1.0, 0.2)
return np.where((np.abs(a - 0.75) < 0.12) & (np.abs(b - 0.3) < 0.2), 0.6, x)
def psnr(x, ref):
return 10 * np.log10(np.ptp(ref) ** 2 / np.mean((x - ref) ** 2))
def main():
import pylops
import pyproximal
from fastprox.pyproximal import ProxOp
rng = np.random.default_rng(0)
clean = image()
t = np.arange(-4, 5)
k = np.exp(-(t[:, None] ** 2 + t[None, :] ** 2) / (2 * 1.5 ** 2))
blur = pylops.signalprocessing.Convolve2D((H, W), h=k / k.sum(), offset=(4, 4))
b = blur @ clean.ravel() + 0.01 * rng.normal(size=H * W)
f = pyproximal.L2(Op=blur, b=b)
tau = 0.95 # the blur has norm at most 1, so 1/L >= 1
def solve(g):
t0 = time.perf_counter()
x = pyproximal.optimization.primal.ProximalGradient(
f, g, np.zeros(H * W), tau=tau, epsg=LAM, niter=ITERS, acceleration="fista")
return x.reshape(H, W), time.perf_counter() - t0
x_fp, t_fp = solve(ProxOp(fp.TVIso(), dims=(H, W), tol=1e-6, warm=True))
x_pp, t_pp = solve(pyproximal.TV(dims=(H, W), sigma=1.0, niter=20))
blurred = b.reshape(H, W)
print(f"blurred and noisy PSNR {psnr(blurred, clean):5.1f} dB")
print(f"TV, fastprox ProxOp PSNR {psnr(x_fp, clean):5.1f} dB {t_fp:.2f} s")
print(f"TV, pyproximal.TV PSNR {psnr(x_pp, clean):5.1f} dB {t_pp:.2f} s")
return psnr(blurred, clean), psnr(x_fp, clean), psnr(x_pp, clean)
if __name__ == "__main__":
try:
import pyproximal # noqa: F401
except ImportError:
print("Needs PyProximal: uv run --group interop python examples/pyproximal_tv.py")
else:
main()
reweighted_tv.py¶
Nonconvex TV^q denoising by iteratively reweighted ℓ1 (Ochs et al. 2015; 0.3): each step a TVIso prox with pixel weights, warm-started from the last dual, decreasing the objective to a stationary point, 6 dB above TV
On GitHub · uv run python examples/reweighted_tv.py
Source
"""Nonconvex TV^q denoising by iteratively reweighted l1 (0.3).
minimise 1/2 |z - y|^2 + gamma sum_p (|(D z)_p| + eps)^q, 0 < q < 1,
by the iteratively reweighted l1 method of P. Ochs, A. Dosovitskiy, T. Brox
and T. Pock, "On iteratively reweighted algorithms for nonsmooth nonconvex
optimization in computer vision", SIAM J. Imaging Sci. 8 (2015) 331-372:
t -> (t + eps)^q is concave, so its tangent at the current |(D z_k)_p|
majorises it, and each step is a weighted isotropic TV prox,
z_{k+1} = prox of gamma sum_p alpha_p |(D z)_p|,
alpha_p = q (|(D z_k)_p| + eps)^(q - 1),
which ``fp.TVIso(pixel_weights=alpha)`` computes, warm-started from the
previous dual (projected onto the new balls). The objective decreases at
every step, and the iterates settle at a stationary point: a fixed point of
the step. Small jumps get large weights and are flattened, large ones small
weights and keep their height, so TV^q loses less contrast than TV: on the
64^2 test image (three flat regions plus noise 0.1), 42.6 dB against 36.7 dB
for TV, each at its best step, after 40 steps of a relative size 3e-8.
"""
import numpy as np
import fastprox as fp
Q, EPS = 0.5, 1e-2
def images(rng, n=64):
a, b = np.mgrid[0:n, 0:n] / n
clean = ((a - 0.5) ** 2 + (b - 0.45) ** 2 < 0.08) + 0.5 * (b > 0.7) - 0.4 * ((a < 0.25) & (b < 0.3))
return clean, clean + 0.1 * rng.normal(size=clean.shape)
def grad_norm(z):
g0 = np.zeros_like(z)
g1 = np.zeros_like(z)
g0[:-1] = z[1:] - z[:-1]
g1[:, :-1] = z[:, 1:] - z[:, :-1]
return np.hypot(g0, g1)
def objective(z, y, gamma):
return 0.5 * ((z - y) ** 2).sum() + gamma * ((grad_norm(z) + EPS) ** Q).sum()
def psnr(z, clean):
return 10 * np.log10(np.ptp(clean) ** 2 / np.mean((z - clean) ** 2))
def reweighted(y, gamma, iters=40):
"""IRL1 from the TV solution; returns z, the objectives and the last step size."""
z = fp.TVIso(2).prox(y, gamma, tol=1e-8, max_iter=10 ** 5)
dual, objs, step = None, [objective(z, y, gamma)], np.inf
for _ in range(iters):
alpha = Q * (grad_norm(z) + EPS) ** (Q - 1)
zn, info = fp.TVIso(2, pixel_weights=alpha).solve(y, gamma, tol=1e-10, max_iter=10 ** 5, warm_start=dual)
dual = info.dual
step = np.linalg.norm(zn - z) / np.linalg.norm(z)
z = zn
objs.append(objective(z, y, gamma))
return z, np.array(objs), step
def main():
rng = np.random.default_rng(0)
clean, y = images(rng)
# Each method at its best step on a small grid (an oracle, for comparison).
tv = max(((psnr(fp.TVIso(2).prox(y, g, tol=1e-8, max_iter=10 ** 5), clean), g) for g in (0.06, 0.08, 0.1, 0.12, 0.15)))
runs = [(reweighted(y, g), g) for g in (0.05, 0.08, 0.12)]
(z, objs, step), g = max(runs, key=lambda r: psnr(r[0][0], clean))
rise = float(np.max(np.diff(objs) / np.abs(objs[1:])))
print(f"TV: PSNR {tv[0]:.2f} dB (gamma {tv[1]})")
print(f"TV^q: PSNR {psnr(z, clean):.2f} dB (q = {Q}, gamma {g}); objective {objs[0]:.3f} -> {objs[-1]:.3f}, "
f"largest relative rise {max(rise, 0.0):.1e}, last step |z_k+1 - z_k| / |z_k| = {step:.1e}")
return tv[0], psnr(z, clean), objs, step
if __name__ == "__main__":
main()
sparse_recovery.py¶
Proximal gradient with ℓ1 against MCP, SCAD, ℓ0, ℓ1/2 and the log penalty (0.2) on a batch of sparse recovery problems, and the tie rule
On GitHub · uv run python examples/sparse_recovery.py
Source
"""Recover sparse signals with convex and nonconvex penalties (since 0.2).
Each of 64 problems observes b = A x0 + noise with A of size 80 x 256 and a
16-sparse x0, and solves
min_x ||A x - b||^2 / 2 + g(x)
by proximal gradient, x <- prox_{t g}(x - t A^T (A x - b)) with t = 1/||A||^2.
The l1 norm keeps every true entry but shrinks each amplitude by lam; at a
lam small enough to limit that bias it also keeps many spurious entries.
The nonconvex penalties
(MCP, SCAD, l0, lq, log) stop shrinking large entries and get close to the
oracle that knows the support. They are not convex, so proximal gradient
finds a stationary point; starting from the l1 solution, as is common, gives
a good one. All 64 problems run as one batch: the maps are elementwise.
uv run python examples/sparse_recovery.py
"""
import numpy as np
import fastprox as fp
M, N, K, TRIALS = 80, 256, 16, 64
def make_problems(rng):
A = rng.normal(size=(M, N)) / np.sqrt(M)
x0 = np.zeros((TRIALS, N))
for row in x0:
idx = rng.choice(N, K, replace=False)
row[idx] = rng.choice([-1, 1], K) * rng.uniform(1, 3, K)
b = x0 @ A.T + 0.05 * rng.normal(size=(TRIALS, M))
return A, x0, b
def proximal_gradient(op, A, b, x, iters=500):
t = 1.0 / np.linalg.norm(A, 2) ** 2
for _ in range(iters):
x = op.prox(x - t * ((x @ A.T - b) @ A), t)
return x
def report(name, x, x0):
found, true = x != 0, x0 != 0
exact = np.mean(np.all(found == true, axis=1))
err = np.median(np.linalg.norm(x - x0, axis=1) / np.linalg.norm(x0, axis=1))
extra = np.mean(np.sum(found & ~true, axis=1))
missed = np.mean(np.sum(~found & true, axis=1))
print(f"{name:22s} {exact:6.0%} {err:9.3f} {extra:6.1f} {missed:6.1f}")
return exact, err
def main():
rng = np.random.default_rng(0)
A, x0, b = make_problems(rng)
# Weights chosen per penalty from a small grid; each has its own scale.
print(f"{'penalty':22s} {'exact':>6s} {'rel. err':>9s} {'extra':>6s} {'missed':>6s}")
x1 = proximal_gradient(fp.Soft(0.1), A, b, np.zeros_like(x0))
results = {"l1": report("l1, lam 0.1", x1, x0)}
for name, op in (("MCP, lam 0.2, b 3", fp.MCP(0.2, b=3.0)),
("SCAD, lam 0.2, a 3.7", fp.SCAD(0.2, a=3.7)),
("l0, lam 0.15", fp.L0(0.15)),
("l1/2, lam 0.1", fp.Lq(0.1, q=0.5)),
("log, lam 0.1, eps 0.1", fp.LogPenalty(0.1, eps=0.1))):
results[name.split(",")[0]] = report(name, proximal_gradient(op, A, b, x1), x0)
# The oracle: least squares on the true support of each problem.
oracle = np.zeros_like(x0)
for xo, xt, bt in zip(oracle, x0, b):
s = xt != 0
xo[s] = np.linalg.lstsq(A[:, s], bt, rcond=None)[0]
report("oracle (known support)", oracle, x0)
# Where the prox is set-valued, tie= picks the minimiser and ctx.info.ties
# counts the entries that sat on the tie. Hard thresholding with lam = 1/2
# and step 1 keeps |x| > 1, zeroes |x| < 1, and |x| = 1 is a tie.
v = np.array([2.0, 1.0, -1.0, 0.5, -3.0])
for tie in ("nonzero", "zero"):
z, ctx = fp.L0(0.5).prox(v, 1.0, keep=True, tie=tie)
print(f"hard threshold of {v}, tie={tie!r:9s}: {z}, {ctx.info.ties} ties")
return results
if __name__ == "__main__":
main()