Source-linked AI summary
Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guarantees
Viraj Shah, Chinmay Hegde
TL;DR
The paper addresses ill-posed linear inverse problems and the limited modeling capability of sparsity priors, alongside weak theoretical guarantees in many learning-based methods. It uses a GAN prior with projected gradient descent in the ambient space, obtaining provable convergence and stronger empirical performance than an existing GAN-based method and a sparsity baseline.
Problem
Linear inverse problems require informative priors when m < n, but sparsity has limited discriminatory capability and many learning-based methods lack concrete theoretical guarantees.
Method
The paper solves the constrained inverse problem with projected gradient descent, alternating gradient updates and projection onto the range of a differentiable GAN generator.
Results
T = log(1/ε) suffices for ε-accuracy under stated conditions, and experiments report better performance than the existing GAN method and sparsity baseline.
Takeaways & Limitations
GAN priors can support linear inverse recovery with both empirical performance gains and a convergence analysis for the proposed algorithm.
Takeaways & Limitations
The method assumes a differentiable generator that well approximates the target signal distribution and relies on measurement conditions such as S-REC.
Abstract
from arXiv · showhide
In recent works, both sparsity-based methods as well as learning-based methods have proven to be successful in solving several challenging linear inverse problems. However, sparsity priors for natural signals and images suffer from poor discriminative capability, while learning-based methods seldom provide concrete theoretical guarantees. In this work, we advocate the idea of replacing hand-crafted priors, such as sparsity, with a Generative Adversarial Network (GAN) to solve linear inverse problems such as compressive sensing. In particular, we propose a projected gradient descent (PGD) algorithm for effective use of GAN priors for linear inverse problems, and also provide theoretical guarantees on the rate of convergence of this algorithm. Moreover, we show empirically that our algorithm demonstrates superior performance over an existing method of leveraging GANs for compressive sensing.
1. INTRODUCTION
Linear inverse problems are ill-posed when measurements are fewer than signal dimensions, motivating structured priors for recovery. The paper replaces limited hand-crafted priors with GAN-based structure and proposes projected gradient descent with theoretical and empirical support.
- Motivation: When m < n, linear inverse problems are ill-posed, so recovery is formulated as constrained optimization over a structured signal set S.
- Motivation: Sparsity can enable accurate recovery under suitable measurement conditions but has limited discriminatory capability for natural signals and images.
- Motivation: GANs learn nonlinear mappings from low-dimensional latent spaces to high-dimensional samples and can better capture the notion of natural signals.
- Our Contributions: The paper proposes projected gradient descent to solve the constrained problem directly, alternating gradient updates with projection onto the generator range.
- Our Contributions: Unlike latent-space gradient descent, the proposed ambient-space method is designed to mitigate local minima and explore outside the generator range.
- Our Contributions: The analysis establishes approximate reconstruction and linear convergence, while experiments on MNIST and CelebA report the best quantitative and visual performance among the compared methods.
2. ALGORITHM AND MAIN RESULTS
The paper solves linear inverse problems by alternating gradient descent on measurement error with projection onto the generator's range. Under S-REC and related conditions on the measurement matrix, the resulting PGD-GAN sequence has a provable convergence guarantee.
- Algorithm: The generator maps latent vectors into high-dimensional samples, restricting candidate reconstructions to its modeled natural-image range.The generator is assumed differentiable so gradients involving it can be computed by back-propagation.
- Algorithm: The algorithm alternates a gradient descent update for measurement error with projection of the result onto the generator's range.The projection is computed by finding the generator output closest to the gradient-updated estimate.
- Algorithm: The projection step minimizes the distance between the gradient-updated vector and a generator output using an inner gradient-descent procedure.The inner optimization uses Tin updates, so the total number of updates is T × Tin.
- Analysis: The analysis uses S-REC to require that measurement differences between signals in the modeled set remain separated, supporting recovery guarantees.S-REC is defined for all pairs of signals in S, while the theorem also assumes a norm bound on A.
- Analysis: Theorem 2.2 establishes convergence for PGD-GAN when A satisfies S-REC with probability 1 − p and has the stated norm bound with probability 1 − q.The theorem applies to every x∗ in the generator's range under the specified Gaussian measurement model and condition ρ^2 ≤ γ.
- Analysis: Choosing the learning rate in the interval 1/(2γ) < η < 1/γ, together with ρ^2 ≤ γ, yields the required contraction condition.The derivation also treats δ as decreasing with the number of measurements m, so it can be neglected when m is sufficient.
3. MODELS AND EXPERIMENTS
The experiments compare the proposed algorithm with and LASSO across two GAN architectures and datasets. Results use fixed update budgets and show better reconstruction performance for the proposed method on MNIST and celebA.
- Experimental setup: The experiments compare the proposed algorithm with and LASSO using two GAN architectures and two datasets.The setup is designed to test the approach across varied architectures and datasets.
- Experimental setup: The measurement matrix uses independent Gaussian entries with zero mean and 1/m standard deviation, while experiments ignore noise.Both algorithms use gradient descent with the same total number of update steps and no random restarts.
- MNIST experiment: The MNIST experiment uses a fully connected one-hidden-layer GAN trained on 60,000 handwritten digit images of size 28 × 28.The generator takes a 20-dimensional standard normal latent vector and outputs 784-dimensional images.
- MNIST experiment: With 10 MNIST images sampled from the generator span, PGD-GAN uses η ≥ 0.5, ηin = 0.01, T = 15, and Tin = 200 for 3000 updates.The comparison algorithm [17] also uses 3000 updates with η = 0.01.
- MNIST experiment: On MNIST reconstruction error, the proposed algorithm outperforms the other two methods, with near-zero error possible using 100 measurements.The evaluation includes quantitative reconstruction errors and qualitative reconstructions.
- celebA experiment: The celebA experiment uses a pre-trained DCGAN with latent dimension k = 100 and evaluates reconstruction on a held-out test dataset.Using m = 1000 measurements, the proposed algorithm produces better reconstructions than the baselines.