When a network sharpens a blurry photo or fills a hole in a face, many clean images are consistent with the input. Most restoration networks still score their output as if every pixel's error were independent of every other pixel's. That assumption does two kinds of damage. Trained with pixel losses, the network converges toward the blurry average of all plausible answers. Asked for uncertainty, it reports per-pixel error bars whose combined volume is enormous, because it cannot express that "if this window edge is shifted left, so is the one three meters away." Recent work has started to give outputs a correlated noise model, but only within small neighborhoods. Long-range structure is exactly what makes these problems ambiguous in a coordinated way: repeated facade elements, symmetric faces, continuous lines across a hole.
We propose a single feed-forward restoration network whose output is a Gaussian distribution with structured covariance. A sparse local part captures texture-scale correlation. A small number of full-image "modes" capture correlated ambiguity between distant regions. The combination keeps likelihood, sampling and conditioning exact and cheap, with cost linear in the number of pixels. The central test is simple to state. If we reveal the true content of one region, does the model correctly become more confident about distant regions that share its ambiguity? A purely local model provably cannot do this beyond a few correlation lengths.
Core Claim
Posterior uncertainty in ill-posed restoration has two layers. One is local and high-dimensional (texture and noise). The other is global and low-dimensional (a few coherent alternatives that span the whole image). A covariance written as the sum of a sparse-precision Gaussian and a low-rank term captures both. It gives better test likelihood and smaller calibrated uncertainty regions than local-only or diagonal models, at a small fraction of the cost of sampling a diffusion model.
Concretely, the output for an input $\mathbf{y}$ is $\mathbf{x} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ with
$$\boldsymbol{\Sigma} = \boldsymbol{\Lambda}^{-1} + \mathbf{U}\mathbf{U}^\top, \qquad \boldsymbol{\Lambda} = \mathbf{L}\mathbf{L}^\top .$$
Here $\boldsymbol{\mu}$ is the predicted mean image with $N$ pixels. $\mathbf{L}$ is a sparse lower-triangular factor whose nonzeros lie in a $5\times5$ stencil and are predicted per pixel. $\mathbf{U}$ is an $N \times r$ matrix of $r \approx 16$–$32$ full-image mode maps. The Woodbury identity and the matrix determinant lemma make the negative log-likelihood of the ground truth exact. They give
$$\log\det\boldsymbol{\Sigma} = -2\sum_i \log L_{ii} + \log\det(\mathbf{I}_r + \mathbf{U}^\top\boldsymbol{\Lambda}\mathbf{U}),$$
and the quadratic term needs only products of the sparse $\boldsymbol{\Lambda}$ with $r+1$ vectors. Total cost is $O(Nr^2)$ with no dense matrix ever formed. A sample is drawn by solving one sparse triangular system and adding $\mathbf{U}\boldsymbol{\epsilon}$. Conditioning on revealed pixels uses Matheron's rule, which updates a sample using only the covariance between revealed and unrevealed pixels, exactly as in the depth setting.
Relation to Prior Work
Two papers supply the mechanism, and the proposal is their combination applied to a new problem.
Learning Structured Gaussians to Approximate Deep Ensembles (SUPN) predicts a sparse Cholesky precision over a $5\times5$ neighborhood for monocular depth. It shows fast sampling and that conditioning on 100 LiDAR points cuts AbsRel from 0.104 to 0.064 on KITTI. We reuse its local factor and conditioning machinery. We differ in three ways: we add a global low-rank term, we target restoration rather than depth, and we test long-range conditioning specifically.
Woodbury Transformations for Deep Generative Flows uses $\mathbf{I}+\mathbf{UV}$ low-rank transforms with Woodbury inversion to give flows global mixing. It improves ImageNet 64×64 bits per dimension from 3.94 to 3.87. We borrow the low-rank-plus-identity algebra but place it in the output covariance of a conditional restoration model rather than inside an unconditional flow.
Two papers motivate the gap. Principal Uncertainty Quantification with Spatial Correlation for Image Restoration Problems (PUQ) shows that restoration uncertainty concentrates along a few coherent directions. It applies principal component analysis to diffusion posterior samples, then uses conformal calibration (a distribution-free way to set interval widths with guaranteed coverage). This reduces uncertainty volume roughly 10× for super-resolution and inpainting and 100× for colorization on CelebA-HQ. However, it works post hoc on $8\times8$ patches and needs many diffusion samples per image, so it sees no cross-patch structure. Our model predicts such directions directly, image-wide, in one forward pass. Stochastic Image Denoising by Sampling from the Posterior Distribution shows posterior sampling improves LPIPS by 16–17% over MMSE denoisers, but at about two minutes per eight 256×256 images. That cost is the gap a closed-form Gaussian fills, while accepting that a Gaussian cannot represent multimodal posteriors.
Other work constrains the design without addressing correlation in the output. CARD whitens correlated sensor noise. Its correlation lives in the measurement noise, not in the scene posterior, so it is complementary. Equipping Diffusion Models with Differentiable Spatial Entropy replaces pixel losses with local distribution matching, which is local by construction. Two architectures already have global reach but use deterministic pixel losses: ATD, with a learned token dictionary and category-based attention at linear cost, and Fourmer, with Fourier-domain global mixing. They show global context helps the mean; neither models joint uncertainty. ATD's dictionary is also a natural source for $\mathbf{U}$: each of $r$ learned queries cross-attends to full-resolution features and emits one mode map. Global receptive field therefore enters the uncertainty model directly rather than only the mean. MVAR is a cautionary result. It finds that visual autoregressive attention is largely diagonal and local, which suggests the global component may need only a small rank. We test that directly.
Research Program
We build the covariance head on an ATD backbone and train it with the exact Gaussian negative log-likelihood above, plus a small $\ell_1$ term on $\boldsymbol{\mu}$ for stable early training. Training uses ATD's own training data and schedule. We study three tasks where ambiguity is coordinated at long range. The first is 4× super-resolution evaluated on Urban100, whose repeated windows and parallel lines alias in correlated ways. The second is large-mask inpainting and the third is colorization, both on CelebA-HQ following PUQ's setup, where facial symmetry and global hue choices couple distant pixels.
Analysis has three parts. First, does the model's predicted long-range correlation match the correlation structure in diffusion posterior samples? We use samples from PUQ's conditional diffusion model as an independent reference. We plot predicted versus empirical correlation as a function of pixel distance. Second, does the learned rank collapse? Here we sweep $r \in \{0, 4, 16, 64\}$ and inspect what the modes encode, for example global color shifts or the phase of a repeated pattern. Third, the conditioning test below, which is the clearest evidence of whether the model has captured the coupling.
Baselines
The naive reference is the same ATD backbone with a per-pixel diagonal Gaussian head. We calibrate it with per-pixel conformal intervals to the same coverage target. This is the independence assumption in its fairest form. Beating it means lower test negative log-likelihood and a smaller calibrated uncertainty volume at equal coverage. PUQ's 10× reduction over independent baselines on CelebA-HQ super-resolution and inpainting is the scale of gap we expect to reproduce or exceed.
The key ablation is the local-only model ($r=0$), which is SUPN's sparse-precision head transplanted onto the ATD backbone. We train it with identical data, epochs and tuning budget. A second ablation is low-rank-only (diagonal $\boldsymbol{\Lambda}$ plus $\mathbf{U}\mathbf{U}^\top$). It isolates whether local texture correlation matters once global modes exist. Beating the local-only model on Urban100 likelihood and on the distant-conditioning test is the central claim. For reference, SUPN reports KITTI depth RMSE of about 4.07 against 3.85 for an 8-member ensemble. No reported result found on Lacuna for SUPN-style heads on any restoration benchmark.
The strongest existing competitor for uncertainty quality is PUQ applied to samples from a conditional diffusion model. We run it in two forms: its published patch-based exact variant, and its reduced-dimension variant over the full image. We compare at matched wall-clock budget and at a generous budget. We report PUQ's ~10× volume reduction on CelebA-HQ as the published reference. Beating it means either matching its calibrated volume at a fraction of the time, or achieving smaller full-image volume because patches cannot share global modes.
For mean-image quality the strongest competitor is deterministic ATD, which reports up to +0.40 dB over HAT on Urban100 super-resolution. No absolute Urban100 PSNR value is reported in the file. We will retrain ATD ourselves and require that our mean $\boldsymbol{\mu}$ stays within 0.1 dB of it. The aim here is not to win on PSNR but to show the covariance head costs nothing on the mean.
Why not just…?
Why not just run PUQ on full images with a diffusion model? This is the real threat to uncertainty quality. Diffusion samples can capture non-Gaussian, multimodal ambiguity that our model cannot. The obstacles are cost and dimensionality. Kawar et al. report about two minutes for eight small images, and principal components estimated from $K$ samples span at most $K-1$ directions over millions of pixels. This is why PUQ itself restricts to $8\times8$ patches. Our matched-compute comparison settles the question. If full-image PUQ gives smaller calibrated volume at equal time, the Gaussian head is not worth it, and we would say so. We expect the Gaussian head to win at practical budgets and lose at very large ones.
Why not just enlarge the local stencil or stack it across scales? A sparse precision matrix already implies a dense covariance. A multiscale or dilated Markov model can in principle couple distant pixels through coarse levels. Its correlations, though, decay roughly exponentially along chains of neighbors and do not single out the specific distant regions that share an ambiguity, such as two non-adjacent windows. We include a multiscale dilated-stencil SUPN baseline with matched parameter count and run the same distance-binned conditioning test on it. If it matches the low-rank model, the global term is unnecessary and the proposal reduces to "use multiscale precision."
Why not just use a diagonal head with conformal calibration? Conformal calibration guarantees coverage regardless of the model, so calibration is not the issue. The issue is volume and usability. PUQ shows independent bounds are 10–100× larger than necessary, and a diagonal model cannot produce coherent samples or propagate revealed information to unrevealed pixels. The diagonal baseline is included precisely to quantify this.
Why not just add a perceptual or local-entropy loss, as Entropy-SDE does? That changes which single image is produced, not whether ambiguity is represented. The resulting output has no likelihood and no conditioning behavior to evaluate, so it addresses a different question.
Proposed Experiments and Decisive Checks
The primary metrics are test negative log-likelihood in bits per dimension; calibrated uncertainty volume at 90% coverage, using PUQ's protocol; LPIPS and FID of drawn samples; PSNR of the mean; and seconds per image at 256×256 and at full Urban100 resolution.
The decisive check is distant conditioning. For each Urban100 or CelebA-HQ test image, we reveal the ground truth in one small patch and apply Matheron's rule. We then measure the reduction in mean-squared error of the conditioned mean in other patches, binned by distance from the revealed one. The diffusion-sample reference defines how much reduction is attainable. The local-only and multiscale models should show reduction that falls to near zero beyond a few stencil widths. The proposal succeeds if the low-rank model shows substantial reduction at large distances, concentrated in patches that share structure with the revealed one (the same facade, the mirrored half of the face). It fails if long-range gains are negligible or match the multiscale baseline.
A second check is the rank sweep. If test likelihood saturates at $r \le 4$, the global ambiguity in these benchmarks is nearly one-dimensional, for example global color in colorization. That would be informative but would argue for a simpler head. If gains continue to $r=32$ on Urban100 but not on faces, that ties the required rank to scene repetitiveness. Finally, we verify that adding the covariance head leaves ATD's mean PSNR unchanged within 0.1 dB, so the uncertainty does not come at the cost of restoration quality.
References
- Learning Structured Gaussians to Approximate Deep Ensembles
- Woodbury Transformations for Deep Generative Flows
- Principal Uncertainty Quantification With Spatial Correlation for Image Restoration Problems
- Stochastic Image Denoising by Sampling from the Posterior Distribution
- CARD: Correlation Aware Restoration with Diffusion
- Equipping Diffusion Models with Differentiable Spatial Entropy for Low-Light Image Enhancement
- ATD: Improved Transformer With Adaptive Token Dictionary for Image Restoration
- Fourmer: An Efficient Global Modeling Paradigm for Image Restoration
- MVAR: Visual Autoregressive Modeling with Scale and Spatial Markovian Conditioning