PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressed Sensing with Deep Image Prior and Learned Regularization

Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, Eric Price, Sriram Vishwanath, Alexandros G. Dimakis

arXiv:1806.06438v4stat.MLcs.ITcs.LG

TL;DR

Compressed sensing must recover signals from limited noisy measurements, while many neural priors depend on large pre-training datasets. The paper uses an untrained convolutional generator whose weights are optimized to match measurements, adds learned weight regularization, and proves a fitting result that supports early stopping. CS-DIP applies to differentiable linear inverse problems, can outperform previous unlearned methods, and is especially useful when large datasets or good generative models are unavailable.

  • Problem

    Compressed sensing recovery often uses priors, but existing generative-model approaches require pre-trained models that are difficult to obtain for medical images.

  • Method

    CS-DIP randomly initializes a DCGAN generator and optimizes its convolutional weights to match observed measurements, with optional learned regularization on those weights.

  • Results

    CS-DIP solves differentiable linear inverse problems and outperforms previous unlearned methods in many cases, while learned regularization reduces reconstruction error, particularly for noisy or compressed measurements.

  • Takeaways & Limitations

    The method can be used without training when only measurements from a single image are available, and its fitting theory supports regularization methods such as early stopping.

  • Takeaways & Limitations

    When large datasets are available and a good generative model can be trained, pre-trained models are expected to outperform CS-DIP.

Abstract

from arXiv · show

We propose a novel method for compressed sensing recovery using untrained deep generative models. Our method is based on the recently proposed Deep Image Prior (DIP), wherein the convolutional weights of the network are optimized to match the observed measurements. We show that this approach can be applied to solve any differentiable linear inverse problem, outperforming previous unlearned methods. Unlike various learned approaches based on generative models, our method does not require pre-training over large datasets. We further introduce a novel learned regularization technique, which incorporates prior information on the network weights. This reduces reconstruction error, especially for noisy measurements. Finally, we prove that, using the DIP optimization approach, moderately overparameterized single-layer networks can perfectly fit any signal despite the non-convex nature of the fitting problem. This theoretical result provides justification for early stopping.

1 Introduction

The paper develops compressed-sensing recovery with an untrained Deep Image Prior, motivated by the difficulty of obtaining pre-trained models for medical images. It combines measurement-fitting, learned weight regularization, and a theory explaining DIP overfitting and early stopping.

  • Motivation: Compressed sensing recovers an unknown signal from noisy measurements, but the underdetermined system requires structural assumptions such as sparsity.The paper notes that m is smaller than n, producing an ill-posed system with many solutions.
  • Motivation: Pre-trained generative-model methods can recover images from fewer measurements, but they require models trained on large datasets that are difficult to obtain for medical imaging.Medical-image data acquisition is expensive, and suitable generative models are challenging to train.
  • Proposed method: CS-DIP initializes a DCGAN generator randomly and optimizes its weights by gradient descent so its output agrees with the observed measurements.The method uses the convolutional network structure as an unlearned image prior.
  • Proposed method: A learned regularization technique regularizes the DCGAN weights during optimization, using prior information to reduce reconstruction error, especially for noisy or compressed measurements.The paper contrasts this with the unregularized method, which uses measurements from only one unknown image.
  • Theoretical result: Gradient descent provably fits any signal to zero error for a sufficiently overparameterized single-hidden-layer network, theoretically supporting early stopping.DIP’s overparameterization can lead to later fitting of measurement noise, motivating regularization and stopping before that stage.

2 Background

Compressed sensing traditionally relies on sparsity and matrix conditions, while newer approaches use image priors, denoisers, and learned neural representations. The paper positions CS-DIP against these alternatives because they often require pre-trained generative models.

  • Classical approaches: Sparse-signal recovery can be polynomial-time under matrix conditions such as the Restricted Eigenvalue Condition or Restricted Isometry Property.Convex relaxations and iterative methods can recover sparse signals when these conditions hold.
  • Applications: Compressed sensing supports imaging applications including single-pixel cameras, x-ray radiography, microwave imaging, and MRI, where reducing measurements is important.Medical measurements can be costly, time-consuming, or potentially dangerous for patients.
  • Alternative priors: Plug-and-play priors, regularization by denoising, and BM3D-AMP use image denoisers within algorithms for general linear inverse problems.These methods extend beyond sparsity-based reconstruction by incorporating denoising operations as priors.
  • Learned approaches: Neural-network approaches can learn image priors from large datasets, including recurrent generative and auto-regressive models.Their empirical success is attributed to learning image structure from very large collections of examples.
  • Learned approaches: Prior generative-model recovery searches latent space for a signal satisfying the measurements, but requires a pre-trained GAN, VAE, or related model.The paper identifies this requirement as the key contrast with CS-DIP.

