Generative models have been studied experimentally and theoretically as priors for inverse problems such as compressed sensing. Recent work by Gunn et al. studied the use of generative priors with tunable complexity, where a family of generative priors with varying complexity is maintained and a specific complexity can be selected at inversion time. They demonstrated that lower reconstruction errors can be experimentally attained for a variety of inverse problems by appropriately tuning the complexity of the generative prior. In the present paper, we establish theory for compressed sensing in the setting of a tunable family of linear generative priors naturally related through their singular value decompositions. We prove that in noiseless Gaussian compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error over the entire family of linear priors. Thus, in this idealized linear noiseless setting, tuning to a lower-complexity prior does not improve the expected reconstruction error. This result is in contract to the behavior of denoising, where lower complexity priors attain lower reconstruction errors due to a standard bias-variance tradeoff. This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.
Michael I. Ivanitskiy, John Jasper, Emily J. King +1stat.ML cs.IT cs.LG math.CO
We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{ReLU}(W^\top W x+b)\) with an appropriate bias vector \(b\). We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order \(d/\log n\). In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with \(n>d+1\), we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization---which should be of independent interest to frame theorists---of the distribution of signs in the Gram matrix.
Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements. In its original form, BIHT performs a ``gradient-descent'' step, followed by hard thresholding. A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade, with subsequent sharp analyses studying a normalized variant instead, that additionally projects every iterate onto the unit sphere. This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with $\widetilde O(s/ε)$ measurements, a deterministic finite-time iterate has directional error at most $ε$, simultaneously for every $s$-sparse unit vector. This matches the optimal sample dependence achieved by normalized BIHT in prior work. Thus, in the noiseless regime, per-iterate normalization is unnecessary for optimal recovery. Under sign corruptions, we prove a sharp separation. If at most a $τ$ fraction of signs are flipped adversarially, then BIHT, without per-iterate normalization, still reaches the robust error floor at an early iterate with a matching $\widetilde O(s/ε)$ sample complexity rate as its normalized variant. This recovery, however, is not stable. We prove a scalar lower bound showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely. Consequently, no general last-iterate convergence theorem can hold for BIHT under sign corruptions, while its normalized surrogate provably escapes this instance.
Objective. Existing quadratic unconstrained binary optimization (QUBO)-based sparse-view computed tomography (CT) reconstruction neglects photon-counting statistics and anatomical heterogeneity. We address both limitations within the QUBO framework.Approach. We propose a quantum compressed-sensing CT method combining penalized weighted least squares (PWLS) and guided total variation (GTV). PWLS weights projection residuals by photon-count reliability, whereas GTV uses gradients from a prior image reconstructed by the simultaneous algebraic reconstruction technique (SART) to preserve edges and suppress noise in homogeneous regions. After binary encoding, both terms form a unified QUBO model. Experiments used four 40 times 40 CT images under a 10-view fan-beam geometry with Poisson noise. Comparisons included conventional reconstruction methods, QUBO variants, gradient descent, simulated annealing, and a D-Wave hybrid quantum-classical solver.Main results. PWLS-GTV achieved the best reconstruction quality across all cases. In the representative chest case, it reached a peak signal-to-noise ratio (PSNR) of 36.64 dB, compared with 22.48 dB for SART, the best conventional baseline. GTV consistently outperformed conventional total variation. Simulated annealing and the D-Wave hybrid solver produced similar reconstructions, whereas gradient descent was ineffective. Repeated hybrid-solver runs showed stable performance.Significance. The framework incorporates photon-statistical weighting and structure-guided regularization into QUBO-based CT reconstruction without changing its quadratic form, providing a proof of concept for quantum-assisted sparse-view CT reconstruction.
To address data overload and inefficient shape-level annotation in robotic visual inspection, this paper proposes a hardware-software integrated optoelectronic architecture. A non-imaging, low-data paradigm is established to minimize annotation dependency. First, a sensor-in-the-loop strategy reconfigures a Digital Micromirror Device (DMD) as a physical optical convolutional layer, enabling photonic-domain feature extraction that unifies sensing hardware and processing software. To suppress data volume at the source, a block-based compressed sensing strategy encodes spatial information into low-dimensional temporal signals, drastically reducing redundancy. Subsequently, to bypass laborious manual defect shape annotation, natural language descriptions guide the network to align with highly generalizable features from Contrastive Language-Image Pre-training (CLIP), steering the attention maps of the optoelectronic neural network toward defect shapes. Furthermore, a Localization Accuracy for Attention (LAA) metric is proposed to quantify shape-level defect localization performance. Experiments on transparent material defect detection validate the system's effectiveness. Parametric analysis reveals how measurement matrices, compression ratios, and block sizes affect accuracy. Results show that, compared to traditional imaging, the proposed architecture maintains equivalent accuracy while reducing data volume by 90% for Vision Transformers and computational workload by 60% for Convolutional Neural Networks. This low-data paradigm offers an efficient solution for industrial automation scenarios involving massive data streams, high acquisition costs, or constrained edge resources.
Ahmed Karam Eldaly, Matteo Figini, Daniel C. Alexandercs.CV stat.AP
We propose a novel Bayesian framework for joint image reconstruction and uncertainty quantification from compressed sensing magnetic resonance imaging data. The problem is formulated as a linear inverse problem, where prior distributions are assigned to the unknown image parameters. Specifically, the image is assumed to be sparse in a given transform domain. We develop a general framework applicable to any sparsifying transform and demonstrate its performance using (1) a total variation transform based on image spatial gradients and (2) a wavelet-domain transform. Bayesian inference is performed using a split-and-augmented Gibbs sampler, while the resulting non-differentiable conditional distributions are efficiently sampled using a proximal Markov chain Monte Carlo method. The proposed algorithms are validated on both single-coil and multi-coil datasets using various k-space sampling patterns and acceleration factors. The results demonstrate that the proposed Bayesian methods consistently outperform their optimisation-based counterparts in image reconstruction while providing uncertainty estimates for the reconstructed images. Furthermore, the estimated uncertainty maps show a strong correlation with the true reconstruction errors and substantially outperformed deep learning-based uncertainty estimation methods.
Markovian Whittle-Matérn fields have been convergently approximated by discrete Gauss Markov Random Fields (GMRFs) with sparse precision matrices using a Finite Element approximation of the two-parameter family, \[ (κ^2 - Δ)^{α/2} u = \mathcal{W}, \;\; κ\in \mathbb{R}, \; α\in \mathbb{N}. \] of SPDEs. Using recent developements in the analysis of Discrete Exterior Calculus (DEC), we present a different, yet closely related, convergent GMRF approximation to these Matérn fields over complete, boundaryless Riemannian manifolds discretized as well-centered simplicial complexes. This convergent method (i) is agnostic to $α, κ$ and thus allows a universal approximation scheme for the precision and covariance matrices of the entire $(α, κ)$-family of GMRFs, so they may be inferred rather than guessed. (ii) inherently models pointwise and piecewise-smoothed measurements of a random field and approximates both equally well (iii) is computationally independent of the interpolants used - it suffers no overhead if one convergent interpolant were replaced with another suitable interpolant over the same mesh. Furthermore, we show that, on discretizations that are well-connected in a precise sense, and volume-concentrated, the precision matrices are spectral functions of a graph-laplacian. We provide a low rank approximator to the family of such Matérn GMRFs and mention a use case: reducing the number of measurements needed to model the GMRF by compressed-sensing.
Recently, partial differential equations (PDEs) have been used to directly model the measurement process in signal processing, although their evaluation is costly. In this paper, we propose a novel alternating direction method of multipliers (ADMM)-based algorithm called physics-aware linearized ADMM (PA-LADMM) for inverse problems from PDE-based measurement processes. The key idea is the linearization of the subproblem with PDEs, leading to a cost-efficient update rule that calls only a PDE solver and its gradient evaluation per iteration. The algorithm has a theoretical convergence guarantee under certain conditions. In addition, we combine it with deep unfolding to unroll the PA-LADMM and train its internal parameters using supervised data. Two distinct experiments, compressed sensing with optical fiber communication and image restoration from noisy anisotropic diffusion, demonstrated the effectiveness of the proposed algorithms.