Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors

Gauri Jagatap, Chinmay Hegde

Abstract

Deep neural networks as image priors have been recently introduced for problems such as denoising, super-resolution and inpainting with promising performance gains over hand-crafted image priors such as sparsity and low-rank. Unlike learned generative priors they do not require any training over large datasets. However, few theoretical guarantees exist in the scope of using untrained neural network priors for inverse imaging problems. We explore new applications and theory for untrained neural network priors. Specifically, we consider the problem of solving linear inverse problems, such as compressive sensing, as well as non-linear problems, such as compressive phase retrieval. We model images to lie in the range of an untrained deep generative network with a fixed seed. We further present a projected gradient descent scheme that can be used for both compressive sensing and phase retrieval and provide rigorous theoretical guarantees for its convergence. We also show both theoretically as well as empirically that with deep network priors, one can achieve better compression rates for the same image quality compared to hand-crafted priors.

Introduction

In inverse imaging, the goal is to reconstruct a high-dimensional image from a smaller set of noisy or incomplete measurements. This includes compressive sensing (recovering images from linear measurements) and compressive phase retrieval (recovering images from non-linear, magnitude-only measurements). Because these problems are ill-posed, they require a "prior"—an assumption about the structure of the image.

Traditionally, researchers used hand-crafted priors like sparsity or Total Variation (TV). Recently, deep learning introduced generative priors (like GANs), which work incredibly well but require massive datasets to train. A newer, fascinating alternative is the untrained network prior (like Deep Image Prior or Deep Decoder), which uses the architecture of a neural network itself as the prior, requiring zero training data. While untrained priors show massive empirical success, there is a severe lack of theoretical guarantees explaining why and when they converge, especially for notoriously difficult non-convex problems like phase retrieval. This paper bridges that theoretical gap.

Methodology

The authors model the target image as lying within the range of an untrained, under-parameterized deep generative network (specifically, a Deep Decoder architecture) driven by a fixed random seed. Because the network has fewer parameters than the image has pixels, it naturally restricts the solution space to structured signals (like natural images) without fitting random noise.

To reconstruct the images, they propose a Network Projected Gradient Descent (Net-PGD) algorithm:

  1. Gradient Step: Take a standard gradient descent step on the measurement loss (using least squares for compressive sensing, and Wirtinger flow for phase retrieval).
  2. Projection Step: Project the resulting noisy update back into the range of the deep network prior by optimizing the network's weights to fit the intermediate image.

To prove this works, the authors develop a novel Set-Restricted Eigenvalue Condition (REC). By treating the ReLU network as a union of linear subspaces (based on activation patterns), they establish bounds on how the measurement matrix preserves the distance between images generated by the network.

Experimental Setup

Because the method relies on untrained priors, no datasets were used for training. For evaluation, the authors used standard image datasets:

  • MNIST: Grayscale images ($28 \times 28$ pixels).
  • CelebA: RGB face images (center-cropped to $64 \times 64 \times 3$).

Key Insights and Ideas

  • Architecture is Destiny: You don't necessarily need to learn the distribution of natural images from millions of examples. The structural bias of an expansive convolutional network (like the Deep Decoder) is inherently suited to represent natural images over noise.
  • Sample Complexity Tied to Network Size: The number of measurements required to successfully reconstruct an image scales with the number of parameters in the network, not the dimension of the image or its sparsity level. For a two-layer network, the sample complexity is $O(k_1 k_2 \log d)$, which is significantly lower than information-theoretic limits for standard sparse priors.
  • First Guarantees for Phase Retrieval: This is the first work to apply deep network priors to compressive phase retrieval. Phase retrieval is highly non-convex because the phase information is missing entirely. The authors prove that Net-PGD can solve it efficiently.
  • Random Initialization is Enough: Previous phase retrieval algorithms required complex, computationally heavy spectral initialization schemes to guarantee convergence. The authors show empirically that a simple uniform random initialization of the network weights is sufficient for Net-PGD to succeed.

Key Results

The authors mathematically prove that Net-PGD achieves linear convergence to the true image (up to an error factor $\epsilon$) for both compressive sensing and phase retrieval, provided the measurement matrix satisfies their new REC bounds.

Comparison of reconstruction methods on MNIST (a) and CelebA (b) datasets, with quantitative nMSE performance across compression ratios (c).

At high compression rates (e.g., $n/d = 0.1$, meaning measurements are 10% of the image size), Net-PGD significantly outperforms standard sparsity-based methods like Lasso and TVAL3 in normalized Mean-Squared Error (nMSE), as shown in Figure (c). For magnitude-only measurements, Net-PGD dramatically outperforms traditional sparse phase retrieval algorithms. For example, on CelebA images (Figure (b)), Net-PGD achieves near-perfect reconstruction while standard sparse methods fail to resolve fine details.

Limitations and Future Work

The primary limitation lies in the theoretical guarantees for the projection step. Fitting a noisy image to an untrained neural network is a highly non-convex optimization problem. While the authors prove the outer loop (Net-PGD) converges assuming the projection step succeeds, proving that gradient descent can globally optimize this specific inner projection step for under-parameterized networks remains an open challenge. Current deep learning theory mostly provides such guarantees only for massively over-parameterized networks. The authors highlight deriving strict convergence guarantees for this specific denoising sub-problem as a highly promising direction for future work.

Summary updated

Abstract

Deep neural networks as image priors have been recently introduced for problems such as denoising, super-resolution and inpainting with promising performance gains over hand-crafted image priors such as sparsity and low-rank. Unlike learned generative priors they do not require any training over large datasets. However, few theoretical guarantees exist in the scope of using untrained neural network priors for inverse imaging problems. We explore new applications and theory for untrained neural network priors. Specifically, we consider the problem of solving linear inverse problems, such as compressive sensing, as well as non-linear problems, such as compressive phase retrieval. We model images to lie in the range of an untrained deep generative network with a fixed seed. We further present a projected gradient descent scheme that can be used for both compressive sensing and phase retrieval and provide rigorous theoretical guarantees for its convergence. We also show both theoretically as well as empirically that with deep network priors, one can achieve better compression rates for the same image quality compared to hand crafted priors.
BibTeX
@inproceedings{jagatap2019algorithmic,
  author = {Gauri Jagatap and Chinmay Hegde},
  title = {{Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=4v4PWEWDv9},
}
Figure