Changelog¶
All notable changes to fastprox. Planned work is in ROADMAP.md. The format follows Keep a Changelog.
[Unreleased]¶
[1.0.1] — 2026-10-25¶
A patch release with the fixes from the two mathematical audits of 2026-10-25 (M1–M7, docs/math-audit-2026-10.md), the documentation of what the derivatives are and guarantee (C1–C6), and eight defects at extreme scales found by the fuzz harness, which now draws parameters from every binade. It adds no C function and changes no signature, so the ABI is 1.0.0's. Three calls now return errors where they gave wrong results: fp_prox_conj of weighted isotonic regression with unequal weights (FP_EINVAL), and group Huber, SCAD and MCP steps beyond γ · max(λ, 1) · max c ≤ 2^960 (FP_EPARAM; they gave NaN). Some results change in the last ulp (SCAD, MCP, and where the new bounds apply).
Added¶
- Two audits of 1.0.0's mathematics,
docs/mathematical-audit-2026-10-25.mdanddocs/theoretical-audit-2026-10-25.md, with errata from checking their claims against the cited literature. Their reproduction scripts are underreports/. The specs for 1.0.1 that address them are indocs/math-audit-2026-10.md.
Changed¶
- The conda recipe's
libfastproxexports a pin on the major version (upper_bound='x'), instead of the minor, as the ABI now holds for every 1.x. docs/api.md, "Conjugates": at large σ the conjugate of a non-homogeneous operator can itself exceed the range (about −σr/n for the simplex of radius r), and is then ±inf; nothing bounds σ, so the call succeeds. The fuzz harness now accepts ±inf there, but not NaN, as it does for float32 (found by a fuzz run, 2026-10-24: r = 1.1e45 at σ = 9.7e272).- What the derivatives are and guarantee (math audit C1–C6). The prox maps are split into Lipschitz ones (convex operators; SCAD, MCP and the log penalty below its critical step), the Hölder-½ log penalty at γλ = ε², and the discontinuous ℓ0, ℓq and log penalty above it. Clarke and B-subdifferential claims are limited to the first class, and the others' derivative at a jump is named as a branch convention. A new section of the API docs, "What the derivatives guarantee", gives the guarantees once composed (chain rules off switching sets, Clarke 2.6.6 for a C¹ loss on the output, the caller's regularity for implicit differentiation of a lower problem) with a counterexample. Only SCAD, MCP and ℓ0 are called bounded, and nonexistence of a minimiser is stated as observed, not proved. The conjugate of a nonconvex penalty is named the Moreau residual (their g* is the indicator of {0}), in the README too.
ctx.deriv.exactandrefinedescribe certified regions, not a bound in the gap. Graph TV's kink mask is described as edges biactive in the saved flow, a superset of the prox's kinks on graphs with cycles. The outer-method statements give their hypotheses (a minimiser, bounded iterates, the KL property, steps strictly below 2/L or 1/L) and say "sufficient", each checked in its source, with aztolschedule, ηₖ / max(1, ‖vₖ‖), that needs no bounded iterates.
Fixed¶
- Found by the 1.0.1 fuzz run, whose harness now draws parameters from every binade, with steps their reciprocal, and checks invariants at any scale (shrinkage maps keep |zᵢ| ≤ |xᵢ| with x's sign, the log barrier stays in its domain, and norm-like proxes keep ‖z‖ ≤ ‖x‖):
- Soft thresholding, ℓ1 over a box and group ℓ2 formed γλw as (γλ)w. With every weight 0, where the step range does not apply, γλ overflowed and inf · 0 gave NaN for the identity; with γλ = 2^1100 and w = 2^-200 the threshold 2^900 came out infinite. They use M3's product, unchanged bit for bit wherever γλ is normal.
- The log penalty's root rounded an ulp above |x| where λ ≪ |x|ε, so the prox moved an entry away from 0. It is now taken as at most |x|.
- 1D TV with ℓ2 of differences returned −inf for a row with an entry near 9e307 among small ones (the piece mean's sum of offsets overflowed), and the piecewise mean at γ = 3.6e-97 for a row with an entry of 1e308 (γ times the row's scale underflowed), where z = x to rounding.
- Found by the hour-long fuzz run (6 workers, nearly 300 million inputs):
- Tree TV gave wrong values where γw_e is far above the data: γw = 8e34 on entries of 100 gave z ≈ 1.7e34, and near 2^960 the sums of capacities overflowed. The clip points were differences of numbers of size γw_e, so a child came out an ulp apart from its parent, and the region means took γw_e as a boundary flow. Capacities are now capped at 2n(max x − min x). That is above any flow, so the prox is unchanged.
- Group Huber at λ < 1 could form an infinite inner step γc_g inside its step range (a NaN group at λ = 1e-280). The step range of group Huber, SCAD and MCP is now γ · max(λ, 1) · max c ≤ 2^960, the same rule as before for λ ≥ 1. Steps between the two bounds, which gave NaN, now return
FP_EPARAM. - The hyperplane and half-space projections with a box returned NaN and ±inf when some aᵢ is far below max |aᵢ|: the breakpoints (xᵢ − bound)/aᵢ overflowed, for example aᵢ = 6.6e-76 of the normalised a at |x| = 2e239. The scale now counts min |aᵢ| too, and is unchanged when the aᵢ are of one size.
- MCP's linear piece, and defensively SCAD's (no SCAD case failed in the run), rounded an ulp above |x| near its end. These pieces now return at most |x|.
- The certified error
zerr(IterInfo.zerr,fp_workspace_image_info) left out the rounding of the returned array to its dtype (math audit M7): TV of (0, 1) in float32 at γ = 0.1 reported gap 0 and zerr 0 for an array 2.4e-8 from (0.1, 0.9). It now adds u(1 + r), with u the dtype's unit roundoff and r = √(2 gap)/‖x‖ (2u(1 + r) after a conjugate, plus the absolute rounding of outputs below the normal range), in C and in the PyTorch and JAX device solves. A positiveztolbelow u raisesAccuracyWarning, and the docs state that the bound holds to working precision and that an exact operator's gap of 0 is not a computed certificate. The stopping test is unchanged, so a converged call has zerr ≤ ztol + u(1 + ztol). - ℓ0 and ℓq formed γλw as (γλ)w, whose first product could overflow or underflow where the scaled penalty is in range (math audit M3):
L0(1e-308).prox([2.0], 1e308)returned 0, where 2 is the global minimiser, with gap 0. The products are now rounded as written from the factors' mantissas in that case, so prox(x; γ2^k, λ2^j, w2^-(k+j)) equals prox(x; γ, λ, w) bit for bit. - The log barrier returned 0, outside its domain, for x = −1e308 at γλ = 1e280, where the answer is 1e-28 (math audit M4): r − x overflowed before the halving. The halves come first, γλ is taken through √γ√λ where it underflows, and an answer below the dtype's smallest positive value returns that value instead of 0.
- 1D TV with ℓ2 of differences stored the squared weights, and a weight whose square underflowed dropped its edge (math audit M5):
TV1DL2(1e-180).prox([1, -1], 1e180)returned the input, where the solution is 0. The weights are now stored over the power of two of the largest, with the step scaled by it, so weights such as 1e200, rejected before, are accepted. A positive weight below 2^-511 times the largest is nowFP_EPARAM(ValueError). The JVP's linear solve runs on its right-hand side over a power of two, so a large one cannot overflow inside it. - SCAD and MCP, and their group forms, returned inf at a = b = 1e308, where the answer is 2 (math audit M6): their middle pieces multiplied x by a or b before dividing. The values and every derivative are now bounded ratios; results at ordinary parameters can differ by an ulp.
- The derivatives of the spectral operators (
fp_spectral_jvp,Spectral.jvpandvjp) were wrong for two close but distinct values with a breakpoint of the scalar map between them (math audit M1). For the nuclear norm at diag(1 + d, 1 − 2d), the coefficient on a symmetric off-diagonal direction is 1/3, and the average of the two pieces' slopes, 1/2, was returned, withctx.deriv.exactTrue, in float64 at d = 1e-7 and in float32 at diag(1.001, 0.998). Within the band of near ties the average is now used only where it agrees with the divided difference within that quotient's rounding bound, and the quotient otherwise. -
fp_prox_conjof weighted isotonic regression returned y − P(y) with P the weighted projection, which is not the prox of the Euclidean conjugate (math audit M2: weights (1, 3) at y = (2, 0) gave (1.5, −0.5), outside the polar cone, where the answer is (1, −1)). With unequal weights the call now returnsFP_EINVAL, and Python'sprox_conjraisesValueError, also throughfastprox.torch,fastprox.jaxand PyProximal. Equal weights keep the conjugate. -
The 1D TV ball (
fp_op_tv1d_ball,TV1DBall) returned NaN on rows with entries beyond about 5e305, from any finite input (found by the nightly fuzz run, 2026-10-24: the conjugate at sigma = 1.8e-306 projects y / sigma). The piece sums in the projection overflowed. A row with max |x| outside [2^-960, 2^960] is now projected at x 2^-k onto the ball of radius alpha 2^-k, and the result scaled back by 2^k. The projection is homogeneous, so this is exact up to rounding, and the derivatives are unchanged. Rows inside the ball still come back exactly. Tested intests/python/test_tree_ball.py, at the fuzz case and at 2^±1000. - Graph TV, tree TV and isotropic image TV returned inf on tiny images whose weights are all below 1 (found by the nightly fuzz run, 2026-10-24, while checking the fix above). The scale-up of a tiny image was bounded by
gammatimes the largest weight, butgammais scaled by the same factor: one tree edge of weight 2.7e-315, on an image of 5e-312 atgamma= 1.9, allowed a scale-up of 2^1034, wheregammaoverflowed to inf. The scale-up is now bounded by the larger ofgammaandgammatimes the largest weight. Anisotropic TV was not affected; for it the scale-up may now stop sooner, which changes results only by rounding. Tested intests/python/test_tv_scaling.py, against the same problems at unit scale. - Isotonic regression returned NaN with weights whose largest is below 2^-1023 (found by a fuzz run, 2026-10-25: weights 5.5e-318 and 1e-315). The weights are stored over their largest power of two, 2^k, and the factor 2^-k overflowed to inf. k is now kept as an exponent and applied with
ldexp. Results are unchanged for other weights. Tested intest_isotonic_extremes: the fuzz case, and weights at 2^-1050 against the same weights at unit scale, bit for bit.
[1.0.0] — 2026-10-24¶
The first stable release, on PyPI (pip install fastprox). The C ABI (FP_ABI_VERSION 1, libfastprox.so.1) now holds for every 1.x: later releases may add functions, but nothing changes or goes (docs/api.md, "ABI stability"). The abi job checks every change against 0.5.0 now, and against 1.0.0 from here on. This release changes no code since 1.0.0rc3. It closes the last feedback item (U6) and moves the PyPI classifier to Production/Stable. For what changed since 0.5, see the three release candidates below.
Changed¶
- Spectral MCP's divergence explained (feedback U6). The report's case, matrix completion of MovieLens ratings, has no minimiser: MCP is bounded and the data term sees only the observed entries, so the iterates of FISTA and of proximal gradient grow without bound while the objective falls. The library is not at fault;
bench/repro_u6_spectral_mcp.pyreproduces it, and docs/api.md says when a minimiser may not exist. The prox, the derivatives at ties and at kinks, and an outer proximal gradient loop were checked too. Two more causes make outer methods fail, now documented in "Inexact proxes inside outer solvers": a step at or above 1/L, which a nonconvex penalty does not tolerate in proximal gradient and FISTA does not tolerate with any penalty; and MCP's derivative b/(b − γ) on its middle piece, unbounded as b falls to γ, with SCAD's counterpart. "Spectral operators" says which derivative the JVP gives at a kink, and at a tie split across one by rounding.tests/python/test_spectral.pygains spectral MCP at ties, MCP and SCAD at every kink alone and tied, the gain, and a monotone proximal gradient run.
[1.0.0rc3] — 2026-10-24¶
The third release candidate for 1.0, from master, on PyPI as a pre-release (pip install --pre fastprox). It completes the user feedback of 2026-10-23 that changes the Python API (U3–U5: derivative keywords on every operator, DerivInfo and refined derivatives at loose tolerances, the sorted ℓ1 norm and the weighted nuclear norm) and carries the speed items of the audit of 2026-10-22: the kernels, the thread pool, the Python and framework wrappers, and image TV's derivatives and saved structure, which now use every thread on a single image. The new C functions join the 1.0 ABI, which the abi job checks against 0.5.0. 1.0.0 follows after some use of this candidate.
Added¶
FASTPROX_SPIN_US: the pool's spin time after a call, in microseconds (default 50, 0 to sleep at once), read once (audit C9). 1000 empty 15-thread jobs a millisecond apart burn 0.15–0.19 s of process CPU at 0, against about 0.9 s at the default../profile_kernels core [case]inbench/profile_kernels.cppprofiles the core: workspace bytes, elementwise throughput, derivatives, the pool's cold latency, the grain, strided rows and the spin (audit C11). CI builds it and runs itselemcase.- The sorted ℓ1 norm (OWL, SLOPE) and the weighted nuclear norm (feedback U5):
- The operator.
fp_op_sorted_l1(w)andfp.SortedL1(weights): \(g(z) = \sum_k w_k \lvert z \rvert_{(k)}\) with nonincreasing weights \(w \ge 0\). Its prox, by a sort and pool-adjacent-violators (Bogdan et al., 2015), costs O(n log n): 1.9× isotonic regression plus a NumPy sort on rows of 10⁴. With equal weights it is soft thresholding, bit for bit. Derivatives in x, the step and the weights average over the pooled blocks. - On matrices.
fp.WeightedNuclearNorm(w), i.e. \(\sum_k w_k \sigma_k(X)\), isSpectral(SortedL1(w)). Before, unequal weights were refused with no alternative; the refusal now points to these two. - Tests. Against cvxpy where blocks pool, the
CASESsuite, finite differences at ties of the singular values, and the fuzzer. - Derivatives of iterative TV at loose tolerances (feedback U4):
- Report.
ctx.derivis aDerivInfo(residual, iters, exact, smoothing).exactsays whether the derivative at the saved point is exact: anisotropic TV once its polish certified the regions, graph TV when no part was stopped bytol, tree TV and the closed-form operators always. Isotropic TV is exact only without smoothing, andsmoothingis its curvature cap μ, in the units of x. In C,fp_workspace_deriv_exact(ws, &exact, &smoothing). - A warning. A derivative that is not exact, at a certified error of z above 1e-4 (inside
inner_accuracy, above its ztol), raisesAccuracyWarningonce per point. Before, a loose solve gave a biased hypergradient without a sign: 3% for isotropic TV after a 1e-6 solve on 2 × 128² images. - Refining.
ctx.refine(ztol)andjvp/vjp(..., refine=ztol)solve the kept call again, from its saved input and its dual, to a tighter tolerance;ctx.refinereturns the refined z. In C,fp_workspace_refine(op, ws, tol, max_iter, out, info), which matches a fresh solve seeded with the kept dual bit for bit, for any thread count, without allocating. - Cost. A refine costs about what solving to the tighter tolerance from the start would have. From a 1e-6 solve on 2 × 128² images, anisotropic TV refines to 1e-12 in 34 iterations (66 fresh), and its derivative becomes exact. Isotropic TV refines to 1e-10 in 31 036 (32 432 fresh): its FISTA converges like 1/k², so the warm start saves little.
- One set of derivative keywords on every operator (feedback U3):
jvpandvjptaketolandmax_itereverywhere. They control isotropic TV's conjugate gradients, and every other operator, the spectral ones included, accepts and ignores them, since its derivatives are in closed form. Before, onlyTVIsotook them, so generic code had to special-case it.ctx.derivis set after every derivative:(0.0, 0)in closed form.fastprox.torch.proxandfastprox.jax.proxtakederiv_tolandderiv_max_iter, astv_isodoes, and pass them to every derivative call. A call with the default keywords costs 0.03–0.05 µs more than before. - CI builds and tests the aarch64 wheel on every pull request that touches the library, its tests or the build, as the release does. It is the wheel built by GCC for a CPU with FMA, where results depended on the thread count before
-ffp-contract=off; only the TestPyPI dry run for 1.0.0rc2 had found that (#105).
Changed¶
fastprox.jaxkeeps a jit of each wrapper function, on the operator or, for a class, keyed on its constant arguments, and of the device TV (audit P9). Called eagerly, the wrappers traced their callbacks on every call:fpj.prox(fp.Soft(0.4), x, 0.8)on 100 entries 1880 → 55 µs, itsjax.grad4387 → 497 µs,fpj.tv_isoon 32 × 32 68 → 0.7 ms. Under an outerjitnothing changes.- The PyTorch and JAX forwards keep the derivative structure only when a derivative can follow (audit P10): under
torch.no_grad(), for inputs without grad, and in every JAX forward callback, whose backward recomputes the prox.fpt.proxofL1Ballon 64 × 10⁴ underno_grad841 → 243 µs,Simplex381 → 179 µs; the jitted JAXSimplexforward 556 → 336 µs. - Less Python per call (audit P11):
Soft().prox(x, out=out)on 100 entries 1.08 → 0.71 µs,Softvjp 1.74 → 1.42 µs,fpt.prox(Soft)7.8 → 5.4 µs. The PyTorch and JAX backwards ask the library for the step's and the parameters' gradients only when an input needs them, which leaves elementwise maps on their gradient-only loop.bench/bench_python.pyhas the audit'storch_wrappers()andjax_wrappers()sections and three moreoverhead()lines. - Isotropic TV's jvp and vjp split one image over the threads (audit T2): on a 512² image at 15 threads, 278 → 76 ms at γ = 0.1 and 1006 → 275 ms at γ = 1; on 2048², 1071 → 234 ms. The conjugate gradients run their pixel passes by rows, sum over regions in fixed chunks of a region-ordered pixel list saved with the structure, and take their dot products over fixed blocks of regions. A batch runs one image at a time on all the threads when that is at least twice as wide as running its images in parallel; 4 × 256² goes 90 → 65–78 ms and 2 × 128² 13 → 11 ms. One thread is faster too: 278 → 217 ms and 987 → 634 ms. Results do not depend on the thread count. On images larger than 64² they differ from before within the solve's tolerance: 7e-14 relative at γ = 0.1, up to 4e-5 at γ = 1 with tol 1e-6, CG counts within 3. The saved structure grows by 8 bytes per entry.
- Isotropic TV's jvp and vjp are 1.5–1.6× faster (audit T3): on a 512² image, 395 → 262 ms at γ = 0.1 and 1503 → 919 ms at γ = 1, one thread. The gradient, its adjoint, the preconditioner and the saved structure tested each entry's neighbours with an integer division and a remainder per axis; they now test once per row. The results are bit-identical.
bench/bench_python.pyhas the audit'simage_tv_derivatives()section. Lqwith q other than 1/2 and 2/3 is 8–11× faster just above its threshold (audit K6): 543 → 48 ns per entry at q = 0.9 and 672 → 80 at q = 0.999, one thread. Newton stops when a step no longer decreases y, the rounding floor of h, which the relative test missed near the threshold; there the iterates oscillated up to the cap of 100. It starts from the tangent bound β + (x − τ)/(1 − q/2) below 2τ instead of from x. The jvp and vjp, which recompute the root, gain the same. Far from the threshold q = 0.9 is 2.5% slower (51.5 → 52.8 ns). Results change at rounding level.L2Ball's jvp and vjp make one pass for the norm and the dot, in eight lanes, and multiply by 1/m (audit K12): 1.16 → 0.36 and 1.14 → 0.38 ns per entry on one row of 10⁶. The prox shares the lane sum of squares: 0.82 → 0.42. Results change at rounding level.- Anisotropic TV builds the structure it keeps for jvp and vjp in parallel (audit T8):
- How. The edge tests run over fixed chunks of fibers, and the components and the boundary sums over slabs of the image along its first axis. The components that cross slabs are summed in a fixed order. The polish shares the components code.
- Speed. On the 2048² test image at γ = 0.1, tol 1e-4 and 15 threads,
keep=Trueadds 8.5 ms to the 77 ms solve instead of 101 ms. On a 64³ random walk it adds 1.1–1.3 ms instead of 8.2–8.4 (1.7 instead of 10.2–11.2 with edge weights). Images from 16² up are no slower. - The polish. It got faster too:
keep=Falsetakes 37 µs instead of 43–48 on a 16² image, and 12.2–12.4 ms instead of 13.1–14.0 on 256². - Results. Without edge weights the derivatives, kinks and branches give the same bits as before. With edge weights the boundary sums are added in another order, which changes results at rounding level (at most 2e-16 relative). Either way the bits do not depend on the thread count.
bench/bench_python.pyhas thekernel_throughput()section of the audit: row and elementwise kernels, one thread, ns per entry. It also hasaniso_keep()(audit B3): anisotropic TV with and without the saved structure.- The valgrind CI job builds at
-O1 -ginstead of-O0, installs valgrind from packages kept in the Actions cache (the Ubuntu mirror served them at 15–45 kB/s on some runs, 8–9 minutes), and runstest_corewithFASTPROX_TEST_LIGHT=1. That runs the tests sized for throughput and concurrency small and skips the fork stress, whose code paths ASan, TSan and the fuzzer cover at full size. The job takes about 4.5 minutes; before, it took 9–29, most of it-O0code under memcheck and the 256 × 1000 elementwise checks of audit C5. - Row operators along a strided axis gather and scatter their rows in tiles of up to 16 (audit C8). Rows are read b at a time, neighbouring elements together, rather than one cache line per element. 1D TV on a (256, 4096) C-order array along axis 0 took 8.9 ms instead of 13.8 ms (the same rows stored contiguously: 8.0 ms). The prox, the conjugate, jvp and vjp give the same bits as before. A row operator's workspace holds 64 KiB more per thread for the tiles.
- Elementwise prox loops run on by-value kernels (audit C4): soft thresholding, the elastic net, Huber, the box, the nonnegative orthant, the log barrier and ℓ1 over a box hand their per-call constants to the loop as plain values, so the compiler vectorises it, in place too. On 2^16 entries, one thread, Apple M5 Pro, in ns per entry (out of place / in place):
| Operator | Before | After |
|---|---|---|
| soft | 0.41–0.44 / 0.44 | 0.16 / 0.16 |
| elastic net | 0.19 / 0.60 | 0.19 / 0.20 |
| huber | 0.22 / 0.63 | 0.22 / 0.22 |
| box | 0.36 / 0.35 | 0.14 / 0.13 |
| nonneg | 0.09 / 0.23 | 0.10 / 0.12 |
The results are the same bits as before, every layout and dtype, checked against the previous library.
- Weighted operators no longer scan their weights on every call (found while measuring C4): the step-range check of audit A1 read step_scale(), which took the largest weight each time. The maximum is now formed once, at construction. This affects soft thresholding, L0, Lq, group and tree ℓ2, ℓ1 over a box, the ℓ2 of differences, graph and tree TV, and the image TVs with pixel or edge weights (whose scan ran once per image). Weighted soft thresholding on 2^16 entries went from 0.92 to 0.18 ns per entry.
- Elementwise derivatives (audit C5):
- A vjp asked for neither the step's nor the parameters' gradient computes only gx. Soft thresholding on 256 × 1000, one thread, went from 590–650 to 47–51 µs, and Huber from 810–850 to 46–48 µs.
- The step slot and up to two shared parameters are summed in registers, in the same order as before.
- Soft thresholding selects its pieces without branches.
- Contiguous JVPs without a parameter tangent run in a vectorisable loop: soft's from 540–600 to 177–180 µs, Huber's from 386–403 to 140–146 µs.
- The vjp's sums are the same bits as before, for every thread count and layout.
- The step's gradient of a projection (the box and the nonnegative orthant) is exactly 0 (audit C5). Before, it summed 0 · g_i and was NaN when a cotangent entry was infinite.
- The thread pool returns once every piece is done and every worker that joined the call has left, instead of waiting for every worker to wake (audit C6). One atomic control word (generation, closed flag, workers allowed, workers inside) replaces the generation and the pending count; a worker that wakes after the call closed its job goes back to wait. On an Apple M5 Pro under heavy background load (load average 20), an empty 15-thread job took 0.6–1 µs warm (119–185 µs before) and 15–26 µs cold (91–231 µs), and soft thresholding on 2^18 entries at 15 threads 28 µs (98–198 µs).
- The pieces of prox and jvp scale with the thread count (audit C7): about 8 row pieces per thread (at least 512 entries each) and 4 elementwise pieces per thread (8192 to 16 384 entries), instead of 16 384 entries whatever the count. 1D TV on 2^15 entries in rows of 16 at 15 threads took 43–56 µs (168–185 µs), soft on 2^15 entries 8 µs (14 µs). The vjp's blocks, which fix the order of its sums, are unchanged, so results are still bit-identical for any thread count.
- ctx.deriv is a DerivInfo of four fields (feedback U4): residual, iters = ctx.deriv now fails; use the attributes. examples/image_denoising.py and examples/autodiff_frameworks.py solve to tol=1e-8 before differentiating isotropic TV, so that their derivatives are not flagged.
[1.0.0rc2] — 2026-10-23¶
The second release candidate for 1.0, from master, on PyPI as a pre-release (pip install --pre fastprox). It adds the spectral operators, one step per row (fp_prox_steps), the device API (no CUDA kernels yet: device arrays return FP_EINVAL), the fixes of the audit of 2026-10-22, and the first items of the user feedback of 2026-10-23 (ztol=, IterInfo.zerr, ConvergenceWarning, fp.inner_accuracy). The new C functions join the 1.0 ABI, which the abi job still checks against 0.5.0. The remaining feedback items change the Python API and follow in an rc3 before 1.0.0.
Added¶
- Unconverged and too-loose iterative calls warn (feedback U2):
fastprox.ConvergenceWarningwhen a call stops atmax_iterbefore its tolerance, with the error it did certify (zerr). It is raised byprox,prox_conj,solve, the one-shot functions, and the PyTorch and JAX image functions and genericprox; JAX warns from the host throughjax.debug.callback, underjittoo. Before,proxreturned an unconverged z with no sign.solve(..., warn=False)and the framework functions'warn=Falsesilence one call.fp.inner_accuracy(target, factor=0.1), a context: the iterative calls inside it that set neithertolnorztoluseztol = factor * target, and a call whose own tolerance certifies less raisesfastprox.AccuracyWarning, the base class ofConvergenceWarning. The state is a context variable, so it is per thread and per task; the PyTorch and JAX wrappers capture it when a call is set up, so JAX's host callbacks see it.- Three examples (
image_denoising.py,autodiff_frameworks.py,reweighted_tv.py) stopped isotropic TV at the default 1000 iterations before their tolerance without saying so; they now passmax_iter=10**5. - Accuracy in the units of z (feedback U1):
- The bound, documented. An iterative image operator's
tolcertifies \(\lVert z - z^\star \rVert \le \sqrt{\mathrm{tol}}\,\lVert x \rVert\) per image, so the default 1e-6 gives \(z\) to 1e-3 relative andtol=1e-10to 1e-5. The header, the docstrings and docs/api.md now say so. A new section of docs/api.md, "Inexact proxes inside outer solvers", gives the conditions of Schmidt, Le Roux and Bach (NeurIPS 2011) for proximal gradient and its accelerated form inztol's units, and the recipe: an innerztola tenth of the outer tolerance, or a decreasing one, with warm starts. On a 96² inpainting problem, warm starts cut FISTA's inner iterations 10–14×. ztol=on everyprox,prox_conjandsolveofTVAniso,TVIsoandGraphTV, on the one-shottv_aniso,tv_isoandgraph_tv, and infastprox.torchandfastprox.jax(tv_iso,tv_aniso,prox,prox_conj). It asks for \(\lVert z_i - z_i^\star \rVert \le \mathrm{ztol}\,\lVert x_i \rVert\) for every image:tol = ztol**2, and for graph TV thetolwhose per-node bound gives that. It is exclusive withtol, and a positiveztolwhose square underflows raisesValueError.tolnow defaults toNone, meaning the previous defaults (1e-6, and 0 for graph TV).IterInfo.zerr: the certified relative error of the worst image, \(\max_i \sqrt{2\,\mathrm{gap}_i} / \lVert x_i \rVert\), on every path (NumPy, PyTorch, JAX). It is NaN for a NaN image.- C:
fp_workspace_image_info(ws, gaps, iters, zerrs, count)returns each image's gap, iterations and certified error from the last call. The errors are computed at the scale the image was solved at, so they hold for images whose gap overflows or underflows. - Spectral operators: any absolutely symmetric operator on the singular values of a batch of matrices, and any permutation-invariant one on the eigenvalues of symmetric matrices. Examples: the nuclear norm, its ball, the spectral norm and its ball, nonconvex low-rank penalties (SCAD, MCP, \(\ell_q\), \(\ell_0\), log), the PSD cone, the spectraplex, \(-\log\det\).
- C:
fp_op_spectral_checksays whether an operator qualifies.fp_spectral_jvpgives the \(k \times k\) core of the derivative from \(A = U^\top H V\), afterfp_proxon the spectrum; the caller keeps the decomposition and the matrix products, so the core still needs no LAPACK or BLAS. Ties and zero singular values take their exact limits from the Jacobian of the prox on the spectrum, through one extra JVP per row; near ties take the average of the two limits within \(\varepsilon^{1/3}\) of the scale. - Python:
fp.Spectral(op, kind="svd" | "eigh"), withNuclearNorm,SpectralNormBallandPSD.prox,prox_from,jvp,vjpandvalueuse NumPy'ssvd/eigh. - PyTorch and JAX:
fastprox.torch.proxandfastprox.jax.proxtake spectral operators, with the decomposition and the matrix products in the framework on the input's device (GPU included) and the \(k \times k\) core on the CPU. Gradients reachx,gamma, andlamorradiuswhenNuclearNormorSpectralNormBallis passed as a class; PyTorch also has forward mode, JAXjitandvmap. - Tests: finite differences on matrices with repeated and zero singular values, where autograd through
torch.linalg.svdgives NaN or a gradient 28–35% off, and Candès et al.'s closed-form divergence. - The design and its sources are in docs/spec.md, "Spectral operators".
- One step per row, image or matrix:
fp_prox_steps(op, gamma, x, out, opt, ws), withgammaof the batch shape (any strides; 0 broadcasts). Each row gets exactly whatfp_proxgives on it alone with its step, for any thread count. Derivatives after it use each row's step:fp_jvp'sdgammamoves every step,fp_vjp'sggammais the sum over rows, and a row's own gradient is \(\langle g, \partial z/\partial\gamma \rangle\) over that row fromfp_jvpwithdgamma = 1. In Python,proxtakesgammaas an array that broadcasts to the batch shape. So dofastprox.torch.proxandfastprox.jax.prox, where each step's gradient is its rows' \(\langle g, \partial z/\partial\gamma \rangle\), from one more JVP, summed back togamma's shape; PyTorch's forward mode takes a tangent per step, and spectral operators take one step per matrix.tests/python/test_steps.pychecks every operator against row-by-row calls, for the prox, the JVP, the VJP and with several thread counts.test_torch.pyandtest_jax.pycheck the wrappers' per-row gradients against finite differences for every shared case. - The device API of the GPU backend, which has no kernels yet:
FP_DEVICE_CUDA(DLPack's value 2) and the statusFP_EDEVICE. The C library loads the CUDA plugin,libfastprox_cuda, on first use. It looks first at the path inFASTPROX_CUDA_PLUGIN, then next to the library, then on the system's search path, and takes the plugin only from the same version. Arrays on a device still returnFP_EINVAL. New functions, which already work on the CPU: fp_device_availableandfp_op_device_check. The latter also reports whether one row of an operator is limited to one thread.fp_workspace_info: thefp_infoand status of the last prox call on a workspace.fp_vjp_device:fp_vjpwith the step's gradient in a 0-d array.fp_workspace_set_streamandfp_workspace_get_stream, for device workspaces.- Tests: CTest runs the loader against a stub plugin, a plugin of another version, a missing one and an empty
FASTPROX_CUDA_PLUGIN.
Changed¶
- The spectral operators,
fp_prox_stepsand the device API, documented as "since 1.1", ship in 1.0, and are marked "since 1.0" (audit A11).test_headerchecksfp_version_string()against the version CMake builds. IterInfohas a sixth field,zerr(feedback U1). Unpacking it into five names now fails; use the attributes.- An image operator's
proxwithoutkeeporctxno longer copies out the dual and builds anIterInfothat it then discards. - Non-NumPy array-likes keep float32: PyTorch and JAX arrays, memoryviews and
array('f')are converted withnumpy.asarray, without a copy where they export a buffer, instead of being cast to float64 (audit P5). Lists and other real types still become float64. Complex inputs raiseTypeError; before, they lost their imaginary part with aComplexWarning. The PyProximal adapter does the same, and converts float16 to float64. dparamsrejects unknown names and wrong sizes with aValueErrorthat lists the operator's parameters (audit P6). Before, a typo gave a zero tangent. It also accepts the derived nameslam(Soft, L1Box, Lq) andradius(SpectralNormBall).- Clearer errors at the Python boundary (audit P7):
- PyTorch tensors of other dtypes raise "fastprox operates on float32 and float64 tensors";
- a read-only
out, a floataxisandthreads < 0raise before the binding; - the one-shot functions reject an array
gammawith a pointer to the operator classes, and an out-of-rangeaxiswith its value; branchvalues other than −1, 0 and 1 raise;- errors from the C library name their entry point (
fp_prox: …).
Fixed¶
- Results on aarch64 Linux depended on the thread count and the array layout: one step per row (
fp_prox_steps) of soft thresholding and the elastic net differed in the last bit between 1, 3 and 8 threads, found by the wheel tests onubuntu-24.04-arm. GCC's default-ffp-contract=fastfusesa * b + cacross statements after inlining, so a loop with a hoisted step and one with a step per entry rounded the same expression differently, and the split of an elementwise run into a vector body and a scalar tail depends on the chunks a thread takes. The library now builds with-ffp-contract=offon GCC and Clang: every operation rounds on its own, on every compiler and CPU. x86 wheels are unchanged (baseline x86-64 has no FMA); on arm64 some results move by an ulp, and kernels cost 0–12% more (Apple M5 Pro: soft thresholding 12%, anisotropic TV 9%, 1D TV 7%, isotropic TV 3%). - A prox call rejected for its arguments leaves the workspace's saved point as it was, whatever the argument (audit A4). Before, a negative step or an output that overlaps the input kept the point, while a step beyond the step range, a negative
tol, or an image or row length the operator rejects discarded it. A call withoutkeep_structure, or one that fails during its work, still discards the point. The header, docs/api.md and docs/spec.md now say this; they read "the last prox call withkeep_structure", but any later call on the workspace counts. - Documentation (audit A6, A10, T10, P12):
- an operator must outlive its workspaces;
- no two calls on one workspace may overlap, the
constderivative calls included; - graph TV's derivatives are exact only with
tol= 0, and withtol> 0 are those of the regions where the solver stopped; - free-threaded CPython is not supported yet. Built from source on 3.14t, the extension re-enables the GIL with a RuntimeWarning, checked.
- Empty batches and NaN or Inf images follow one contract across the NumPy, PyTorch and JAX paths of the iterative operators (audit P8).
- Empty batches: they return an empty result with gap 0, 0 iterations and
converged, with empty or zero gradients. Before:- NumPy raised "invalid argument" (
fp_workspace_get_dual, as the empty call never marked its dual); fastprox.torch.tv_isoraisedIndexErrororRuntimeError;fastprox.jax.tv_isoraisedZeroDivisionError.
- NumPy raised "invalid argument" (
- NaN images: on the device paths a NaN image ran all 1000 iterations and made
convergedFalse. It now takes none and reports a NaN gap, as on the C path since A8. The other images are unaffected, and their gradients stay finite. - ±Inf: PyTorch and eager JAX now reject it with
ValueError, as the C path does. Underjax.jitsuch an image is treated as a NaN image. - Calls on one Python
Contextare serialised by a lock (audit P3). Its workspace's scratch, branch override and derivative tolerance are shared, and the GIL is released during the C calls. 4 threads making derivative calls on one context gave wrong results in 80 of 80 isotropic TV vjps (by up to 3.9e262) and in 118 of 120 soft-thresholding jvps with a branch. The cost on a tiny call is under 0.03 µs. - The Python bindings release the GIL in operator constructors, workspace creation, and the dual and kink copies (audit P4). Building
GraphTVon 2·10⁶ nodes held it for 255 ms. - Row operators' workspaces hold per-thread scratch for at most as many threads as there are rows (audit C2). Before, one row of 2²³ samples for 1D TV allocated 10.6 GB at 15 threads instead of 704 MB. Pages were touched lazily, so the time was the same, but with strict overcommit, or Windows commit accounting, the call could fail with
FP_ENOMEM. Spectral derivatives size their scratch the same way. - Thread counts are capped at 4 times the CPUs the process may run on, and at 4096 (audit C3).
fp_options.threads = 100000on soft thresholding of 2²⁶ entries created 4095 permanent pool threads, and the call took 14× longer than serially. The environment variables are capped the same way. - A
parallel_runfrom inside a pool job now runs serially on its thread (audit C10). From the caller's thread it calledtry_lockon a mutex that thread already held, which is undefined behaviour. No kernel nests today, so this is a guard for future kernels. - Images holding a NaN, in TV in 2 and 3 dimensions, graph TV and tree TV (audit A8):
- Certificate. Such an image used to report a perfect certificate: gap 0,
converged, and 0 iterations (1 for tree TV). It now reports a NaN gap and 0 iterations, and does not by itself make the callFP_ENOTCONV, since more iterations cannot fix it.fp_info.gap, a sum over the batch, is then NaN, andIterInfo.convergedstays True. - Dual. The NaN dual that
fp_workspace_get_dualreturns for such an image was rejected byfp_workspace_set_dual. Nowsetstores NaN entries as 0 and rejects only ±Inf, so a dual read back can always be set again, including as Python'swarm_start=.
Tested in test_core.cpp (test_nan_images), test_tv_iso.py, test_tv_spatial.py and test_graph_tv.py.
- Kept calls that do no work now give derivatives (audit A3). Two kinds of call returned FP_OK but left no saved point, so fp_jvp and fp_vjp then returned FP_EINVAL:
- an empty batch with keep_structure. Its derivatives now return FP_OK and write nothing, with zero gradients;
- fp_prox_conj at σ = 0. Its derivatives are now those of the identity, with a NaN σ-derivative, which is not defined there for every operator.
Steps are now checked on empty batches too. Before, a SCAD step that violated a > 1 + γ, or negative steps in fp_prox_steps on x of shape (3, 0), were accepted.
- Image operators (TV in 2 and 3 dimensions, graph and tree TV) ignore fp_options.axis, as documented (audit A5). Before, fp_prox rejected axis 5 with FP_EINVAL, and a workspace created with the default axis rejected a call with axis 0.
- Sizes too large to allocate return FP_ENOMEM and not FP_EINTERNAL (audit A7). The n of the group constructors and the counts of fp_op_tree_l2 above 2⁶⁰ − 1 are now FP_EPARAM, checked before the pointer arithmetic that was undefined for them.
- A failed fp_workspace_set_branch leaves an earlier override in place (audit A9). Elementwise operators dropped it on an invalid side, while row and image operators kept it. A row operator's override also survives an allocation failure in the next call.
- Graph TV: the dual and gap at large steps (audit T6). The flow of a live edge was read as γwₑ − residual, which loses it below an ulp of γwₑ. On a 16×16 grid with tol 0, the result was:
- at γ = 1e10: a dual residual ‖x − z − q‖∞ of 2.7e-6;
- at γ = 1e15: a gap of 0.33;
- at γ ≥ 1e17: a dual residual of 2.8 and a gap of 121, all reported converged.
The saved flow, which decides kinks, had the same error. Once γ·max w exceeds 64 times the value range, the max-flow engines (EIBFS and BK) now sum each arc's net flow from what every augmentation pushes, and the certificate reads that. Below that bound, cap − residual is accurate to 64ε of the range and stays, so the common case is not slowed. The dual residual is now 4e-16 and the gap 1e-30 from γ = 1e10 to 1e280. Tested in test_graph_tv.py (test_dual_at_large_steps, test_dual_at_the_step_bound) and test_maxflow.cpp (test_large_caps, and the net flow against cap − residual on every problem).
- Spectral derivatives on chains of near-ties (audit T7). Values whose adjacent gaps fall under the tie band ε^(1/3)·max|s| chain into clusters much wider than the band, and every pair in such a cluster took the averaged limit. Now only pairs within the band do; the others take their quotient. 200 singular values 5e-6 apart had a nuclear-norm jvp off by 0.23 relative, now about 1e-13. Tested in test_spectral.py (test_chained_near_ties).
- Graph and tree TV: inputs whose range overflows (audit T9). With max x − min x infinite, the graph solver's stopping width was NaN, so it set every node to the mean (x = [1e308, −1e308, 5e307, −5e307] gave [0, 0, 0, 0] with converged), and tree TV's gap was NaN. Both operators now solve far from unit scale on a power-of-two rescaling, as the image TVs do since T5. This is exact, and results are unchanged near unit scale. The gap can be inf when its value exceeds the double range. Tested in test_graph_tv.py (test_value_range_overflow, test_power_of_two_scale).
- 1D TV with the ℓ2 norm: derivatives far from unit scale (audit K4). The prox was already scaled, but its jvp and vjp formed ‖W D z‖ and its cube on raw z. On x = σ·[0, 1, 3, 2, 5] with γ = 0.8σ:
- at σ = 1e-110 the weight derivative was NaN or −inf;
- at σ = 1e110 the weight gradient was silently 2× off (6.7e109 instead of 3.4e109);
- beyond 1e±160 the Jacobian collapsed to the identity.
The derivatives now run in scale-free form, with the differences over ‖W D z‖ and γ/‖W D z‖ computed on z scaled by a power of two. They are scale-invariant from 2⁻⁵⁶⁰ to 2⁵³⁰. jvp and vjp at n = 10⁵ take at most 4% longer. Tested in test_tv1d_l2.py (test_derivative_scale_invariance).
- Row kernels far from unit scale, and fixed box entries (audit K3, K7, K8, K11).
- Log penalty (K3). The root of the stationarity condition no longer cancels for |x| < ε: λ = 1e-20, ε = 1, x = 3e-20 gave 0 where the root is 2e-20, and λ = 1e-14 was 5.5% off. It now matches 80-digit references to within 4 ulp. The root also no longer overflows: [1e200, 1e154, 1e155] gave [0, 1e154, 0]. Its derivative avoids λ/u².
- Hyperplane, half-space and the sums of the largest entries (K7). Σ aᵢxᵢ no longer overflows for entries near DBL_MAX/n. project_hyperplane([1.4e308, 1.4e308], [1, 1], 0) gave [−inf, −inf]; the solver now rescales by a power of two. The projection is exactly homogeneous, from 2⁻¹⁰⁰⁰ to 2¹⁰⁰⁰.
- Isotonic regression (K8). Block sums that overflow are redone on block means: isotonic([1.5e308, 1.5e308, 0]) gave inf. Weight ratios below 1e-100 are rejected (FP_EPARAM), as for the weighted ℓ1 ball.
- Box, ℓ1 over a box and hyperplane (K11). An entry with lo = hi is fixed, also when x lies on it: its Jacobian was 1, now 0.
Speeds are unchanged; the overflow paths are taken only when needed. Tested in test_nonconvex.py, test_planes.py and test_operators.py. (K9, an overflow in 1D TV's constant mean, can no longer be reached with the step range of A1.)
- fp_prox_conj at small σ and steps that overflow inside kernels (audit A1). For σ < 5.6e-309, 1/σ overflowed: soft thresholding returned NaN with FP_OK, and row operators returned FP_EINVAL for the same call. At σ = 1e-300, group ℓ2, tree ℓ2 and image TV returned wrong values with FP_OK, and float32 failed from σ = 1e-100. The fixes:
- Homogeneous operators. For a positively homogeneous g or a cone indicator (soft thresholding, the ℓ2, group, tree and ℓ∞ norms, max, the sums of the largest entries, every TV, the orthant, the second-order cone, isotonic regression), the conjugate is now y − prox_g(y). That is exact and the same for every σ > 0, with σ-derivative 0. It changes results for σ ≠ 1 at rounding level. For image operators the workspace dual after the call is now that of the unit-step problem, so a warm start seeded from an earlier fp_prox_conj at another σ starts from a scaled dual.
- Other operators. They return FP_EPARAM when 1/σ or some y/σ overflows: float32 is checked for σ < 1, float64 for σ < 2⁻⁶⁴.
- A step range for every call. γ times the operator's largest parameter must not exceed 2⁹⁶⁰ (about 2.4e289); beyond it the call returns FP_EPARAM. Before, the log barrier at γ = 1e308 gave inf and NaN, max and the sum of the largest entries gave −inf, and tree TV gave a wrong value at DBL_MAX.
Conjugate timings are unchanged. Tested in test_core.cpp (test_conj_extremes) and a wider σ range in test_moreau_conjugates. The fuzz harness now checks that a successful call on finite input never returns NaN, for every finite step.
- Outputs that overlap their input (audit C1, P2). out was checked only by pointer equality, so other overlaps gave silently wrong results: an in-place transpose, a reversed view, or a view shifted by a row. In one of these cases the result depended on the thread count, which broke the determinism guarantee. A stride-0 output raced. The C library now accepts an output that is exactly its input (the same data, shape and strides) and returns FP_EINVAL for any other overlap of byte ranges, or for a stride-0 output dimension, before any work, so a workspace keeps its previous structure. The same rule applies to dx/dout in fp_jvp, g/gx in fp_vjp, the steps of fp_prox_steps and the output of fp_value. In Python, any out works: an input that overlaps it is copied and the call retried. The check runs only after the C library rejects a call, so the common path costs nothing. A read-only or zero-stride out now raises a clear ValueError. Tested in test_core.cpp (test_aliasing) and tests/python/test_out_overlap.py.
- Array descriptors too large to address (audit A2). Extents whose product, or strides whose offset span, overflowed int64 were accepted and led to out-of-bounds reads and writes; for example, shape (2⁶² + 1, 4) with strides (0, 1) sized the workspace for 4 entries. Every descriptor is now limited to 2⁶⁰ − 1 entries and offset span (FP_ESHAPE), and workspace byte counts saturate, so an oversized one fails to allocate (FP_ENOMEM) instead of coming out short. Tested in test_core.cpp (test_descriptor_bounds).
- Euclidean norms far from unit scale (audit K2, with K5 and K10). The ℓ2 ball, ℓ2 and group ℓ2, the tree-structured norms, group Huber, SCAD and MCP and the second-order cone took √(Σxᵢ²), whose squares overflow beyond about 1e154 and underflow below about 1e-154. Examples: project_l2_ball([1e200, 1e200], 1) returned [0, 0], the cone gave inf and NaN on [0, 1e200, 1e200], and group Huber gave NaN on [1e200, 1e200]. Norms are now rescaled by a power of two wherever the plain sum of squares leaves its safe range, as the reference BLAS dnrm2 does (Blue 1978; Anderson 2017). They also keep that scale where the norm itself overflows or is subnormal, so results are right for any finite input. In-range rows give the same bits as before. Two derivatives were fixed as well:
- TreeL2's chain step no longer forms τ/s³ (K5): it gave inf for groups below about 1e-103.
- Huber's derivative no longer forms (δ + γλ)² (K10), which over- or underflowed.
Rows of 8 entries take about 5% longer for the ℓ2 ball, from one range test per row; long rows, the cone and group ℓ2 are unchanged. Tested in tests/python/test_norm_scaling.py: homogeneity at 2^±400 to 2^±1000, subnormal inputs, norms above the largest double, and the audit's reproducers. The fuzz harness now also scales these operators' inputs; it found a NaN on subnormal input during this work, now fixed.
- Image TV far from unit scale (audit T5): beyond about 1e154, ‖x‖² and the gap terms overflowed. Isotropic TV then returned x itself, reported as converged, and the conjugate prox at σ = 1e-156 returned 0. 3D anisotropic TV returned only the 1D prox along the last axis, and 2D anisotropic TV ran to max_iter with a NaN gap. Below about 1e-154 the same squares underflowed. The anisotropic and isotropic TV solvers now rescale an image whose largest entry is outside [2⁻⁶⁴, 2⁶⁵) by a power of two and scale back, all exact, so prox(c x, c γ) = c prox(x, γ) for c = 2^k. Images in that range give the same bits as before. Isotropic TV's derivatives run at the solved scale, so they are also exact past 2⁵¹², where squared gradients would overflow. The gap scales by c² and may be reported as +inf. Tested in tests/python/test_tv_scaling.py (k = ±300 to ±1000, the conjugate at σ = 1e-156, jvp and vjp at 2⁷⁰⁰), and the fuzz harness now scales image-TV inputs by 2^±(600–1000).
- Enum values outside their enumeration (audit A12). A C caller can pass any int in an enum argument or field, and the library compared such values directly, which is undefined in C++. This covers the dtype and device of fp_array, the 1D TV method, the spectral kind, and the device of fp_device_available and fp_op_device_check. The boundary now reads them as ints and rejects values outside the enum with the same codes as before. The sanitizer build treats UBSan reports as fatal (-fno-sanitize-recover=undefined); before, the job passed with them. Tested in test_header.c.
- Anisotropic TV derivatives at tiny bounds (audit T1): where an edge's bound γ w_a β_e was below about 10⁷ eps max|x| (tiny γ, or learned edge weights near 1e-6), the derivatives merged regions that the solution keeps apart. On 32² N(0,1) images the jvp was 0.79–0.97 off the exact identity at γ = 1e-8 to 1e-12, and 0.59–0.66 off finite differences with half of the edge weights at 1e-6 or 1e-8, with nothing signalled. The flat test read the edge's 1D dual, whose rounding then exceeds the bound. An edge whose jump the gap certifies, |z_j − z_i| > 2√(2 gap) plus rounding allowances, is now a boundary whatever its dual says. Every solution with such a jump has one there too, so the rule only corrects. The check is skipped when no jump can pass it, which is the usual case: keep=True costs at most 3% more on a 2048² image at tol 1e-4. Tested in test_tv_aniso.py (2D and 3D, tiny γ and tiny edge weights, also through branch) and test_core.cpp.
- Derivatives at a zero threshold (audit K1): where the threshold is 0 (λ = 0, a zero weight or group weight, or γ = 0) the map is the identity, but at x = 0 the Jacobian was 0, so an unpenalised coefficient starting at 0, as in unrolled ISTA, got no gradient. It is now 1 (1/(1 + γ l2) for the elastic net) for soft thresholding, the elastic net, ℓ1 over a box, ℓ0, SCAD, MCP, the log penalty, group ℓ2, the tree-structured norms, and the group SCAD and MCP that use the scalar maps at x_g = 0; jacobian_diag now agrees with the empty kink mask there. The log penalty at γλ = 0 also gives the same parameter derivatives whether or not a branch override is set. Tested in tests/python/test_kinks.py and by two new cases in derivative_cases with an exact 0 in x.
- PyTorch: second-order reverse mode through fastprox.torch.prox, prox_conj, tv_iso and tv_aniso (create_graph=True, as in torch.autograd.functional.hvp and hessian) returned a wrong Hessian with no error: torch 2.14's once_differentiable no longer refuses double backward, and the prox's own second derivatives were dropped. For soft thresholding the Hessian diagonal was off by 2 on the entries the prox keeps. It now raises RuntimeError until exact second order lands in 1.0.x (audit P1). First-order backward and forward mode are unchanged. Tested in test_torch.py for soft thresholding, 1D TV, the nuclear norm and both device-native TV functions.
- 1D TV with the ℓ2 norm (since 0.2; also released as 0.5.1): wrong results, and NaN, on rows whose weights or entries span many orders of magnitude. Found by the nightly fuzz run: NaN on entries near 10⁻¹⁴⁷ with only an edge of weight 4·10⁻¹⁴⁹ between them (μ* ≈ 2·10⁻²⁹⁵, in a conjugate prox). Three causes:
- σx underflowed in the tridiagonal solves, so ‖W D z‖ was 0 at every μ, bisection drove μ to 0, and the zero pivot of a zero weight gave NaN.
- ‖W D z‖ was computed from differences of z, which carry its rounding: one ulp of z across an edge of weight 0.5 is 10⁻¹⁷, which hid an edge whose part was 10⁻¹⁵⁰. The Newton iteration now runs on the differences, B Dz = μ D x with B = μI + D Dᵀ W² on the edges. B is an M-matrix whose pivots are kept in the same cancellation-free excess form. The step is taken in the normalised dual u/γ. z still comes from one solve with μI + K at the final μ.
- ‖u₀‖² underflowed for small rows, which passed them as inside. The inside test and the iteration now run on the centred row and γ scaled by a power of two that brings the largest entry to [½, 1). Bisection runs in the exponent, so a root 150 orders of magnitude below its bracket takes a few steps, not 500.
On such rows the old results were off by up to 100% of max|x|; they now agree with a 700-digit solver to 2·10⁻¹⁶. Ordinary rows change only by rounding, at the same speed. Tested in tests/python/test_tv1d_l2.py: the fuzz input against the closed form for two rigid blocks, and scale invariance over 2^±600 for 300 rows with weights over 150 orders of magnitude.
- Graph TV, tree TV and image TV keep the step range when they scale up an image near the smallest normal double (found by the nightly fuzz run). The scale-up checked gamma but not gamma times the weights, so with weights above 1 the scaled capacities overflowed. A path of 8 nodes with one entry of 2.4e-308 and gamma = w = 3.9 gave inf and NaN from TreeTV. GraphTV returned a NaN gap and TVAniso stopped unconverged. The scale-up now stops where gamma times the largest weight reaches 2^960. The result is unchanged where nothing overflowed.
[0.5.1] — 2026-10-21¶
A patch release of 0.5.0 on the release/0.5.x branch: pip install fastprox gets it while 1.0 is a release candidate. The C API, the ABI and the Python API are those of 0.5.0.
Fixed¶
- 1D TV with the ℓ2 norm gave wrong results, and sometimes NaN, on rows whose weights span many orders of magnitude, silently: the fix under [Unreleased] above. In tests on random rows, weights over 16 orders of magnitude gave wrong results on three rows in four, by up to 2.5% of max|x|; weights over 8 orders did so only for entries near 10⁻¹⁰⁰.
[1.0.0rc1] — 2026-10-20¶
The release candidate for 1.0, on PyPI as a pre-release (pip install --pre fastprox). The C ABI is now frozen: until 2.0 it only grows, and CI checks that against the last release. Its ABI is that of 0.5.0, unchanged, under a new major version. The operators and the Python API are those of 0.5.0.
Added¶
- An ABI check in CI: the
abijob compares the C library with the last release usingabidiff(libabigail), on the types offastprox.h, and fails on any change but an addition. Publishing to PyPI waits for it. CMake now requiresFP_ABI_VERSIONto equal the major version, which is also the soname's. The policy for 1.x is in docs/api.md, "ABI stability".
Changed¶
- The major version is 1, and with it
FP_ABI_VERSION(fp_abi_version()returns 1) and the soname:libfastprox.so.1on Linux,libfastprox.1.dylibon macOS. Programs built against 0.x need rebuilding once, as for any 0.x minor version; no declaration changed since 0.5.0.
Fixed¶
fp_value,Operator.valueand the PyProximal adapter were documented as "since 1.0"; they shipped in 0.5.- The conda recipe builds the Python package with Ninja. scikit-build-core had picked Makefiles, which conda-forge's Linux image lacks (the GitHub runners have make). Its tests now import the package on the oldest and the newest supported Python, and check the extension with
abi3audit, as conda-forge's linter suggests.
[0.5.0] — 2026-10-19¶
Added¶
- A conda-forge recipe,
packaging/conda/recipe.yaml, forlibfastprox(the C library, with its pkg-config and CMake files) andfastprox(the Python package, abi3). The newcondaworkflow builds and tests it with rattler-build on Linux, macOS and Windows. - CMake option
FASTPROX_STATIC_LIBSTDCXX, on by default: it links libstdc++ and libgcc statically on Linux with GCC, as before. conda-forge turns it off, since it provides its own. fastprox.pyproximal.ProxOp: any operator as apyproximal.ProxOperator, so fastprox works in PyProximal's solvers. It reshapes PyProximal's flat vectors todims, returns \(g(x)\) fromOperator.value, mapsproxdualtoprox_conj, and can warm-start the iterative image operators. It is checked against PyProximal'sL1, itsmoreautest, and a lasso throughProximalGradient. The exampleexamples/pyproximal_tv.pydeblurs an image: the same PSNR aspyproximal.TV, about 6× faster. PyProximal (LGPL-3.0) stays optional, in theinteropdependency group.fp_valueandOperator.value(x): the value \(g(x)\), one per row or image, for every operator. The projections give their set's indicator: 0 within a relative tolerance, else infinity. Each value is checked against the operator's prox: \(z = \operatorname{prox}_{\gamma g}(x)\) must minimise \(g(y) + \lVert y - x \rVert_2^2 / (2\gamma)\) (tests/python/test_value.py). This is what the PyProximal adapter needs for its objective, and it is added before the 1.0 freeze.- A documentation site, https://dvillacis.github.io/fastprox/, built with MkDocs Material from the Markdown in
docs/, the README, the changelog and roadmap, and the examples (each with its source); the Python reference is generated from the docstrings (mkdocstrings), and formulas are LaTeX, rendered by KaTeX. A workflow builds it strictly on every pull request and deploys it to GitHub Pages on each release.
Changed¶
fp_op_logis nowfp_op_log_penalty, matching the PythonLogPenaltyand leaving no doubt next tofp_op_log_barrier: a breaking change to the C API, made before the 1.0 freeze. The Python package is unchanged.
[0.4.0] — 2026-10-19¶
Added¶
- Kink masks and branch overrides for the box and the nonnegative orthant (entries on a bound), the simplex and the ℓ1 ball (entries at the threshold, on or off the support; for the ℓ1 ball also a row on its sphere, inside or projected) and group ℓ2 (a group at its threshold, zeroed or live), through
fp_workspace_kinks/fp_workspace_set_branchandctx.kinks/branch=as for the other operators. Row-level kinks take the side given at the row's or group's first entry. Group ℓ2 now saves its live groups for its derivatives, which are unchanged. Each side matches its one-sided difference (tests/python/test_kinks.py). - Kink masks and branch overrides for tree TV, whose kinks are edges: masks and sides have the shape of x with the last axis over the edges (
fp_workspace_kinks/fp_workspace_set_branchtake that shape). An edge with equal ends and its flow on its bound is joined (−1, the default) or kept apart (+1). The fuzzer now covers tree TV. - The same for graph TV, judged on the flow its solver found, which the prox call now saves with the structure (one double per edge and image); on a graph with cycles the flow is not unique. Graph TV on a forest gives tree TV's kinks and derivatives. The fuzzer now covers graph TV.
Changed¶
- Graph TV's max-flow engine is excesses incremental breadth-first search (Goldberg, Hed, Kaplan, Kohli, Tarjan and Werneck, ESA 2015), written from the papers in
src/maxflow/eibfs.hpp, instead of the Boykov–Kolmogorov engine: 1.9–2.7× faster at γ = 0.5 and 1.2–1.9× at γ = 0.1 on 512² grids, within 12% elsewhere (docs/benchmarks.md). The solutions are unchanged bit for bit (the same cuts); the flow, and with itinfo.dual, the gap to rounding and graph TV's kink masks, can differ. - A cleared branch override of an image operator (anisotropic, graph and tree TV) copies back the prox call's own structure instead of rebuilding it from the saved x and z, so it is the default bit for bit in float32 too.
- The README describes what sets fastprox apart, with measured figures, and has quick starts for images, PyTorch on GPUs and the C API.
[0.3.0] — 2026-10-19¶
Graph and tree TV, PyTorch and JAX wrappers, and image TV on the GPU, with
more accurate and cheaper image TV derivatives, spatially varying weights
for image TV, and kink masks and branch overrides for TV and the nonconvex
maps. The larger open items moved to 0.4 in ROADMAP.md. The C ABI only
grows: every 0.2 declaration and struct is unchanged
(fp_workspace_set_deriv_tol now also accepts 0, its new default). The
release candidate 0.3.0rc1 (2026-10-18) had everything below except the
cached reference of bench/compare_deepinv.py.
Added¶
- A max-flow engine for graph TV (
src/maxflow/, internal): Boykov–Kolmogorov augmenting paths on two search trees, written from the paper, whose trees and flow carry over between solves when terminal or edge residuals change. It runs in caller memory without allocating and is tested by optimality certificates and against Dinic's algorithm (tests/c/test_maxflow.cpp). - Graph TV,
fp_op_graph_tv(n, m, edges, w)andfp.GraphTV(n, edges, weights)/fp.graph_tv: the prox of γ Σ_e w_e |z_u − z_v| on any graph, on the last axis and batched over the others. Parametric max-flow (Chambolle and Darbon; Hochbaum) with each part cut at the mean of its solution, so a part whose cut is trivial ends exactly; every part is cut in one solve per round, reusing the flow and the search trees. Exact to rounding withtol = 0(the Python default), else withintol·(max x − min x) at every node;fp_info.gapis the duality gap with the flow as the dual. Derivatives (JVP, VJP, γ and per-edge weights) are exact averages over the regions where z is constant. Tested by an independent KKT check (tests/python/test_graph_tv.py), against 1D TV on chains, anisotropic TV on grids and CVXPY fixtures. - Tree TV,
fp_op_tree_tv(n, m, edges, w)andfp.TreeTV(n, edges, weights)/fp.tree_tv: graph TV for edges that form a forest (trees, paths, in any labelling), exact in one pass by dynamic programming (Kolmogorov, Pock and Rolínek, Algorithm 2), with the breakpoints of the messages in two pairing heaps (O(n log n)) or, when every tree is a path, a sorted deque (O(n)). The gap, the dual and the derivatives are those of graph TV, from code now shared by both (src/ops/edge_tv.hpp). 4–8× faster than graph TV on trees; tested against graph TV, against 1D TV on shuffled paths, by the KKT check and CVXPY fixtures (tests/python/test_tree_tv.py).bench/compare_tree_tv.pytimes it. - PyTorch and JAX wrappers,
fastprox.torch.prox/prox_conjandfastprox.jax.prox/prox_conj: any operator, or an operator class with its parameters, as a differentiable function of the input, the step and the parameters, with the gradients from the library's VJP (and, in PyTorch, its JVP for forward mode). PyTorch: atorch.autograd.Function, CPU tensors or a round trip from other devices. JAX:custom_vjpoverpure_callback, underjit,gradandvmap. Tested bygradcheck(reverse and forward),jax.test_util.check_gradsand against the NumPy API on elementwise, row, image, graph and tree operators (tests/python/test_torch.py,test_jax.py; dependency groupinterop, a CI job on Linux and macOS).examples/autodiff_frameworks.pylearns TV weights with Adam and γ of isotropic TV underjax.jit. - Device-native image TV,
fastprox.torch.tv_iso/tv_anisoandfastprox.jax.tv_iso/tv_aniso: the problems ofTVIsoandTVAnisosolved in tensor operations on the input's device (CUDA, MPS, CPU), with no change to the C API. Forward: FISTA on the dual with the C kernels' step, restarts, gap stopping and warm starts (duals in the C kernels' form, so either side can warm-start the other). Backward in x, γ and the weights: the C kernels' derivatives on the flat regions, found on the device by hooking and pointer jumping and summed by a sort and a segmented scan, so the result is the same run to run (no atomic adds) and memory does not grow with the iterations. PyTorch: reverse and forward mode; JAX: reverse mode underjitandvmap. Tested intests/python/test_device_tv.py(also on a GPU when one is present);bench/device_tv.pytimes it against the C kernels. bench/compare_deepinv.py: isotropic TV against DeepInverse'sTVDenoiser(same problem; Chambolle-Pock with autograd through its iterations): time to a given accuracy on the CPU and the GPU, the host round trip of the C path, and the time, memory and accuracy of the backward. On 8 × 256² images on an Apple M5 Pro, the device path reaches a given accuracy 3–17× sooner on MPS; the unrolled backward keeps 10 MiB per iteration (4 GiB at 400), the implicit one 6 MiB (docs/benchmarks.md).- One step per image in the device-native image TV:
gammainfastprox.torch.tv_iso/tv_anisoandfastprox.jax.tv_iso/tv_anisomay be a tensor that broadcasts to the batch shapex.shape[:-ndim](forxof shape (B, C, H, W), shape (B, 1) gives each sample its own step), as DeepInverse's denoisers take one σ per sample. Each image matches a call with its own scalar step, and the gradient ingammahasgamma's shape. One step for all images runs as before. - Spatially varying weights for image TV:
fp_op_tv_iso_weighted(ndim, w, alpha)/fp.TVIso(ndim, weights, pixel_weights=alpha), \(\gamma \sum_p \alpha_p \lVert (W D z)_p \rVert_2\) with one weight per pixel, andfp_op_tv_aniso_weighted(ndim, w, beta)/fp.TVAniso(ndim, weights, edge_weights=beta), γ Σₐ wₐ Σ_p β_{a,p} |z_{p+eₐ} − z_p| with one weight per pixel and axis, for one image shape (batched over leading axes). The weights enter the dual bounds (anisotropic TV's 1D steps are weighted 1D TV proxes), so the gap, warm starts and the polish carry over, and all-ones weights give the unweighted operator bit for bit. Derivatives in x, γ, w and every spatial weight (grads.pixel_weights,grads.edge_weights, in the weights' shapes), also throughfastprox.torch.proxandfastprox.jax.prox. Tested against CVXPY fixtures with random weights (some zero), finite differences, adjointness and gradcheck/check_grads (tests/python/test_tv_spatial.py,test_tv_spatial_weightsintests/c/test_core.cpp).examples/reweighted_tv.pyruns iteratively reweighted ℓ1 for TV^q (Ochs, Dosovitskiy, Brox and Pock 2015) to a stationary point, 6 dB above TV on its test image. - Spatial weights in the device-native image TV:
pixel_weightsinfastprox.torch.tv_isoandfastprox.jax.tv_iso,edge_weightsintv_aniso, the problems ofTVIso(pixel_weights=)andTVAniso(edge_weights=)on the input's device. One map for every image or one per image (the weights broadcast tox.shape, edge weights with a leading axis of ndim), differentiable in reverse mode and, in PyTorch, forward mode, with gradients summed back to the weights' shapes. Each image matches the C kernel with its own map, gradients included (to 1e-11, exactly for anisotropic TV); tested by gradcheck, check_grads,vmapand on the GPU. 7–12% more time per forward on MPS. - Kink masks for 1D, anisotropic and isotropic TV (
fp_workspace_kinks,ctx.kinks(tol)): the edges (1D TV: code 1 at the tail; anisotropic TV: bit a for an edge along axis a) and pixels (isotropic TV) where the dual is withintolof its bound and the jump or gradient withintolof 0, the biactive points where the derivative is set-valued; weights included. Read from the saved solution and dual, the same for any thread count, and checked against the definition recomputed from the returned z and dual. Branch overrides for TV come later (fp_workspace_set_branchreturnsFP_EINVALfor them). - The ties of ℓ0, ℓq and the log penalty are kinks (code 1): masks and branch overrides, with the zero piece on one side and the nonzero branch on the other, as for SCAD and MCP; for the log penalty with γλ ≤ ε², whose map is continuous, the kink where its branch starts. Each side matches its one-sided difference.
- Branch overrides for 1D and anisotropic TV (
fp_workspace_set_branch,branch=in Python): at a kink, side −1 joins the edge's two sides and +1 keeps them apart with the sign of its dual, the two pieces of the B-Jacobian there. Each matches the one-sided difference in a direction that keeps it, in x and in γ, and the VJP is its adjoint. Isotropic TV has none yet. docs/deepinv.md:fastprox.torch.tv_iso/tv_anisoin place of DeepInverse'sTVDenoiser/TVL1Denoiser, with the map between their arguments (per-sample steps, stopping, warm starts, gradients) and the differences to expect, checked byexamples/deepinv_tv.py(needs DeepInverse; it says so and stops without it).bench/compare_deepinv.pytakesanisoto comparetv_anisowithTVL1Denoiser: on 8 × 256² images on an Apple M5 Pro, 2.2–12× faster on MPS to the same accuracy, with a backward of 45–52 ms against 630 ms for 400 unrolled iterations (docs/benchmarks.md).
Fixed¶
- 2D anisotropic TV (since 0.2): when ‖x‖² overflowed, as in a conjugate prox at a tiny σ (x/σ ≈ 1e251), the gap target was infinite, the method stopped before its first iteration and returned a z it had never written (left-over memory, so results also changed with the thread count). It now computes z and its gap first. Found by fuzzing the weighted constructors; tested in
tests/c/test_core.cpp.
Changed¶
- Derivatives of isotropic and anisotropic TV read the flat pixels and edges off the dual, in the C kernels and on the device: an entry strictly inside its dual bound, ‖u_p‖ < γ(1 − 10⁻⁹) for isotropic TV and |p_e| < γwₐ(1 − 10⁻⁹) for anisotropic TV, is flat at the solution (complementary slackness). Before, a threshold on the jumps of z set by the certified error, 8·rms(gap), also flattened entries with small true jumps. Isotropic TV's system is stiffer with these entries (pixels on the sphere with small gradients, and more so as the gap shrinks), so its curvature γ/‖g_p‖ is capped at γ/μ, μ = 0.1 w_max √(2 gap / N), a Huber smoothing at the level of the certified error (Hintermüller and Stadler 2006; De los Reyes, Schönlieb and Valkonen 2017) that vanishes with the gap. On 2 × 128² images the isotropic derivative's error against the exact one fell from 18–57% to 4% at a gap tolerance of 1e-6 and from 5–24% to 0.5–0.7% at 1e-8 (near the 0.8% by which two valid derivatives differ at degenerate pixels), at 3–8× the conjugate gradient iterations; the anisotropic C kernel's from 7–19% to 2–5% at 1e-8, and it is exact from 1e-10 or wherever the polish has found the regions; the device's anisotropic derivative is exact at 1e-8. Boundary edges of anisotropic TV take the sign of their dual, as in the polish. The device backward now uses the C kernel's Jacobi preconditioner (1.6–25× fewer iterations than the region sizes alone at γ ≥ 0.1).
- Graph TV on graphs with nodes of high degree: the max-flow engine rescanned all of a node's arcs whenever it grew or was adopted, which made a hub quadratic (a star with 10⁵ leaves took 24.6 s). Nodes of degree above 32 now resume their growth scan and take the first valid parent in cyclic order, and a node freed next to such a hub rejoins its tree after the adoption stage rather than reactivating the hub: 53 ms on that star, 1.7–5× faster on a grid with five hubs, and the same steps as before on graphs without hubs (grids and kNN graphs unchanged). Tested against Dinic's algorithm on stars and random graphs with hubs, fresh and reused (
tests/c/test_maxflow.cpp). - Isotropic TV's derivatives stop their conjugate gradients, by default, at the relative error of z that the prox's gap certifies, √(2 gap)/‖x‖ (at most √tol after a solve to
tol, and no tighter than 1e-10, or 100 ε on the device), instead of a fixed 1e-10 (100 ε in float32 on the device). Residuals below √tol did not change the gradient, whose error after a solve totolis 50–100 √tol, and the C kernel takes 2–5× fewer iterations. A fixed tolerance is still available:tolinTVIso.jvp/vjp(default nowNone),deriv_tolinfastprox.torch.tv_isoandfastprox.jax.tv_iso, andfp_workspace_set_deriv_tol, which now takes 0 for the default (its new initial value). - The device-native image TV sums over regions with a segmented scan in two levels (within blocks of 32 sorted entries, then over the blocks) rather than by doubling over the whole image: 6× faster on MPS for 8 × 512² images, with the same accuracy. With the new stopping rule the isotropic backward on those images takes 137 and 546 ms on MPS at gap tolerances of 1e-4 and 1e-6 (before: 948 and 2494 ms), 269 and 1062 ms with PyTorch on the CPU (1227 and 3282) and 635 and 3111 ms with JAX (5724 and 20 285); on the DeepInverse comparison (8 × 256²) it takes 166 ms at 1e-6 against 612, with the same gradient error (docs/benchmarks.md).
bench/compare_deepinv.pycaches its float64 reference indeepinv_ref_<mode>_<size>_<batch>.npz(read when present, written otherwise), so that a machine with few cores, such as Colab, can use one computed elsewhere. docs/benchmarks.md has the comparison on an NVIDIA T4.
[0.2.0] — 2026-10-17¶
Image operators, nonconvex penalties and more exact operators, with derivatives. The C ABI only grows: every 0.1 declaration and struct is unchanged.
Added¶
- Anisotropic TV of 2D and 3D images (
fp_op_tv_aniso,fastprox.TVAniso,fastprox.tv_aniso): the prox of γ Σₐ wₐ TVₐ on the last 2 or 3 axes, batched over the others. Dual methods with exact 1D TV steps along each axis: the accelerated dual block proximal gradient method for two axes (Beck 2017, §12.5.4; Chambolle and Pock 2015) and the fast dual proximal gradient method for three (Beck, Algorithm 9). It stops on a certified duality gap (tol·‖x‖²/2 per image,FP_ENOTCONVaftermax_iter), and recovers the solution's constant regions to polish it to the exact solution when they are identified. JVP and VJP in x, γ and the axis weights come from those regions in O(n). Bit-identical for any thread count, also inside a single image. - Image operators in the core: a third operator kind (
ImageOp) acting on the last k axes, with its own driver, working sets in the workspace and threads inside an image when the batch is small. - Warm starts:
fp_workspace_get_dual,fp_workspace_set_dualandfp_workspace_set_warm; in Python,warm_start=andwarm=True, andIterInfo(gap, iters, ties, converged, dual) for iterative operators. fp_options.tolandmax_iterare now used (by the iterative operators), and the Pythonproxbinding takes them.- CVXPY reference fixtures for images (
tests/fixtures/reference_images.npz,generate.py images), Python tests (tests/python/test_tv_aniso.py), C tests with an independently recomputed certificate, and fuzzing of the new operator. bench/compare_tv_aniso.py: time to reach a given accuracy against proxTV's 2D and 3D solvers.- Isotropic TV of 2D and 3D images (
fp_op_tv_iso,fastprox.TVIso,fastprox.tv_iso): the prox of \(\gamma \sum_p \lVert (W D z)_p \rVert_2\) with forward differences on the last 2 or 3 axes, the weights scaling each axis inside the norm. FISTA on the dual (Beck and Teboulle 2009; Beck 2017, §12.4.4) with a certified gap, warm starts (a dual for another γ is projected onto the new ball) and an exact 1D path for one active axis; rescaled internally so extreme weights and steps stay finite (found by fuzzing: 4w² underflowed to 0 for a denormal weight). JVP and VJP by implicit differentiation, one unknown per flat region, solved by conjugate gradients. fp_workspace_set_deriv_tolandfp_workspace_deriv_info: tolerance and iteration cap of the derivative solves, and the residual and iterations of the last one; in Python,tolandmax_iteronTVIso.jvp/vjpandctx.deriv.bench/compare_tv_iso.py: time to reach a given accuracy against scikit-image'sdenoise_tv_chambolle. CVXPY fixtures for isotropic TV,tests/python/test_tv_iso.py, C tests with an independent certificate, and fuzzing.src/ops/image_util.hpp: the fiber passes, geometry and fixed-order row sums shared by the image operators.- Nonconvex pointwise maps: ℓ0 (
fp_op_l0,L0,hard_threshold), ℓq for 0 < q < 1 (fp_op_lq,Lq,lq; closed forms for q = 1/2 and 2/3, Newton from |x| otherwise), SCAD (fp_op_scad,SCAD,scad), MCP (fp_op_mcp,MCP,mcp) and the log penalty (fp_op_log,LogPenalty,prox_log), with derivatives in x, γ and their parameters. The SCAD and MCP maps are given for any step and need a > 1 + γ and b > γ (FP_EPARAMotherwise, through a new step check). Verified against minimisation on a refined grid, ties included; ℓ0, SCAD and MCP cost about 0.4–0.5 ns per entry, ℓq 12–13 ns in closed form and about 40 ns by Newton (Apple M5). - The tie rule:
fp_options.tie(FP_TIE_NONZEROby default,FP_TIE_ZERO) andfp_info.ties, the number of entries exactly on a threshold, the same for any thread count; in Pythontie="nonzero"|"zero"andctx.info.ties. Derivatives follow the branch the rule picked. tests/python/test_nonconvex.py(global minimisers on a refined grid, exact tie flags, closed forms against Newton, step conditions) and the nonconvex maps inCASES, the C derivative cases and the fuzzer.CASESentries may now be marked nonconvex, which skips the firm-nonexpansiveness property.- Support functions through the Moreau identity: the prox of λ max (
fp_op_max,Max,prox_max), which is min(x, τ) with Condat's simplex threshold, and of λ times the sum of the k largest entries or absolute values (fp_op_sum_largest,SumLargest,prox_sum_largest; Beck 2017, Examples 6.49–6.51). Both use the set scaled by γλ, so small steps do not overflow. - Projection onto a hyperplane or half-space intersected with a box (
fp_op_hyperplane,Hyperplane,HalfSpace,project_hyperplane,project_halfspace; Beck 2017, Theorem 6.27), with derivatives in x, b, a and the bounds. a may be a scalar or per entry, and a = 1 on [0, 1] is the capped simplex. Its multiplier comes from Newton steps on the piecewise-linear constraint function inside a bracket, with a median-of-breakpoints fallback, starting long rows from a strided sample's root: 3–9 ns per entry on Apple M5. An empty set for the row length returnsFP_EPARAM. tests/python/test_planes.py: KKT conditions up to 20 000 entries, agreement with the bisection reference, the closed forms and the operators these generalise (simplex, ℓ∞, soft thresholding), conjugates, extreme steps, long structured rows,aover 90 orders of magnitude, and errors. The new operators are also inCASES, the C derivative cases and the fuzzer.- The log barrier −λ Σ log zᵢ (
fp_op_log_barrier,LogBarrier,prox_log_barrier; Beck 2017, Lemma 6.5), stable for x < 0 and huge |x| or γλ; ℓ1 over a box (fp_op_l1_box,L1Box,prox_l1_box; Beck, Example 6.23, here for any interval and per-entry weights and bounds); and the projection onto the second-order cone with t first (fp_op_soc,SOC,project_soc; Beck, Example 6.37). All with derivatives; 0.7–0.9 ns per entry on Apple M5. - Group Huber, group SCAD and group MCP by norm composition (
fp_op_group_huber,fp_op_group_scad,fp_op_group_mcp,GroupHuber,GroupSCAD,GroupMCPand their functions; Beck, Theorem 6.18 and Example 6.66): each group is scaled by the scalar prox of its norm at the step γc_g, with groups and weights as for group ℓ2 and derivatives in x, γ, the scalar parameters and the group weights. The kernel wraps the scalar operator, so its formulas and kink rules are shared. Group SCAD and MCP check a > 1 + γ max c and b > γ max c at call time. Cost is that of group ℓ2 (about 3.5 ns per entry with group ids, 1 ns per entry on rows). tests/python/test_radial.py: stationarity of the log barrier over 9 orders of magnitude, ℓ1 over a box and the group penalties against minimisation on refined grids, the cone's KKT conditions and polar conjugate, Beck's closed form for group Huber, kink rules, NaN and infinity handling and errors. The new operators are also inCASES, the C derivative cases and the fuzzer.- Tree-structured group norms l₁‖z‖₁ + Σ_g η_g ‖z_g‖₂ for nested or disjoint groups (
fp_op_tree_l2,TreeL2,tree_soft_threshold), and the sparse group lasso as the case of a partition (TreeL2.sparse_group,sparse_group_soft_threshold). The prox composes soft thresholding and the group shrinks from the smallest group up (Bach, Jenatton, Mairal and Obozinski 2012, (3.8)). Groups come as CSR arrays in any order, and the tree condition is checked when the operator is built. Derivatives in x, γ, l₁ and the group weights follow the chain of shrinks. About 1 ns per entry for the sparse group lasso with groups of 16, and 8 ns for a depth-8 tree at n = 10⁶. - Projection onto the 1D TV ball {Σ wᵢ|zᵢ₊₁ − zᵢ| ≤ α} (
fp_op_tv1d_ball,TV1DBall,project_tv1d_ball; Beck 2017, Theorem 6.30). This is the 1D TV prox at the step where the TV equals α. Safeguarded Newton steps find that step: they start from γ = 0⁺, are taken in log–log scale while far from the root, and are exact on the final structure. Derivatives in x, α and the weights come by implicit differentiation of TV(z) = α. It takes 4–15 1D TV solves per row, 40–135 ns per entry on Apple M5. - 1D TV with the ℓ2 norm of the differences, the prox of γ(Σ wᵢ² (zᵢ₊₁ − zᵢ)²)^½ (
fp_op_tv1d_l2,TV1DL2,tv1d_l2). The dual is a trust-region problem. The result is the piecewise mean when the minimal dual, a cumulative sum, lies in the ball. Otherwise Newton's method finds the root of Moré and Sorensen's secular equation, starting from μ = 0 (Nocedal and Wright, Algorithm 4.4). Each of its 2–8 steps costs one tridiagonal factorisation, with pivots kept in a form free of cancellation, and the result is exact to rounding. Derivatives in x, γ and the weights are in closed form, by Sherman–Morrison on the tridiagonal Hessian. 30–90 ns per entry on Apple M5, 1.0–1.3× faster than proxTV'smore_TV2, which hits its iteration cap and returns wrong results on many large or unscaled rows. tests/python/test_tv1d_l2.py: agreement with a dense solver near the inside threshold too, with zero weights; an independently built dual point certifying the result up to n = 10⁵; n = 2 against 1D TV; shift, scale and reversal invariance; float32; the γ gradient against finite differences; errors. The operator is also inCASES, the C derivative cases and the fuzzer. Fuzzing found two problems. A weight whose square underflows has to count as zero. And each piece has to be centred on its first entry: otherwise the rounding of a constant piece's mean, divided by a tiny w², posed as a huge dual (NaN at w = 2·10⁻⁵³ in the nightly run).bench/compare_external.pygains the comparison with proxTV.tests/python/test_tree_ball.pycovers:- random trees against block coordinate descent on the dual, and order independence;
- the operators the tree norm generalises (group ℓ2, soft thresholding, the sparse group lasso);
- the TV ball on its sphere up to n = 10⁵, against bisection on the step, with zero weights;
- the projection inequality, special cases and the α gradient against finite differences;
- errors.
The new operators are also in CASES, the C derivative cases and the fuzzer.
- Examples for 0.2, run by the Python tests: examples/image_denoising.py (isotropic and anisotropic TV of images, gap certificates, warm starts on a γ sweep, a batch, and learning γ through TVIso.vjp) and examples/sparse_recovery.py (proximal gradient with ℓ1 against MCP, SCAD, ℓ0, ℓ1/2 and the log penalty on 64 recovery problems at once, against the oracle, and the tie rule), and examples/group_sparsity.py (lasso, group lasso, sparse group lasso, group MCP and SCAD on grouped regression with λ chosen on a validation set, and hierarchical sparsity with tree_soft_threshold).
Changed¶
- Isotropic TV restarts FISTA when the momentum points uphill (the gradient test of O'Donoghue and Candès 2015), checked every 4th iteration and never at a shorter interval than the previous restart. Solves to a gap of 1e-8 and below take up to 15× fewer iterations (64² noise at γ = 3 to 1e-10: about 26 000 → 1 500). At γ ≤ 0.3, looser solves are unchanged, while at γ = 3 they gain from 1e-4 on. Each iteration costs 1–4% more. Results stay bit-identical for any thread count.
- Anisotropic TV restarts its dual methods when the momentum points uphill (O'Donoghue and Candès), as isotropic TV does; its dual is a quadratic over a polyhedron, so the restarted methods converge linearly. The polish now takes the solution's regions from the dual: an edge whose 1D dual is strictly inside its bound is flat. It runs at the gap checks, tenfold drops of the gap apart, and ends the solve as soon as the polished point meets the tolerance with a gap at most 1/100 of the iterate's. The old polish ran once at the end and took its regions from jumps of z below a threshold, which merged small true jumps and could make the output worse. On 64³ volumes, the time to 1e-6 relative error falls 4.7–5.6× (now 1.8–4.8× faster than proxTV's Yang3 ADMM, which led there), and on 256² and 512² images 2.3–2.8×. Tight solves end at the exact solution to rounding. Some medium accuracies are 2–19% slower. Results stay bit-identical for any thread count, and a warm start from the dual of a polished solve stops at once. The polish needs 3 more doubles per entry of workspace (12 instead of 9).
ctx.jacobian_diag(branch=None, kink_tol=0.0)in Python, the diagonal of dz/dx for the elementwise operators:jvp(ctx, dx=ones)under its own name, honouring the branch override. For MCP it gives 0, 1 or b/(b − γwᵢ) per entry, which are the SCD subspaces a semismooth* Newton step reads. Operators whose Jacobian is not diagonal raiseValueError. The test overCASESchecks jvp(ctx, dx) = diag · dx for every elementwise operator.- Kink masks and branch overrides for soft thresholding, ℓ1 over a box, SCAD and MCP:
fp_workspace_kinks(ws, tol, mask, &count)reports which entries of a kept prox call lie withintol(absolute, in the input's units) of a breakpoint, with a code saying which one. The mask has the new dtypeFP_I8and is the same for any thread count.fp_workspace_set_branch(ws, side, tol)makesfp_jvp/fp_vjpdifferentiate the piece on the x − ε (−1) or x + ε (+1) side of each flagged breakpoint, with that piece's formula taken at x. These are the other elements of the B-subdifferential, for example both elements at a biactive entry, and with them each side's derivative matches its one-sided finite difference, in x, γ and θ.- In Python:
ctx.kinks(tol), andbranch=andkink_tol=onjvp/vjp. - Each map now has explicit pieces, so its default derivatives are bit-identical to before (checked on 64 arrays), and the derivative loops are as fast as before: the override is a separate instantiation.
- Tests: one-sided differences from both sides at every breakpoint, near-kink entries, the conjugate's units, strides and negative strides, threads, a pass with no allocation, and fuzzing of random overrides.
examples/weighted_glasso.py: the weighted graphical lasso by ADMM. The −log det step iseighplusLogBarrieron the eigenvalues, and the penalty step is weightedSoftor weightedMCPon the packed upper triangle. On 40 variables with 47 true edges and 120 samples, the graphical lasso keeps all but two edges only alongside 28 spurious ones (relative error 0.30). Adaptive weights cut the spurious edges to 6 and miss one more edge (error 0.22), and weighted MCP with the same weights lowers the error to 0.20. The samples are drawn through the Cholesky factor, so they are the same on every platform. The KKT residual of the convex solves is checked, and the Python tests run the example.- SCAD and MCP take per-entry weights, g(z) = Σ wᵢ ρ(zᵢ):
fp_op_scad(λ, a, weights, out)andfp_op_mcp(λ, b, weights, out)(a new argument, NULL for the unweighted map),SCAD(lam, a, weights),MCP(lam, b, weights), andweights=andaxis=onscadandmcp. Entry i is the unweighted map at the step γwᵢ (for MCP, wρ_{λ,b} = ρ_{wλ,b/w}). The step condition becomes a > 1 + γ max w or b > γ max w, the rule the group penalties already use. With weights θ = (λ, a or b, w…), and the VJP in w gives the hypergradient for learning, for example, edge weights. Without them θ stays (λ, a or b), and the maps are bit-identical to before at the same speed: the weighted case is a separate instantiation, so the unweighted loop loads no weight. Weighted maps cost about 1.0–1.3 ns per entry on Apple M5. A zero weight, or γ = 0, now returns the entry exactly: MCP's b·|x|/b did not, and its derivative there is now 1. - The polish of anisotropic TV runs in parallel. Its union-find works in fixed slabs along the first image axis, each joined by its own thread, and then joins the edges between slabs serially. Labels and region sums are also formed per slab. The slabs depend only on the shape, and the output is bit-identical to the serial polish for any thread count. Its edge pass also vectorises now. One polish on a 64³ volume takes 1.8 ms on eight threads instead of 3.9 (6.5 instead of 7.1 on one), and whole solves to 1e-12 are 3–15% faster on eight threads.
- The derivative CG of isotropic TV is preconditioned with the diagonal of the reduced system instead of the region sizes: 1.4–3× fewer iterations in the expensive solves (γ ≥ 0.3, tight tolerances), up to 40% more in cheap ones at small γ. The reported residual keeps its meaning, so
deriv_tolbehaves as before. - Anisotropic TV in 2D checks its gap on the second block step of each iteration, whose duals are feasible as they stand. A check is then one sweep over the image instead of an extra 1D TV pass, which cost about 60% of an iteration. Checks follow the gap: after iterations 1 and 2, then when its rate of fall predicts the tolerance, and at least every 4 iterations. Before, no solve stopped before iteration 4. A failed polish is retried early only when its ratio to the iterate's gap was at most 1/100 (in 2D, where a polish costs about 1.2 iterations; 3D keeps the eager retries). On 256² and 512² images at λ = 0.1, 1e-2 relative error is reached 1.8–2.0× sooner, now 1.6–1.7× faster than proxTV's DR2, which led there. 1e-3 is up to 22% faster and 1e-6 5–29% faster; 1e-4 at λ = 0.1 is 11–12% slower. The z returned is d − Σₐ qₐ for the dual returned, and the polish depends on the data and the dual alone, so a warm start from the dual of a solve still returns the same bits after 0 iterations. Warm starts also polish from their first check: on nearby images to 1e-6, 1–2 iterations instead of 4–12.
bench/compare_tv_aniso.pysweeps tolerances in quarter decades and proxTV's iteration caps in half powers of two.
Fixed¶
- Anisotropic TV used a warm-start dual without checking it, so an infeasible seed could certify a wrong point. For example, q₀ = x − mean(x) with the other blocks zero returned the constant image after 0 iterations as converged, with gap 0 and 57% error. A NaN dual left in the workspace by a NaN image made the next warm call run to
max_iterwith a NaN gap. Each fiber of a starting dual is now checked: its running sums must stay within γwₐ and end at 0, up to rounding. A fiber that fails is rebuilt from its clipped running sums. Feasible duals, including all duals from earlier calls, are used unchanged, so warm restarts stay bit-identical.
[0.1.0] — 2026-10-16¶
First release, on PyPI (pip install fastprox). Changes since 0.1.0rc2:
Added¶
-
variantsworkflow andbench/tv_variants.cpp: variants of the 1D TV kernel side by side against proxTV (classic, linearized, hybrid and weighted taut string), compiled into one binary and timed on the same inputs with the order rotated, on the arm64 runner and on x86_64 jobs. It runs on pushes tovariants/*branches or by hand.condattakes the length of its first, paper-form phase as a template parameter (kShortby default) so variants need no copy of the kernel. -
profileworkflow (manual dispatch): several identical jobs on GitHub's x86_64 runner, each labelled with the CPU it landed on. Each job profiles single-thread 1D TV against proxTV withbench/profile_kernels.cpp, which records hardware counters where the VM exposes them and rotates the solver order so that none benefits from branch history. It also summarises GCC's assembly of the kernels (conditional jumps against selects) withbench/asm_summary.py.
Documentation¶
examples/: basic usage, 1D TV denoising, proximal gradient (lasso and batched simplex least squares), derivatives checked against finite differences, and bilevel learning of TV weights through the VJP.tests/python/test_examples.pyruns them all; matplotlib for the plot is in theexamplesdependency group.docs/api.mdlists, for every operator, which Jacobian the derivatives use at kinks and ties. It explains why each choice is an element of the B-subdifferential, and that the x, γ and parameter derivatives together form one. The ℓ∞ prox and conjugate proxes reverse the thresholding rule through the Moreau identity.
Changed¶
bench/compare_external.pyrotates the order of the solvers with every repetition (fastprox's default solver always ran first, on an input just written, and its Condat path right after it), and quick mode takes the median of 7 repetitions instead of 3.- 1D TV: the per-call finiteness and range pass runs in 8 independent lanes with
fminnm/fmaxnmon arm64 (compare-selects elsewhere) instead of one dependent chain: 0.25 instead of 0.48 ns per sample with Clang and 0.89 with GCC on Apple M5 (float64, n = 10⁶). Weighted rows on white noise at λ = 10 went from 5.52 to 5.29 ns per sample, and float32 rows at λ = 0.1 are now 1–5% behind Condat's single-precision code (were 6–12%). - 1D TV: the branch-free bound updates in short segments of Condat's algorithm are written as min/max of the excess instead of selects on a comparison, which GCC compiled back into branches. Same arithmetic up to the sign of zero. With GCC 16 on Apple M5, 4–12% faster at λ = 0.1 and 5–27% faster at λ = 1 (uniform and weighted), within 3% of the Clang build at λ ≤ 1; at λ = 10, uniform rows lose 1–19% under GCC (random walk most), where the branches it emitted happened to predict well, and weighted rows gain up to 10%. Clang's code is unchanged.
-
Simplex and ℓ1 ball: the first pass of Condat's method skips blocks of 8 entries whose maximum is at or below the running pivot (the pivot can only change on an entry above it, so results are bit-identical). The ℓ1 norm that decides whether x is inside the ball is summed in 8 lanes instead of one dependent chain. On Apple M5 at n = 10⁶: simplex projection 0.50 instead of 0.60 ns per sample on Gaussian input, now faster than Condat's code (0.56); unweighted ℓ1 ball 0.64 instead of 1.08, weighted 1.08 instead of 1.37 (Clang) and 1.05 instead of 1.68 (GCC). The ℓ∞ prox shares the ℓ1-ball kernel.
-
x86-64: the min/max helpers behind 1D TV's bound updates and range pass and the simplex block maximum use SSE2
minsd/maxsdinstead of a compare-select, which GCC compiled into compare-and-branch. Same values. On GitHub's x86_64 runners (GCC 13.3, n = 10⁵), 1D TV went from fastest or within 2% of proxTV in 3–6 of 18 settings to 12–13 on Intel Xeons (8573C, 6973P-C) and from 14–17 to 17–18 on AMD EPYC; at λ = 1 fastprox now takes 0.82–1.03 of proxTV's time on Intel (was 1.01–1.16). Uniform random walk at λ = 10 lost 5–11% relative to proxTV, where the branches predicted well. -
1D TV: after the first 3 samples of a segment, Condat's algorithm now tracks the segment by its running sum. The lower bound is the running maximum of the candidates (s − λₖ)/m and the upper bound the running minimum of (s + λₖ)/m, so the clamps are min/max and the only value carried between steps is the sum, instead of a dependency chain through every clamp (same algorithm and structure; values differ at rounding level). On Apple M5 (n = 10⁵, single thread) the kernel is 1.3–2.9× faster at λ ≥ 1 and unchanged at λ = 0.1. Weighted white noise at λ = 10, the one setting where fastprox trailed proxTV on every machine, went from 1.03–1.09 of proxTV's time to 0.43–0.45 (Clang) and from 1.14 to 0.60 (GCC 16), and uniform random walk at λ = 10 from 0.99 to 0.64. On GitHub's runners (GCC 13.3): weighted white noise at λ = 10 from 1.12–1.14 to 0.73–0.78 on Intel Xeons, from 1.00–1.08 to 0.55–0.62 on AMD EPYC and from 1.22 to 0.92 on Neoverse-N2; uniform random walk at λ = 10 from 1.05–1.09 to 0.83–0.84 on Intel and from 1.19 to 1.06 on Neoverse-N2. At λ = 0.1 weighted rows lost about 3% on Intel. Long segments no longer use branches for the clamps, so
kBranchFree(8) is replaced bykShort(3).
Fixed¶
- Weighted ℓ1-ball projection with weights spanning many orders of magnitude could return outputs far larger than the input (z = [5.5e7, 2.4e70] for x = [11.0, 2.0], weights [1.8e-308, 7.7e-246] and radius 1e-300; found by fuzzing). Removing an entry within rounding of the pivot that dominated the running sums cancelled them. The threshold is now kept at least at the largest breakpoint left out of the support, as it is in exact arithmetic. The same guard is in the unweighted kernel.
[0.1.0rc2] — 2026-10-15¶
Fixed¶
- The macOS wheel of 0.1.0rc1 aborted the process (
OMP: Error #15) when PyTorch, or any package bundling a recent LLVM OpenMP runtime, was used in the same process: each wheel carried its own libomp, and the copies refuse to coexist.
Changed¶
- Rows run on fastprox's own thread pool (
src/core/parallel.cpp) instead of OpenMP. No OpenMP runtime is linked or bundled on any platform; the wheels depend only on the system and NumPy, and macOS wheels now support macOS 11.0 (arm64) and 10.15 (x86_64). Same results bit for bit; dynamic scheduling as before. Measured against the OpenMP build on Apple M5 in one process: equal on one thread, 1–8% slower at 2–4 threads on small batches, 8–31% faster at 8–15 threads. threads = 0meansfp_default_threads():FASTPROX_NUM_THREADS, else the first number inOMP_NUM_THREADS, else the CPUs the process may use (CPU affinity on Linux). Concurrent callers do not oversubscribe: one uses the pool, the others run serially. A child afterfork()builds its own pool.fp_has_openmp()andfastprox.has_openmp()are replaced byfp_default_threads()andfastprox.default_threads(); the CMake optionFASTPROX_OPENMPis nowFASTPROX_THREADS.- CI: a ThreadSanitizer job; AddressSanitizer and Valgrind now run with threads.
[0.1.0rc1] — 2026-10-15¶
First release candidate, on PyPI (pip install --pre fastprox).
Added¶
- Plain-C API (
include/fastprox.h) over a C++17 core: opaque operator and workspace handles,fp_prox,fp_prox_conj,fp_jvp,fp_vjp, error codes with every exception caught at the boundary. - Operators: soft thresholding (weighted), elastic net, Huber, group ℓ2 and ℓ2 norm, box, nonnegative orthant, ℓ2 ball, simplex, weighted ℓ1 ball, ℓ∞ norm, isotonic regression, and 1D TV (Condat's direct algorithm and taut string, edge weights).
- JVP and VJP in the input, the step and the operator parameters for every operator.
- Batching over any axis of strided n-d arrays, OpenMP parallelism with bit-identical results for any thread count, and allocation-free calls with a workspace.
- Python package built with nanobind (abi3, CPython ≥ 3.12): one-shot functions and operator classes with
prox,prox_conj,jvpandvjp. - C/C++ and Python test suites, a benchmark script, and a CI workflow.
- Release pipeline: sdist job, trusted publishing to TestPyPI (manual dispatch with
publish) and to PyPI (tagsv*, checked against the package version); PyPI metadata and a README for the project page; pre-release tags throughFASTPROX_VERSION_SUFFIXinCMakeLists.txt; Python tests also run on CPython 3.14. - Fuzz harness for the whole API (libFuzzer target and standalone driver) with a nightly workflow; CVXPY + Clarabel reference fixtures; benchmarks against proxTV and Condat's code (
bench/compare_external.py,docs/benchmarks.md); API reference (docs/api.md); Valgrind CI job.
Changed¶
- 1D TV: the Condat path falls back to the taut string after 3n + 1024 rescanned steps (was 16n + 1024 steps in total), which makes adversarial inputs such as ramps about 3.5× cheaper without affecting typical signals.
- 1D TV: the bound updates of Condat's algorithm are branch-free selects with a table of reciprocals, 25–35% faster on noisy signals (same arithmetic, so the same results).
- 1D TV: weighted problems now use Condat's direct algorithm, generalised to per-edge weights (radii precomputed per piece), with the same budgeted fallback to the taut string;
FP_TV1D_CONDATaccepts weights. Weighted rows went from 1.4–2.8× slower than proxTV's weighted taut string to faster in most settings. - 1D TV: radii that can never be active (above the dual bound j · (max x − min x)) are clamped, and when no edge can be active the result is the constant mean. Extreme weights or steps no longer cost accuracy: the residual stays within 10 n ε ‖x‖∞.
- 1D TV: the taut string stores its two chains as segments (length, rise, cached slope) in coordinates local to the current knot, an idea taken from proxTV's classic taut string. It is 17–26% faster and needs no compensated sums: the cumulative sum of the signal is never formed.
- Unweighted simplex and ℓ1-ball projections keep candidate values instead of indices (about 30% faster). The simplex also tests finiteness inside its pivot pass instead of a separate pass (a further 19%), and the ℓ1 ball and ℓ∞ prox reuse their ℓ1 norm as the test.
- 1D TV: bound updates are branch-free only in the first 8 samples of a segment; weighted rows read their radii directly when none can need clamping; operator construction makes one pass over the weights.
- Workspace scratch is no longer zero-filled, and the finiteness check is a branch-free pass: one-shot calls on large rows are noticeably faster.
- The version is defined once, in
CMakeLists.txt; the Python package reads it from there.
Fixed¶
- Weighted ℓ1-ball projection returned infinities for tiny weights (around 1e-279) because sums of squared weights underflowed (found by fuzzing). Weights are now normalised by their maximum, and ratios below 1e-100 are rejected.
fp_prox_conjwith σ = 0 on arrays with negative strides computed byte offsets in unsigned arithmetic (undefined behaviour, found by fuzzing).- Static Windows builds marked API symbols
dllexport. - The taut string kept cumulative sums in plain doubles and missed the 10 n ε ‖x‖∞ accuracy bound on long rows; its chains now use local coordinates.
- A test assumed weighted isotonic regression is firmly nonexpansive in the Euclidean norm; it is so in the weighted norm, which the test now uses.