Technical Summary: Conformalized Rate-Adaptive Sensing (CoRAS)

1. Problem Statement

High-resolution imaging systems often operate under strict constraints regarding bits, energy, acquisition time, and latency. While deep learning models have significantly improved image reconstruction from compressed or partial inputs, the performance of these models varies substantially across different images. A complex image with fine details may require a high sampling rate for accurate reconstruction, whereas a simple image may be reconstructed accurately from heavily compressed data.

The core problem addressed is the stopping time problem: determining the minimum amount of information (sampling rate) required to reconstruct a specific image such that the reconstruction error falls below a target level $c$ with high probability.

• Challenge: The true image is unavailable at the time of acquisition, making the exact stopping time unobserved during the process.
• Limitation of Existing Methods: Fixed-rate stopping rules (calibrated to guarantee error control for the worst-case image) are inefficient. They waste resources on simple images and may still fail to meet error targets for complex images.
• Goal: Develop a method that adaptively selects an acquisition rate for each image while providing finite-sample marginal coverage guarantees (ensuring the error is below the target with probability at least $1-\alpha$) and, ideally, approximate conditional coverage across images of varying complexity.

2. Methodology: CoRAS Framework

The proposed method, Conformalized Rate-Adaptive Sensing (CoRAS), operates in two main phases: a horizontal prediction step and a vertical calibration step.

2.1. Horizontal Prediction (Extrapolation)

CoRAS acquires every image up to a pre-specified early decision time $t_0$. It then analyzes the "reconstruction path"—the sequence of reconstructed images and their residuals as the sampling rate increases.

• Residual Decomposition: Assuming an orthonormal transform (e.g., Fourier or Wavelet) where acquisition proceeds in an ordered manner (e.g., low to high frequency), the squared reconstruction loss is decomposed into "bandwise residual energies."
• Next-Band Residuals: The method defines a "next-band residual" $I_{i,t}$, which measures how well the reconstruction at step $t-1$ predicts the new information revealed at step $t$.
• Ordered-Tail Model: Under the assumption that the residual spectrum follows a power-law decay (Assumption 1), the logarithm of the next-band residuals behaves linearly with respect to the acquisition step.
• Monotone Polynomial Fit: CoRAS fits a monotone polynomial to the observed log-residual history ($t=2$ to $t_0$) for each image. The polynomial order is selected via cross-validation. This fit is extrapolated to predict future residuals and estimate a horizontal stopping time $\hat{T}^H_i$, the point where the predicted loss drops below $c$.

2.2. Vertical Calibration (Conformal Correction)

Since the horizontal extrapolation may be inaccurate for complex images due to limited history, CoRAS applies a conformal correction using a calibration set of images.

• State Definition: The "state" $S_i$ of an image is defined as a pair: $(\hat{T}^H_i, \hat{\Omega}_i)$, where $\hat{T}^H_i$ is the horizontal prediction and $\hat{\Omega}_i$ is the entropy of the reconstruction at time $t_0$ (serving as a proxy for image complexity).
• Weighted Correction: For a test image, CoRAS identifies calibration images with similar states. It computes a weighted average of the errors between the true stopping times and the horizontal predictions of these similar calibration images.
• Conformal Prediction: This correction is integrated into a conformal prediction framework. The method constructs a prediction set of candidate stopping times. The final rule, $\hat{U}^{HV}_{n+1}$, selects the largest candidate $t$ such that the conformal p-value exceeds $1-\alpha$. This ensures that the selected stopping time is a valid upper bound for the true stopping time.

2.3. Theoretical Guarantees

• Marginal Validity: Theorem 2 proves that under the assumption of exchangeable images and monotonic loss, CoRAS guarantees $P(L_{n+1}(\hat{U}^{HV}_{n+1}) \le c) \ge 1-\alpha$. This holds regardless of whether the horizontal extrapolation model is correctly specified.
• Approximate Conditional Validity: Theorem 3 establishes that the method achieves approximate conditional coverage across images with different states. The coverage gap depends on how well the vertical weights match the states (measured by Maximum Mean Discrepancy) and the magnitude of the remaining systematic error after horizontal extrapolation.

3. Key Contributions

1. Adaptive Stopping Rule: CoRAS is the first method to solve the image-specific stopping time problem in reconstruction using conformal prediction, moving beyond global fixed-rate rules.
2. Path-Based Prediction: It introduces a novel "horizontal" prediction mechanism that extrapolates the reconstruction path using a theoretical model of image generation (ordered-tail model) and monotone polynomial fitting.
3. State-Based Calibration: It defines a specific state vector combining the predicted stopping time and reconstruction entropy to perform "vertical" calibration, allowing the method to adapt to image complexity.
4. Theoretical Framework: The paper provides finite-sample marginal validity guarantees and a new model-based theory for approximate conditional coverage in the context of adaptive sensing.

4. Experimental Results

The authors evaluated CoRAS on two datasets: Fashion-MNIST (standard image benchmark) and M4Raw (multi-coil brain MRI with raw k-space measurements).

• Coverage: On both datasets, CoRAS achieved the target coverage rate (90% for $\alpha=0.1$) for the reconstruction error, matching the guarantees of fixed-rate baselines.
• Efficiency: CoRAS significantly outperformed fixed-rate rules in terms of sampling efficiency.
  • Fashion-MNIST: CoRAS used fewer measurements on average than both raw and model-based fixed-rate rules.
  • M4Raw: Similar improvements were observed, with CoRAS reducing the mean sampling rate and excess sampling rate.
• Adaptivity:
  • CoRAS successfully assigned more measurements to complex images (high entropy) and fewer to simple images.
  • While fixed-rate rules maintained a constant sampling rate regardless of image complexity, CoRAS increased its rate as image entropy increased.
  • The "excess sampling rate" (measurements taken beyond the true optimal stopping time) was lowest for CoRAS across all entropy levels, indicating it stops closer to the true target time.
• Coverage by Complexity: For high-entropy (complex) images, all methods showed a slight drop in coverage below the target, suggesting that predicting the stopping times for very complex images remains challenging, though CoRAS adapted its rate more effectively than baselines.

5. Significance and Claims

The paper claims that CoRAS provides a principled solution to the trade-off between acquisition efficiency and reconstruction quality.

• Practical Impact: It enables systems to "buy" measurements one step at a time, stopping as soon as the quality target is met, rather than acquiring a fixed, potentially excessive amount of data.
• Theoretical Novelty: The work extends conformal prediction to a setting where no baseline covariates are available at test time, and the object being predicted (stopping time) is unobserved until the process stops. It bridges the gap between synthetic control methods in causal inference and conformal prediction.
• Limitations and Future Work: The authors acknowledge that the current method uses a fixed decision time $t_0$ and stops only once. They note that a more flexible design involving sequential decisions could be more efficient but would require new theoretical developments to maintain finite-sample guarantees. The paper positions CoRAS as a foundational step toward sequentially valid adaptive sensing in imaging and other domains (e.g., spectroscopy, large language model reasoning).