Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors

Gauri Jagatap, Chinmay Hegde

Deep neural networks have recently shown immense promise as image priors for inverse problems like denoising, super-resolution, and inpainting, often outperforming hand-crafted priors such as sparsity. While learned generative priors require massive datasets and extensive training, a new class of untrained network priors (e.g., Deep Image Prior) has emerged. These methods use the structure of a neural network architecture itself as a prior, requiring zero training data.

Despite their empirical success, untrained priors have lacked a rigorous theoretical foundation. This paper bridges that gap by providing the first theoretical convergence guarantees for solving inverse imaging problems—specifically compressive sensing and phase retrieval—using untrained, under-parameterized neural networks.

The Challenge of Inverse Imaging

Inverse imaging is the task of recovering an image from incomplete or corrupted measurements. Historically, researchers relied on hand-crafted priors, assuming properties like sparsity in a certain basis. Recently, learned priors (like GANs) have dominated performance benchmarks but at the cost of requiring massive datasets and thousands of hours of training.

Untrained priors offer a compelling middle ground: they require no training data but still leverage the expressive power of neural architectures. However, without theoretical guarantees, it remained unclear exactly how many measurements were needed for successful recovery or if the underlying algorithms were guaranteed to converge.

Methodology: Net-PGD and the Deep Decoder

The authors focus on an "under-parameterized" architecture called the Deep Decoder, where the number of network weights is significantly smaller than the number of pixels in the target image.

To solve inverse problems using this architecture, they propose Net-PGD (Network Projected Gradient Descent). The algorithm alternates between two steps:

  1. Gradient Step: Updates the current image estimate to better match the observed measurements. This uses standard least-squares for linear problems (compressive sensing) or Wirtinger gradients for non-linear problems (phase retrieval).
  2. Projection Step: Projects this updated estimate back onto the space of images that can be represented by the neural network. This is achieved by briefly optimizing the network's weights to fit the current estimate.

To prove convergence, the authors extend the Restricted Isometry Property (RIP)—a cornerstone of compressed sensing theory—to the range of these neural networks. By leveraging a "linearization principle," they argue that because ReLU activations are piecewise linear, the network's output space can be treated as a union of many local linear subspaces.

Key Theoretical Insights

  • Architecture as a Filter: The core mechanism behind untrained priors is that the network architecture acts as a low-pass filter. Because it is under-parameterized, the network cannot easily represent high-frequency noise, forcing it to converge on the natural structural components of the image.
  • Sample Complexity vs. Parameters: The theoretical analysis reveals that the number of measurements required for successful recovery depends on the number of parameters in the network, not the total number of pixels in the image. This explains the high sample efficiency of these models.
  • Provable Convergence: The authors mathematically prove that Net-PGD converges at a linear rate to the true image (within a small error margin), provided the measurement matrix satisfies their newly defined "Set-RIP" condition.

Empirical Results

The authors evaluated their algorithms on two standard benchmarks: MNIST (28x28 grayscale handwritten digits) and CelebA (64x64 RGB celebrity faces).

Compressive Sensing

For standard linear inverse problems, Net-PGD was compared against traditional baselines like Lasso (L1 sparsity) and TVAL3 (Total Variation).

Compressive Sensing Results

Net-PGD achieves significantly lower normalized Mean Squared Error (nMSE) at low compression ratios (e.g., 10% measurements) compared to Lasso and TVAL3. Visually, the untrained network prior recovers sharp structural details that traditional hand-crafted priors miss or blur.

Compressive Phase Retrieval

This work is also the first to apply and theoretically analyze untrained priors for compressive phase retrieval—reconstructing images from magnitude-only measurements, a notoriously difficult non-convex problem.

Phase Retrieval Results

In magnitude-only measurement tests, Net-PGD outperformed the state-of-the-art sparse phase retrieval algorithm, Sparta. It maintains high image quality and successfully converges even when measurements are very scarce.

Limitations and Future Work

While this paper establishes crucial theoretical groundwork, several challenges remain:

  • Gaussian Assumption: The current theoretical guarantees rely on the measurement matrix being Gaussian. Real-world imaging systems (like MRI or CMOS sensors) often use structured measurement patterns.
  • Computational Cost: The projection step requires an inner optimization loop to fit the network weights, making the algorithm computationally slower than simple analytical methods like Lasso.
  • Local vs. Global Convergence: For phase retrieval, the theoretical guarantees are local. While random initialization works well in practice, developing a theoretical "smart initialization" scheme for untrained priors remains an open challenge.

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. Unlike learned generative priors they do not require any training over large datasets. However, few theoretical guarantees exist in the scope of using untrained 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 neural network priors, one can achieve better compression rates for the same image quality as compared to when hand crafted priors are used.
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