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:
- 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).
- 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).
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.
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