Skip to content

NUFFT

torchlinops.linops.NUFFT

Bases: NUFFTBase

Non-uniform Fast Fourier Transform (type II) as a named linear operator.

Implemented as a Chain of zero-padding, FFT, and interpolation. Supports forward (image-to-kspace) and adjoint (kspace-to-image) operations.

ATTRIBUTE DESCRIPTION
**options

oversamp : float Oversampling factor for fourier domain grid width : float Width of kernel to use for interpolation skip_prep_locs : bool Flag for skipping scaling/shifting/etc of locs toeplitz : bool If True, normal() performs toeplitz embedding calculation toeplitz_dtype : torch.dtype Data type for the toeplitz embedding. Probably should be torch.complex64

TYPE: dict

Source code in src/torchlinops/linops/nufft/nufft.py
class NUFFT(NUFFTBase):
    """Non-uniform Fast Fourier Transform (type II) as a named linear operator.

    Implemented as a ``Chain`` of zero-padding, FFT, and interpolation. Supports
    forward (image-to-kspace) and adjoint (kspace-to-image) operations.

    Attributes
    ----------
    **options : dict
        oversamp : float
            Oversampling factor for fourier domain grid
        width : float
            Width of kernel to use for interpolation
        skip_prep_locs : bool
            Flag for skipping scaling/shifting/etc of locs
        toeplitz : bool
            If True, normal() performs toeplitz embedding calculation
        toeplitz_dtype : torch.dtype
            Data type for the toeplitz embedding. Probably should be torch.complex64
    """

    default_options: ClassVar[dict] = {
        "oversamp": 1.25,
        "width": 4.0,
        "toeplitz": False,
        "toeplitz_dtype": torch.complex64,
    }

    def __init__(self, *args, **kwargs):
        if "mode" in kwargs:
            raise ValueError(
                f"`mode` parameter was deprecated. Must now explicitly choose torchlinops.SamplingNUFFT or torchlinops.NUFFT."
            )
        super().__init__(*args, **kwargs)

    @property
    def padded_size(self):
        return tuple(int(i * self.options["oversamp"]) for i in self.grid_size)

    def build(self):
        grid_size = self.grid_size
        ndim = len(self.grid_size)
        padded_size = self.padded_size
        if self.options.get("skip_prep_locs"):
            locs_prepared = self.locs
        else:
            if config.cache_nufft_parameters:
                locs_prepared = self.prep_locs(self.locs, self.grid_size, padded_size)
            else:
                locs_prepared = self.prep_locs.__wrapped__(
                    self.locs, self.grid_size, padded_size
                )
        self.locs_prepared = locs_prepared
        pad = Pad(
            padded_size,
            self.grid_size,
            in_shape=self.input_shape,
            batch_shape=self.batch_shape,
        )

        # Create FFT
        fft = FFT(
            ndim=ndim,
            centered=True,
            batch_shape=self.batch_shape,
            grid_shapes=(pad.out_im_shape, self.input_kshape),
        )

        # Create Apodization
        width, oversamp = self.options["width"], self.options["oversamp"]
        beta = self.beta(width, oversamp)
        if config.cache_nufft_parameters:
            weight = self.apodize_weights(grid_size, padded_size, width, beta)
        else:
            weight = self.apodize_weights.__wrapped__(
                grid_size, padded_size, width, beta
            )
        if weight.isnan().any() or weight.isinf().any():
            raise ValueError(
                f"Nan/Inf values detected in apodization weight (width={width}, oversamp={oversamp})."
            )
        batched_input_shape = NS(self.batch_shape) + NS(self.input_shape)
        apodize = Diagonal(weight.to(locs_prepared.device), batched_input_shape.ishape)
        apodize.name = "Apodize"

        # Create Interpolator
        interp = Interpolate(
            locs_prepared,
            padded_size,
            batch_shape=self.batch_shape,
            locs_batch_shape=self.output_shape,
            grid_shape=self.input_kshape,
            width=width,
            kernel="kaiser_bessel",
            kernel_params={"beta": beta},
        )
        # Create scaling
        scale_factor = width**ndim * (prod(grid_size) / prod(padded_size)) ** 0.5
        scale = Scalar(weight=1.0 / scale_factor, ioshape=interp.oshape)
        linops = [apodize, pad, fft, interp, scale]
        return linops

    @staticmethod
    @lru_cache(maxsize=64)
    def prep_locs(
        locs: Shaped[Tensor, "... D"],
        grid_size: tuple,
        padded_size: tuple,
        pad_mode: Literal["zero", "circular"] = "circular",
    ):
        """
        Parameters
        ----------
        locs : Shaped[Tensor, "... D"]
            Input tensor representing locations in the grid. The last dimension corresponds to spatial dimensions.
            Range is [-N//2, N//2]
        grid_size : tuple
            The original size of the grid before padding.
        padded_size : tuple
            The size of the grid after padding.
        pad_mode : Literal["zero", "circular"], optional
            The type of padding applied. Can be "zero" for zero-padding or "circular" for circular padding.
            Default is "circular".
        Returns
        -------
        Shaped[Tensor, "... D"]
            Adjusted locations tensor in [0, padded_size - 1], float dtype.

        Raises
        ------
        ValueError
            If an unrecognized `pad_mode` is provided.

        Examples
        --------
        >>> _ = torch.manual_seed(0);
        >>> locs = torch.rand(1000, 3) * 64 - 32 # [-32, 32]
        >>> locs.min()
        tensor(-31.9949)
        >>> locs.max()
        tensor(31.9896)
        >>> grid_size = (64, 64, 64)
        >>> padded_size = (80, 80, 80) # oversamp = 1.25
        >>> locs_scaled_shifted = NUFFT.prep_locs(locs, grid_size, padded_size)
        >>> locs_scaled_shifted.min()
        tensor(0.0064)
        >>> locs_scaled_shifted.max()
        tensor(79.9871)

        Notes
        -----
        - Assumes that the input `locs` are centered.
        - Adjusts the locations by scaling and shifting them according to the grid and padded sizes.
        - Applies clamping or remainder operations based on the padding mode.
        """
        # Clone to prevent in-place scaling from modifying the original
        out = locs.clone()
        padded_size = torch.as_tensor(padded_size, device=out.device)
        grid_size = torch.as_tensor(grid_size, device=out.device)
        out = out * padded_size / grid_size
        out += padded_size // 2
        if pad_mode == "zero":
            out = clamp(out, 0, padded_size - 1)
        elif pad_mode == "circular":
            out = torch.remainder(out, padded_size)
        else:
            raise ValueError(f"Unrecognized padding mode during prep: {pad_mode}")
        return out

    @staticmethod
    @lru_cache(maxsize=64)
    def apodize_weights(grid_size, padded_size, width: float, beta: float):
        grid_size = torch.tensor(grid_size)
        padded_size = torch.tensor(padded_size)
        grid = torch.meshgrid(*(torch.arange(s) for s in grid_size), indexing="ij")
        grid = torch.stack(grid, dim=-1)

        # Sigpy compatibility
        apod = (
            beta**2 - (torch.pi * width * (grid - grid_size // 2) / padded_size) ** 2
        ) ** 0.5
        apod /= torch.sinh(apod)

        # Beatty paper
        # apod = (torch.pi * width * (grid - grid_size // 2) / padded_size) ** 2 - beta**2
        # print(apod)
        apod = torch.prod(apod, dim=-1)
        return apod

__init__

__init__(*args, **kwargs)
Source code in src/torchlinops/linops/nufft/nufft.py
def __init__(self, *args, **kwargs):
    if "mode" in kwargs:
        raise ValueError(
            f"`mode` parameter was deprecated. Must now explicitly choose torchlinops.SamplingNUFFT or torchlinops.NUFFT."
        )
    super().__init__(*args, **kwargs)

prep_locs cached staticmethod

prep_locs(
    locs: Shaped[Tensor, "... D"],
    grid_size: tuple,
    padded_size: tuple,
    pad_mode: Literal["zero", "circular"] = "circular",
)
PARAMETER DESCRIPTION
locs

Input tensor representing locations in the grid. The last dimension corresponds to spatial dimensions. Range is [-N//2, N//2]

TYPE: Shaped[Tensor, '... D']

grid_size

The original size of the grid before padding.

TYPE: tuple

padded_size

The size of the grid after padding.

TYPE: tuple

pad_mode

The type of padding applied. Can be "zero" for zero-padding or "circular" for circular padding. Default is "circular".

TYPE: Literal['zero', 'circular'] DEFAULT: 'circular'

RETURNS DESCRIPTION
Shaped[Tensor, '... D']

Adjusted locations tensor in [0, padded_size - 1], float dtype.

RAISES DESCRIPTION
ValueError

If an unrecognized pad_mode is provided.

Examples:

>>> _ = torch.manual_seed(0);
>>> locs = torch.rand(1000, 3) * 64 - 32 # [-32, 32]
>>> locs.min()
tensor(-31.9949)
>>> locs.max()
tensor(31.9896)
>>> grid_size = (64, 64, 64)
>>> padded_size = (80, 80, 80) # oversamp = 1.25
>>> locs_scaled_shifted = NUFFT.prep_locs(locs, grid_size, padded_size)
>>> locs_scaled_shifted.min()
tensor(0.0064)
>>> locs_scaled_shifted.max()
tensor(79.9871)
Notes
  • Assumes that the input locs are centered.
  • Adjusts the locations by scaling and shifting them according to the grid and padded sizes.
  • Applies clamping or remainder operations based on the padding mode.
Source code in src/torchlinops/linops/nufft/nufft.py
@staticmethod
@lru_cache(maxsize=64)
def prep_locs(
    locs: Shaped[Tensor, "... D"],
    grid_size: tuple,
    padded_size: tuple,
    pad_mode: Literal["zero", "circular"] = "circular",
):
    """
    Parameters
    ----------
    locs : Shaped[Tensor, "... D"]
        Input tensor representing locations in the grid. The last dimension corresponds to spatial dimensions.
        Range is [-N//2, N//2]
    grid_size : tuple
        The original size of the grid before padding.
    padded_size : tuple
        The size of the grid after padding.
    pad_mode : Literal["zero", "circular"], optional
        The type of padding applied. Can be "zero" for zero-padding or "circular" for circular padding.
        Default is "circular".
    Returns
    -------
    Shaped[Tensor, "... D"]
        Adjusted locations tensor in [0, padded_size - 1], float dtype.

    Raises
    ------
    ValueError
        If an unrecognized `pad_mode` is provided.

    Examples
    --------
    >>> _ = torch.manual_seed(0);
    >>> locs = torch.rand(1000, 3) * 64 - 32 # [-32, 32]
    >>> locs.min()
    tensor(-31.9949)
    >>> locs.max()
    tensor(31.9896)
    >>> grid_size = (64, 64, 64)
    >>> padded_size = (80, 80, 80) # oversamp = 1.25
    >>> locs_scaled_shifted = NUFFT.prep_locs(locs, grid_size, padded_size)
    >>> locs_scaled_shifted.min()
    tensor(0.0064)
    >>> locs_scaled_shifted.max()
    tensor(79.9871)

    Notes
    -----
    - Assumes that the input `locs` are centered.
    - Adjusts the locations by scaling and shifting them according to the grid and padded sizes.
    - Applies clamping or remainder operations based on the padding mode.
    """
    # Clone to prevent in-place scaling from modifying the original
    out = locs.clone()
    padded_size = torch.as_tensor(padded_size, device=out.device)
    grid_size = torch.as_tensor(grid_size, device=out.device)
    out = out * padded_size / grid_size
    out += padded_size // 2
    if pad_mode == "zero":
        out = clamp(out, 0, padded_size - 1)
    elif pad_mode == "circular":
        out = torch.remainder(out, padded_size)
    else:
        raise ValueError(f"Unrecognized padding mode during prep: {pad_mode}")
    return out

torchlinops.linops.FastSamplingNUFFT

Bases: SamplingNUFFT

Non-uniform FFT (type II, sampling mode) without the FFT shift sandwich.

SamplingNUFFT builds [Pad, FFT(centered=True), Sampling]. The centered FFT copies the full grid 3x per axis (ifftshift/fftshift rolls), in forward and again through autograd's backward. This subclass applies the shift theorem instead: it runs a plain fftn on the padded grid and folds the centering into the gather indices plus a per-sample complex phase, precomputed once per trajectory:

fftshift(fftn(ifftshift(x)))[l] = S(k) * fftn(x)[k],
k = (l - N//2) mod N,
S(k) = exp(-2j*pi * sum_d k_d * ((N_d + 1)//2) / N_d)

For all-even padded sizes S reduces to the parity sign (-1)**sum_d k_d. Computes the same operator as SamplingNUFFT (to complex64 rounding); inherits prep_locs, device, and options.

The centering phase lives at either end of the gather, selectable via the phase_placement option (issue #210):

  • "samples" — phase Diagonal after Sampling (per-sample phase): O(nlocs) multiplies forward+backward.
  • "grid" — per-axis broadcast Diagonals on the uncentered fftn grid before Sampling: O(prod padded_size) multiplies forward+backward, O(sum N_d) storage.
  • "auto" (default) — "grid" iff the sample count exceeds prod(padded_size). resolved at build time, recorded as self.phase_placement_resolved.

Both placements compute the same operator: the unit-modulus phase commutes with the gather.

Source code in src/torchlinops/linops/nufft/fast_sampling_nufft.py
class FastSamplingNUFFT(SamplingNUFFT):
    """Non-uniform FFT (type II, sampling mode) without the FFT shift sandwich.

    ``SamplingNUFFT`` builds ``[Pad, FFT(centered=True), Sampling]``. The centered
    FFT copies the full grid 3x per axis (ifftshift/fftshift rolls), in forward
    and again through autograd's backward. This subclass applies the shift
    theorem instead: it runs a plain ``fftn`` on the padded grid and folds the
    centering into the gather indices plus a per-sample complex phase,
    precomputed once per trajectory:

        fftshift(fftn(ifftshift(x)))[l] = S(k) * fftn(x)[k],
        k = (l - N//2) mod N,
        S(k) = exp(-2j*pi * sum_d k_d * ((N_d + 1)//2) / N_d)

    For all-even padded sizes ``S`` reduces to the parity sign
    ``(-1)**sum_d k_d``. Computes the same operator as ``SamplingNUFFT`` (to
    complex64 rounding); inherits ``prep_locs``, ``device``, and options.

    The centering phase lives at either end of the gather, selectable via the
    ``phase_placement`` option (issue #210):

    - ``"samples"`` — phase ``Diagonal`` after ``Sampling`` (per-sample
      phase): ``O(nlocs)`` multiplies forward+backward.
    - ``"grid"`` — per-axis broadcast ``Diagonal``s on the uncentered fftn
      grid before ``Sampling``: ``O(prod padded_size)`` multiplies
      forward+backward, ``O(sum N_d)`` storage.
    - ``"auto"`` (default) — ``"grid"`` iff the sample count
      exceeds ``prod(padded_size)``.
      resolved at build time, recorded as ``self.phase_placement_resolved``.

    Both placements compute the same operator: the unit-modulus phase
    commutes with the gather.
    """

    default_options: ClassVar[dict] = {
        **SamplingNUFFT.default_options,
        "phase_placement": "auto",
    }

    @staticmethod
    def resolve_phase_placement(
        phase_placement: str, nlocs: int, padded_size: tuple[int, ...]
    ) -> str:
        """Resolve the ``phase_placement`` option to a concrete placement.

        Parameters
        ----------
        phase_placement : str
            One of ``"samples"``, ``"grid"``, ``"auto"``.
        nlocs : int
            Number of gathered sample points.
        padded_size : tuple[int, ...]
            Oversampled grid size, one entry per spatial axis.

        Returns
        -------
        str
            ``"grid"`` iff ``nlocs > prod(padded_size)`` when ``"auto"``
            (ties resolve to ``"samples"``); otherwise the literal
            ``"samples"``/``"grid"``.

        Raises
        ------
        ValueError
            If ``phase_placement`` is unrecognized.
        """
        if phase_placement == "auto":
            return "grid" if nlocs > math.prod(padded_size) else "samples"
        if phase_placement in ("samples", "grid"):
            return phase_placement
        raise ValueError(
            f"phase_placement must be 'samples', 'grid', or 'auto' but got "
            f"{phase_placement!r}"
        )

    def build(self):
        ndim = len(self.grid_size)
        padded_size = tuple(int(i * self.options["oversamp"]) for i in self.grid_size)
        self.phase_placement_resolved = self.resolve_phase_placement(
            self.options["phase_placement"],
            math.prod(self.locs.shape[:-1]),
            padded_size,
        )

        # Inherited, cached locs preparation: l_p = centered gather indices
        if config.cache_nufft_parameters:
            locs_prepared = self.prep_locs(self.locs, self.grid_size, padded_size)
        else:
            locs_prepared = self.prep_locs.__wrapped__(
                self.locs, self.grid_size, padded_size
            )

        pad = Pad(
            padded_size,
            self.grid_size,
            in_shape=self.input_shape,
            batch_shape=self.batch_shape,
        )

        # Plain (uncentered) FFT: no shift sandwich anywhere in the chain
        fft = FFT(
            ndim=ndim,
            centered=False,
            batch_shape=self.batch_shape,
            grid_shapes=(pad.out_im_shape, self.input_kshape),
        )

        grid_shape = fft._shape.output_grid_shape
        # Uncentered gather indices: idx = (l_p - N//2) mod N, identical for
        # both placements; for "samples" the phase comes from fold_centering.
        size = torch.tensor(
            padded_size, dtype=locs_prepared.dtype, device=locs_prepared.device
        )
        idx = ifftshift_locs(locs_prepared, size)
        sampling = Sampling.from_stacked_idx(
            idx,
            dim=-1,
            input_size=padded_size,
            output_shape=self.output_shape,
            input_shape=grid_shape,
            batch_shape=self.batch_shape,
        )

        if self.phase_placement_resolved == "samples":
            # Cached fold: per-sample centering phase on the gathered output;
            # broadcasts over batch dims. Unit modulus -> adjoint/normal exact.
            if config.cache_nufft_parameters:
                phase = FastSamplingNUFFT.fold_centering(locs_prepared, padded_size)
            else:
                phase = FastSamplingNUFFT.fold_centering.__wrapped__(
                    locs_prepared, padded_size
                )
            oshape = NS(self.batch_shape) + NS(self.output_shape)
            phase_diag = Diagonal(phase, oshape.ishape)
            phase_diag.name = "FoldedCenteringPhase"
            return [pad, fft, sampling, phase_diag]
        # Grid placement: the same phase applied on the full uncentered fftn
        # grid as D per-axis broadcast Diagonals BEFORE the gather
        phase_diags = FastSamplingNUFFT.grid_phase_diags(
            padded_size,
            grid_shape,
            self.batch_shape,
            device=locs_prepared.device,
        )
        return [pad, fft, *phase_diags, sampling]

    @staticmethod
    def grid_phase_ramps(padded_size: tuple[int, ...], device=None) -> list[Tensor]:
        """Per-axis phase ramps for the uncentered fftn output grid.

        Parameters
        ----------
        padded_size : tuple[int, ...]
            Oversampled grid size, one entry per spatial axis.
        device : torch.device, optional

        Returns
        -------
        list[Tensor]
            D complex64 tensors of shape ``(N_d,)``:
            ``R_d[m] = exp(-2j*pi*m*rolls_d/N_d)``, ``rolls_d = (N_d+1)//2``.
            Parity sign ``(-1)**m`` on even axes. Unit modulus.
            Stored factored: the full-grid outer product ``R_1 * ... * R_D``
            (``prod(padded_size)`` entries) is never materialized; applying
            the ramps in sequence yields it exactly.
        """
        ramps = []
        for n in padded_size:
            rolls = (n + 1) // 2
            m = torch.arange(n, dtype=torch.float32, device=device)
            ramps.append(torch.exp(-2j * torch.pi * m * rolls / n))
        return ramps

    @staticmethod
    def grid_phase_diags(padded_size, grid_shape, batch_shape, device=None):
        """Broadcast Diagonals applying the grid phase, one per axis."""
        ndim = len(padded_size)
        oshape = NS(batch_shape) + NS(grid_shape)
        diags = []
        ramps = FastSamplingNUFFT.grid_phase_ramps(padded_size, device=device)
        for d, (ramp, n) in enumerate(zip(ramps, padded_size)):
            # Broadcast over all other grid axes (and any batch dims); torch
            # broadcasting keeps this a per-axis multiply, never O(prod N).
            weight = ramp.view((1,) * d + (n,) + (1,) * (ndim - 1 - d))
            broadcast_dims = tuple(grid_shape[i] for i in range(ndim) if i != d)
            diag = Diagonal(weight, oshape.ishape, broadcast_dims=broadcast_dims)
            diag.name = f"GridPhase{d}"
            diags.append(diag)
        return diags

    @staticmethod
    @lru_cache(maxsize=64)
    def fold_centering(
        locs_prepared: Integer[Tensor, "... D"],
        padded_size: tuple[int, ...],
    ) -> Tensor:
        """Fold the centered-FFT sandwich into plain-FFT gather indices + phase.

        Parameters
        ----------
        locs_prepared : Integer[Tensor, "... D"]
            Output of ``SamplingNUFFT.prep_locs`` (centered gather indices in
            ``[0, N_d - 1]``), dtype int64.
        padded_size : tuple[int, ...]
            Oversampled grid size, one entry per spatial axis.

        Returns
        -------
        phase : Tensor
            complex64 tensor of shape ``locs_prepared.shape[:-1]``: per-sample
            unit-modulus phase ``S(k)``.
        """
        size = torch.tensor(
            padded_size, dtype=locs_prepared.dtype, device=locs_prepared.device
        )
        idx = ifftshift_locs(locs_prepared, size)
        rolls = (size + 1) // 2
        angle = (
            idx.to(torch.float32) * rolls.to(torch.float32) / size.to(torch.float32)
        ).sum(dim=-1)
        phase = torch.exp(-2j * torch.pi * angle)
        return phase

fold_centering cached staticmethod

fold_centering(
    locs_prepared: Integer[Tensor, "... D"],
    padded_size: tuple[int, ...],
) -> Tensor

Fold the centered-FFT sandwich into plain-FFT gather indices + phase.

PARAMETER DESCRIPTION
locs_prepared

Output of SamplingNUFFT.prep_locs (centered gather indices in [0, N_d - 1]), dtype int64.

TYPE: Integer[Tensor, '... D']

padded_size

Oversampled grid size, one entry per spatial axis.

TYPE: tuple[int, ...]

RETURNS DESCRIPTION
phase

complex64 tensor of shape locs_prepared.shape[:-1]: per-sample unit-modulus phase S(k).

TYPE: Tensor

Source code in src/torchlinops/linops/nufft/fast_sampling_nufft.py
@staticmethod
@lru_cache(maxsize=64)
def fold_centering(
    locs_prepared: Integer[Tensor, "... D"],
    padded_size: tuple[int, ...],
) -> Tensor:
    """Fold the centered-FFT sandwich into plain-FFT gather indices + phase.

    Parameters
    ----------
    locs_prepared : Integer[Tensor, "... D"]
        Output of ``SamplingNUFFT.prep_locs`` (centered gather indices in
        ``[0, N_d - 1]``), dtype int64.
    padded_size : tuple[int, ...]
        Oversampled grid size, one entry per spatial axis.

    Returns
    -------
    phase : Tensor
        complex64 tensor of shape ``locs_prepared.shape[:-1]``: per-sample
        unit-modulus phase ``S(k)``.
    """
    size = torch.tensor(
        padded_size, dtype=locs_prepared.dtype, device=locs_prepared.device
    )
    idx = ifftshift_locs(locs_prepared, size)
    rolls = (size + 1) // 2
    angle = (
        idx.to(torch.float32) * rolls.to(torch.float32) / size.to(torch.float32)
    ).sum(dim=-1)
    phase = torch.exp(-2j * torch.pi * angle)
    return phase

torchlinops.linops.nufft.toeplitz_psf

toeplitz_psf(
    nufft: NUFFT,
    inner: NamedLinop | None = None,
    dtype: dtype | None = None,
    oversamp: float = 2.0,
) -> NamedLinop

Compute the Toeplitz point spread function (PSF) for a NUFFT operator.

Constructs a PSF kernel that enables efficient A.H @ inner @ A computation via FFT-based Toeplitz embedding, avoiding explicit forward/adjoint NUFFT pairs.

PARAMETER DESCRIPTION
nufft

The NUFFT operator to compute the PSF for.

TYPE: NUFFT

inner

An optional inner linear operator applied between the forward and adjoint NUFFT (e.g., density compensation). If None, defaults to the identity.

TYPE: NamedLinop DEFAULT: None

dtype

Data type for the PSF kernel. Defaults to torch.complex64.

TYPE: dtype DEFAULT: None

oversamp

Toeplitz oversampling factor. Default is 2.0.

TYPE: float DEFAULT: 2.0

RETURNS DESCRIPTION
NamedLinop

A Dense named linear operator containing the Toeplitz PSF kernel in the Fourier domain.

Source code in src/torchlinops/linops/nufft/toeplitz.py
def toeplitz_psf(
    nufft: NUFFT,
    inner: NamedLinop | None = None,
    dtype: torch.dtype | None = None,
    oversamp: float = 2.0,
) -> NamedLinop:
    """Compute the Toeplitz point spread function (PSF) for a NUFFT operator.

    Constructs a PSF kernel that enables efficient ``A.H @ inner @ A``
    computation via FFT-based Toeplitz embedding, avoiding explicit
    forward/adjoint NUFFT pairs.

    Parameters
    ----------
    nufft : NUFFT
        The NUFFT operator to compute the PSF for.
    inner : NamedLinop, optional
        An optional inner linear operator applied between the forward and
        adjoint NUFFT (e.g., density compensation). If ``None``, defaults
        to the identity.
    dtype : torch.dtype, optional
        Data type for the PSF kernel. Defaults to ``torch.complex64``.
    oversamp : float, optional
        Toeplitz oversampling factor. Default is 2.0.

    Returns
    -------
    NamedLinop
        A ``Dense`` named linear operator containing the Toeplitz PSF
        kernel in the Fourier domain.
    """

    if isinstance(nufft, SamplingNUFFT):
        raise NotImplementedError(
            "Toeplitz embedding is not implemented for SamplingNUFFT"
        )

    # Initialize variables
    dtype = default_to(torch.complex64, dtype)
    new_grid_size = scale_int(nufft.grid_size, oversamp)
    new_padded_size = scale_int(nufft.padded_size, oversamp)
    c0 = tuple(w // 2 for w in nufft.padded_size)
    c1 = tuple(w // 2 for w in new_padded_size)
    ndim = len(nufft.grid_size)

    os_options = {**nufft.options, "skip_prep_locs": True}
    nufft_os = NUFFT(
        rescale_locs(nufft.locs_prepared, c0, nufft.padded_size, c1, new_padded_size),
        grid_size=new_grid_size,
        output_shape=nufft.output_shape,
        input_shape=nufft.input_shape,
        input_kshape=nufft.input_kshape,
        batch_shape=nufft.batch_shape,
        **os_options,
    )

    # Initialize inner if not provided
    if inner is None:
        inner = Identity(ishape=nufft.oshape)

    if len(inner.ishape) != len(inner.oshape):
        raise ValueError(
            f"Inner linop must have identical input and output shape lengths but got ishape={inner.ishape} and oshape={inner.oshape}"
        )

    # Get all useful shapes and sizes
    kernel_shape, ishape, oshape, kernel_size, input_size, batch_sizes = psf_sizing(
        nufft, inner, oversamp
    )

    # Create empty kernel
    kernel = torch.zeros(*kernel_size, dtype=dtype, device=nufft.device)

    # Allocate input
    allones = torch.zeros(*input_size, dtype=dtype, device=nufft.device)
    scale_factor = oversamp**ndim / (prod(new_grid_size) ** 0.5)

    # Compute kernel by iterating through all possible input-output pairs
    dim = tuple(range(-len(new_grid_size), 0))
    for batch_idx in all_indices(batch_sizes):
        allones[batch_idx] = 1.0
        otf = nufft_os.H(inner(allones))
        kernel[batch_idx] = cfftn(otf, dim=dim, norm=None) * scale_factor
        allones[batch_idx] = 0.0  # reset
    kernel_os = Dense(
        weight=kernel,
        weightshape=kernel_shape,
        ishape=ishape,
        oshape=oshape,
    )

    return kernel_os

torchlinops.linops.nufft.rescale_locs

rescale_locs(
    locs,
    c0: tuple,
    w0: tuple,
    c1: tuple,
    w1: tuple,
    dim: int = -1,
)

Perform a scale-and-shift operation on a single dimension of a locs tensor.

PARAMETER DESCRIPTION
locs

The locs to rescale, shape [... D ...]

TYPE: Tensor

c0

The center and width parameter for the current locs

TYPE: tuple

w0

The center and width parameter for the current locs

TYPE: tuple

c1

The desired center and width parameters.

TYPE: tuple

w1

The desired center and width parameters.

TYPE: tuple

dim

The dimension of locs to unstack

TYPE: int DEFAULT: -1

RETURNS DESCRIPTION
Tensor

The rescaled trajectory coordinates.

Source code in src/torchlinops/linops/nufft/toeplitz.py
def rescale_locs(locs, c0: tuple, w0: tuple, c1: tuple, w1: tuple, dim: int = -1):
    """Perform a scale-and-shift operation on a single dimension of a locs tensor.
    Parameters
    ----------
    locs : Tensor
        The locs to rescale, shape [... D ...]
    c0, w0 : tuple
        The center and width parameter for the current locs
    c1, w1: tuple
        The desired center and width parameters.
    dim : int
        The dimension of locs to unstack

    Returns
    -------
    Tensor
        The rescaled trajectory coordinates.
    """
    ndim = locs.shape[dim]
    out = []
    for d in range(ndim):
        loc = torch.select(locs, dim, d)
        # Affine transform
        loc = (loc - c0[d]) * w1[d] / w0[d] + c1[d]
        out.append(loc)
    return torch.stack(out, dim=dim)