# Fast & Robust Image Interpolation using Gradient Graph Laplacian Regularizer

arXiv: https://arxiv.org/abs/2101.09951 · HTML: https://mlsanity.com/paper/2101.09951/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2021.

## Built on by (most cited first, 4 of 4)

- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Sparse Graph Learning with Spectrum Prior for Deep Graph Convolutional Networks](https://mlsanity.com/paper/2202.13526/) (2022)
- [Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment](https://mlsanity.com/paper/2110.11420/) (2021)
- [Constructing an Interpretable Deep Denoiser by Unrolling Graph Laplacian Regularizer](https://mlsanity.com/paper/2409.06676/) (2024)

## Abstract (arXiv)

In the graph signal processing (GSP) literature, it has been shown that signal-dependent graph Laplacian regularizer (GLR) can efficiently promote piecewise constant (PWC) signal reconstruction for various image restoration tasks. However, for planar image patches, like total variation (TV), GLR may suffer from the well-known "staircase" effect. To remedy this problem, we generalize GLR to gradient graph Laplacian regularizer (GGLR) that provably promotes piecewise planar (PWP) signal reconstruction for the image interpolation problem -- a 2D grid with random missing pixels that requires completion. Specifically, we first construct two higher-order gradient graphs to connect local horizontal and vertical gradients. Each local gradient is estimated using structure tensor, which is robust using known pixels in a small neighborhood, mitigating the problem of larger noise variance when computing gradient of gradients. Moreover, unlike total generalized variation (TGV), GGLR retains the quadratic form of GLR, leading to an unconstrained quadratic programming (QP) problem per iteration that can be solved quickly using conjugate gradient (CG). We derive the means-square-error minimizing weight parameter for GGLR, trading off bias and variance of the signal estimate. Experiments show that GGLR outperformed competing schemes in interpolation quality for severely damaged images at a reduced complexity.