3 Proposed Algorithm

CS-DIP reconstructs images by optimizing the weights of an untrained convolutional generator to match compressed measurements, with optional total-variation and learned weight regularization. Learned regularization estimates layer-wise weight statistics from similar-image measurements and incorporates them as a prior, while the unlearned variant needs only measurements from the target image.

  • 3.1 Compressed Sensing with Deep Image Prior (CS-DIP): CS-DIP initializes a convolutional generator with random weights and optimizes them so AG(z; w) matches the observed measurements y.The latent input z is fixed, and the optimization can use gradient-based methods for differentiable generative models and forward operators.
  • 3.1 Compressed Sensing with Deep Image Prior (CS-DIP): The method restricts reconstructions to outputs of a convolutional network, whose structure provides a prior for general differentiable linear inverse problems.With sufficient measurements, the recovered signal is expected to satisfy x∗≈G(z; w∗).
  • 3.1 Compressed Sensing with Deep Image Prior (CS-DIP): The optimization uses total variation, learned regularization, and early stopping; setting λL = 0 makes CS-DIP completely unlearned.Total variation regularizes the generated image, while learned regularization acts on the generator weights.
  • 3.2 Learned Regularization: Learned regularization poses the reconstruction as MAP estimation and introduces a prior that penalizes weights away from an optimal distribution characterized by µ and Σ.The Gaussian prior yields a quadratic penalty, with λL controlling its strength; when µ = 0 and Σ = I_d×d, it reduces to ℓ2 regularization.
  • 3.2.1 Learning the Prior Parameters: Because per-weight statistics are intractable for large networks, the method estimates layer-wise µ and Σ, assuming weights within a layer share a distribution and layers are independent.The statistics are estimated from optimized weights obtained by running CS-DIP on measurements from multiple images, without access to their ground truth during weight optimization.
  • 3.2.2 Discussion of Learned Regularization: The unlearned method uses only one target image's measurements, whereas learned regularization requires measurements from roughly 10 similar images and is intended for settings lacking massive datasets or good generative models.If a massive dataset supports a strong pretrained generative model, the authors expect pretrained methods to outperform CS-DIP.

4 Theoretical Results

The analysis proves that gradient descent can fit any measured signal with a sufficiently overparameterized single-hidden-layer generator, despite non-convexity. This result explains why early stopping is needed for DIP-based recovery, particularly when measurements are noisy.

  • Theoretical result: Gradient descent fits any signal to zero error when a single-hidden-layer network has sufficient constant-factor overparameterization.The result concerns optimizing the input-to-hidden weights while holding the hidden-to-output weights fixed.
  • Model and optimization: The generator is a single-hidden-layer ReLU network with k inputs, d hidden units, and n outputs, trained over W with V fixed.Here W denotes input-to-hidden weights, while V denotes hidden-to-output weights.
  • Model and optimization: Gradient descent uses updates Wτ+1 = Wτ − η∇L(Wτ), with a step size scaled by η = η̄ ∥y∥^2 8m 4m+d and η̄ ≤ 1.The theorem assumes d ≥ Cm for a fixed numerical constant C.
  • Theoretical result: For orthonormal-row measurement matrices, including subsampled Fourier matrices, the theorem applies to the compressed sensing setting.The stated condition is that A has orthonormal rows.
  • Implication for early stopping: Because sufficiently wide networks eventually fit any signal, including noise, early stopping is necessary for DIP-based methods to succeed.The proof provides a theoretical explanation for the empirically motivated stopping heuristic.

5 Experiments

