import torch


def interpolate(dense_descriptors: torch.Tensor, keypoints: torch.Tensor):
    """Bilinearly interpolate sparse descriptors.
    Args:
        * dense_descriptors: The dense descriptor maps, of size [1 x C x H x W]
        * keypoints: The [N x 2] keypoint coordinates,
    Returns:
        * sparse_descriptors: The [N x C] sparse descriptors.
    """
    batch, channels, height, width = dense_descriptors.shape
    assert batch == 1
    scale = torch.tensor([width - 1, height - 1]).to(keypoints)
    keypoints = (keypoints / scale) * 2 - 1
    keypoints = keypoints.clamp(min=-2, max=2)
    sparse_descriptors = torch.nn.functional.grid_sample(
        dense_descriptors, keypoints[None, :, None], mode="bilinear", align_corners=True
    )
    return sparse_descriptors.view(channels, -1).transpose(-1, -2)