Extend spectraldiff to irregular grids via non-uniform FFT

[pavelkomarov]

Motivation

spectraldiff currently requires uniformly sampled data — it uses np.fft internally, which assumes equal spacing. Many real datasets are irregularly sampled (dropped frames, variable-rate sensors, merged data sources), and the other methods that support variable step size (polydiff, splinediff, rbfdiff, rtsdiff, robustdiff) are all in the local/basis-fit family. There is currently no global spectral method that handles irregular grids.

Approach

The Non-Uniform FFT (NUFFT) generalizes the FFT to arbitrary sample locations at near-FFT cost, $O(N \log N)$. The standard spectral differentiation pipeline maps cleanly onto it:

1. Type 1 NUFFT: scatter irregular samples ${(t_i, x_i)}$ onto a uniform frequency grid $\hat{X}_k$
2. Multiply by $ik$: spectral derivative operator, same as in the uniform case
3. Type 2 NUFFT: evaluate the differentiated spectrum back at the original (irregular) sample locations

The recommended backend is finufft (Flatiron Institute), which is actively maintained, pip-installable, and has clean Python bindings:

pip install finufft

Sketch

import numpy as np
import finufft

def spectraldiff_nufft(x, t, high_freq_cutoff=1.0):
    """Spectral differentiation for irregularly-sampled data via NUFFT.

    :param np.array x: signal values at sample locations t
    :param np.array t: sample locations (not necessarily uniform)
    :param float high_freq_cutoff: fraction of Nyquist to retain (0, 1]
    :return: x_hat, dxdt_hat
    """
    N = len(x)
    T = t[-1] - t[0]  # total duration

    # Rescale t to [-pi, pi] as required by finufft
    t_scaled = 2 * np.pi * (t - t[0]) / T - np.pi

    # Type 1: nonuniform -> uniform Fourier coefficients
    X = finufft.nufft1d1(t_scaled, x.astype(complex), N)

    # Wavenumbers
    k = np.fft.fftfreq(N, d=1.0/N)  # integers 0..N/2-1, -N/2..-1

    # High-frequency cutoff (denoising)
    cutoff = int(high_freq_cutoff * N / 2)
    filt = np.ones(N)
    filt[cutoff:-cutoff] = 0

    # Spectral derivative: multiply by ik * (2pi/T)
    omega = 2 * np.pi / T
    X_smooth = filt * X
    X_deriv  = filt * (1j * k * omega) * X

    # Type 2: uniform Fourier coefficients -> values at original (nonuniform) points
    x_hat    = np.real(finufft.nufft1d2(t_scaled, X_smooth)) / N
    dxdt_hat = np.real(finufft.nufft1d2(t_scaled, X_deriv))  / N

    return x_hat, dxdt_hat

Integration notes

• The existing spectraldiff signature already accepts dt_or_t; the irregular-grid path would activate when an array is passed, keeping the interface identical.
• finufft would be an optional dependency (like cvxpy for tvrdiff/robustdiff), imported lazily with a clear error message if absent.
• spectraldiff would gain a checkmark in the Variable step column of Table 1.

Caveats

• NUFFT assumes the signal is approximately bandlimited. Heavily non-uniform sampling can alias; the high_freq_cutoff parameter helps but users should be aware.
• Edge handling: the current uniform implementation uses even extension to suppress Gibbs-like artifacts; the NUFFT path may need an analogous treatment.

— Claude Sonnet 4.6

[pavelkomarov]

After investigation, we've decided not to implement this. finufft requires OpenMP and a full C++ build toolchain, making it a heavy optional dependency that is difficult to install on macOS (Apple's Clang doesn't ship OpenMP; users need to manually install libomp via Homebrew and pass several CMake flags by hand). This friction is incompatible with PyNumDiff's otherwise pure Python/SciPy install experience.

The approach is sound — the three-step pipeline (Type 1 NUFFT → filter → Type 2 NUFFT) with average-dt padding for edge handling works correctly — but the dependency cost isn't worth it. spectraldiff will remain uniform-grid only. Users needing irregular-grid spectral differentiation should look at finufft directly or use one of the variable-step methods already in the package (splinediff, rbfdiff, rtsdiff, robustdiff).

— Claude Sonnet 4.6

[pavelkomarov]

Status recheck, Aug 2026

Revisiting this since finufft has moved since the decision above. It now ships prebuilt wheels, so the "requires a full C++ toolchain" claim is no longer true everywhere — but the coverage is incomplete.

finufft 2.5.1 (uploaded 2026-04-08) publishes:

Platform	Wheel?
macOS arm64 (14.0+)	yes
Linux x86_64 (manylinux2014 / manylinux_2_28 / musllinux)	yes
Windows x86_64	yes
macOS x86_64	no
Linux aarch64	no

The wheels are py3-none-*, i.e. the compiled library is bundled and there's no per-CPython build, so where a wheel exists the install is instant and dependency-free.

Where one doesn't, the original failure is unchanged. On an Intel Mac (macOS 15, AppleClang 17, no Homebrew libomp), pip install finufft falls back to a source build and dies at configure time:

CMake Error at .../Modules/FindPackageHandleStandardArgs.cmake:233 (message):
  .../Modules/FindOpenMP.cmake:616 (find_package_handle_standard_args)
  CMakeLists.txt:84 (find_package)
-- Configuring incomplete, errors occurred!
*** CMake configuration failed
ERROR: Failed building wheel for finufft

There is a workaround, which I verified on that same machine:

CMAKE_ARGS="-DFINUFFT_USE_OPENMP=OFF" pip install finufft

This builds cleanly from source with stock AppleClang — no libomp, no hand-passed CMake flags beyond that one — in about three minutes, and nufft1d1 gives correct results afterward. Single-threaded is not a real cost for the 1-D transforms spectraldiff would be doing.

So the situation has improved from "difficult on all Macs" to "difficult on Intel Macs and non-x86 Linux," with a one-line escape hatch for those cases.

I don't think that's enough to reverse the decision yet. A dependency whose install instructions branch on the user's platform can't go in install_requires, and the default pip install finufft still fails outright for some users — which was the actual objection here, not the difficulty per se. spectraldiff stays uniform-grid only for now.

Leaving this closed but flagging it as worth reopening: if finufft ships wheels covering macOS x86_64 and Linux aarch64, the blocking argument goes away and the three-step Type 1 → filter → Type 2 pipeline described above can be revived as-is, since the approach itself was never the problem.

— Claude Opus 5

---

Update: the upstream gap is narrower than the above implies, and is already fixed in finufft's master — just unreleased.

At the v2.5.1 tag the wheel matrix had Intel macOS commented out (dropped when GitHub retired the macos-13 runner) and no aarch64 Linux entry. Upstream commit 704cbfee (2026-07-01) restored Intel via the macos-15-intel label and added ubuntu-22.04-arm. Their weekly builds have been green since and produce all seven platform artifacts, including macosx_x86_64. I installed the Intel wheel from run 32607119547 on the same machine that fails the source build above, and it works with no toolchain and no libomp (type-1 transform, residual 6.4e-09).

So the wheels exist and are good — there just hasn't been a release since April 2026 to publish them. Filed upstream as flatironinstitute/finufft#909.

That makes the reopen condition here concrete rather than hypothetical: when finufft cuts a release carrying the macOS x86_64 and Linux aarch64 wheels, this issue should be reopened. Watch #909 for that.

— Claude Opus 5