The experiments evaluate CS-DIP on grayscale and RGB images using Gaussian and Fourier measurements, comparing learned regularization and unlearned baselines. CS-DIP generally outperforms unlearned methods, while learned regularization helps most with noise and severe compression.

  • Experimental setup: Experiments use MNIST, chest x-rays, and RGB retinopathy images with Gaussian i.i.d. and Fourier measurement processes.The baselines include BM3D-AMP, TVAL3, and Lasso in a DCT basis.
  • Learned regularization: Learned regularization reduces reconstruction error, particularly as measurement noise increases or the number of measurements decreases.The comparison holds other parameters constant and learns a Gaussian weight prior from ten x-ray images.
  • Unlearned CS-DIP: On MNIST, CS-DIP outperforms the baselines in almost all measurement regimes.Figure 2b shows reconstructions using 75 measurements out of 784 pixels.
  • Unlearned CS-DIP: On chest x-rays, CS-DIP outperforms all baselines except BM3D-AMP at higher measurement counts.At lower sampling rates, including m/n ≤3%, BM3D-AMP often fails to converge.
  • Unlearned CS-DIP: Against a pre-trained DCGAN, CS-DIP performs worse with fewer measurements but improves beyond it as measurements increase.The authors attribute this crossover to optimizing network weights rather than the latent space, giving CS-DIP greater expressiveness for complicated signals such as medical images.
  • Additional experiments: Additional experiments evaluate Fourier measurements, RGB retinopathy images, additive noise, and runtime.On Fourier measurements, the method outperforms all baselines in the reported x-ray comparison.

6 Conclusion

The conclusion presents CS-DIP as an untrained approach for differentiable linear inverse problems, augmented by learned weight regularization and supported by a fitting result for wide single-layer networks.

  • DIP can be generalized to differentiable linear inverse problems and often outperforms state-of-the-art unlearned methods.
  • Learned Gaussian regularization on network weights reduces reconstruction error, especially for noisy or compressed measurements.
  • A sufficiently wide single-layer network can fit any signal using DIP optimization despite the fitting problem’s non-convexity.The result provides theoretical justification for early stopping and related regularization methods.

A Implementation Details

Implementation uses grid-searched hyperparameters, random initializations, and early stopping to control the CS-DIP optimization and avoid fitting measurement noise.

  • Grid search selects λT = 0.01 and λL = 100 using lowest error on observed measurements without ground truth.
  • Measurement matrices and network inputs are randomly initialized, while the input z remains fixed during weight optimization.The input dimension is 128; different z initializations do not affect performance for sufficiently large images.
  • All experiments stop after 1000 iterations, within the plateau before DIP begins fitting noise at roughly 10,000 iterations.This early-stopping rule is intended to avoid overfitting.

B Additional Experiments

Additional experiments test the method with Fourier measurements, RGB retinopathy images, additive noise, and runtime comparisons. The method outperforms baselines in the x-ray Fourier setting and generally on retinopathy, while remaining reasonably fast despite an unfair GPU comparison.

  • Fourier measurement process: 381, 634, 1260, and 2500 Fourier coefficients correspond to 3, 5, 10, and 20 radial lines, respectively.The measurements come from a subsampled Fourier matrix with radial-line index selection.
  • Fourier measurement process: The algorithm quantitatively outperforms all baselines on the x-ray dataset across the tested radial-line settings.The settings are 3, 5, 10, and 20 radial lines in the Fourier domain.
  • Retinopathy: On RGB retinopathy images, the method outperforms all baselines except BM3D-AMP at higher measurement counts.At higher measurements, green and purple pixel patches still corrupt reconstructions; BM3D-AMP often fails at lower measurements, similarly to x-ray.
  • Robustness to noise: The method is robust to additive noise and exhibits behavior similar to the baselines.This evaluation concerns the noisy case where η ≠ 0 in Equation 1.
  • Runtime: The method is faster in most runtime comparisons, but the comparison is not fair because only the proposed method used a GPU.The proposed method ran on an NVIDIA GTX 1080-Ti, and the authors characterize its runtime as reasonable.

C Proof of Section 4: Theoretical Justification for Early Stopping

The proof analyzes gradient descent for the DIP network through its Jacobian, residual, and local spectral properties. Its lemmas establish initialization and perturbation controls needed for the theoretical early-stopping justification.

  • Proof setup: The proof develops notation, preliminary gradient and Jacobian calculations, and spectral lemmas for the DIP optimization analysis.The Jacobian and misfit vector are used to rewrite the gradient-descent iterations.
  • Jacobian properties: At initialization, Lemma C.1 analyzes the minimum singular value of the Jacobian for Gaussian matrices and ReLU activation.The lemma defines the Jacobian using random matrices V and W and the derivative of ReLU.
  • Jacobian properties: Lemma C.2 bounds Jacobian perturbations for weights W within radius R of Gaussian initialization W0.The bound holds uniformly over such W with an explicitly stated high-probability guarantee.
  • Jacobian properties: Lemma C.3 controls the spectral norm of the Jacobian, complementing the minimum-singular-value and perturbation bounds.Together, these lemmas characterize the local Jacobian behavior used in the convergence argument.
  • Initialization: Lemma C.4 provides an initial-misfit result for the random network using Gaussian matrices and a normalization involving ∥y∥ and ∥z∥.The supplied statement introduces the random matrices and the initialization setting for this bound.

C.4 Proof of Theorem 4.1

The proof applies a non-smooth overparameterized optimization theorem to the DIP parameter W and ReLU mapping Vφ(Wz). It verifies the theorem’s three Jacobian assumptions using the preceding lemmas.

  • Theorem application: The proof considers nonlinear least-squares optimization with mapping f: R^p → R^n and formalizes three assumptions on its Jacobian.The assumptions concern initialization’s minimum singular value, local Jacobian perturbation, and a global spectral-norm bound.
  • Theorem application: Theorem C.5 states convergence properties for non-smooth overparameterized optimization when those Jacobian assumptions hold.The theorem uses a constant learning rate satisfying η ≤ 1/β^2.
  • DIP specialization: The DIP specialization sets the parameter to W and the nonlinear mapping to Vφ(Wz), with φ equal to ReLU.The proof reduces the application of Theorem C.5 to verifying its assumptions for this mapping.
  • Assumption verification: Lemma C.1 supplies Assumption 1, while Lemma C.3 supplies Assumption 3, each with high-probability guarantees.The remaining task is verifying the local perturbation condition in Assumption 2.
  • Assumption verification: Lemma C.4 bounds the initial residual, and Lemma C.2 is then used to establish the remaining local Jacobian condition.The proof concludes after imposing a sufficiently large width condition and applying Theorem C.5.

D.1 Proof of Lemma C.1

The proof of Lemma C.1 studies the Jacobian Gram matrix for a one-hidden-layer ReLU network with Gaussian weights. It combines concentration, covariance calculations, and local sign-change bounds to control its minimum eigenvalue.

  • Jacobian Gram matrix: The proof first rescales to ν = 1 and rewrites the Jacobian Gram matrix using V, ReLU derivatives, and the input z.The resulting expression is J(W)J^T(W) = ∥z∥^2 V diag(φ′(Wz) ⊙ φ′(Wz)) V^T.
  • Minimum-eigenvalue bound: A matrix concentration theorem is introduced to lower-bound the minimum eigenvalue through the expectation Σ of random positive semidefinite matrices.The theorem assumes bounded second moments and provides a high-probability bound parameterized by δ.
  • Minimum-eigenvalue bound: For ReLU, the proof calculates Σ and related quantities needed to apply the concentration theorem.The supplied passages identify these as the covariance and parameter calculations in the argument.
  • Width condition: The argument obtains a width requirement of d ≥ 3528 · n in one concentration step.This condition appears in the supplied proof fragments as a sufficient dimensional scaling.
  • Local perturbations: To control perturbations from initialization, the proof tracks neurons whose preactivation signs differ between W and W0.The set S(W) indexes sign changes, and V_S(W) selects the corresponding columns of V.
  • Local perturbations: Gordon’s lemma and sign-change bounds provide high-probability control of the perturbation terms, completing the spectral argument.The final step also invokes standard concentration results for the spectral norm of a Gaussian matrix.

D.5 Proof of Lemma C.4

The section presents proof fragments involving Gaussian vectors, triangular-inequality reasoning, and high-probability bounds, alongside reconstruction comparisons across measurement settings and image datasets.

  • The proof uses the triangular inequality as an intermediate step in bounding the network expression.
  • The argument analyzes entries of V φ (Wz) through random Gaussian vectors with distribution N(0, I_d).
  • The resulting bound holds with probability at least 1 − e^−n/2 − e^−d/2.
  • The reconstruction figures compare the proposed algorithm with BM3D-AMP, TVAL3, and Lasso across MNIST, x-ray, and retinopathy images.The displayed settings vary the number of measurements, including MNIST, x-ray, and retinopathy cases.
Loading 1806.06438v4…