Detecting the origin of information or infection spread in networks is a fundamental challenge with applications in misinformation tracking, epidemiology, and beyond. We study the multi-source detection problem: given snapshot observations of node infection status on a graph, estimate the set of source nodes that initiated the propagation. Existing methods either lack statistical guarantees or are limited to specific diffusion models and assumptions. We propose a novel conformal prediction framework that provides statistically valid recall guarantees for source set detection, independent of the underlying diffusion process or data distribution. Our approach introduces principled score functions to quantify the alignment between predicted probabilities and true sources, and leverages a calibration set to construct prediction sets with user-specified recall and coverage levels. The method is applicable to both single- and multi-source scenarios, supports general network diffusion dynamics, and is computationally efficient for large graphs. Empirical results demonstrate that our method achieves rigorous coverage with competitive accuracy, outperforming existing baselines in both reliability and scalability.

We provide a rigorous analysis of implicit regularization in an overparametrized tensor factorization problem beyond the lazy training regime. For matrix factorization problems, this phenomenon has been studied in a number of works. A particular challenge has been to design universal initialization strategies which provably lead to implicit regularization in gradient-descent methods. At the same time, it has been argued by Cohen et. al. 2016 that more general classes of neural networks can be captured by considering tensor factorizations. However, in the tensor case, implicit regularization has only been rigorously established for gradient flow or in the lazy training regime. In this paper, we prove the first tensor result of its kind for gradient descent rather than gradient flow. We focus on the tubal tensor product and the associated notion of low tubal rank, encouraged by the relevance of this model for image data. We establish that gradient descent in an overparametrized tensor factorization model with a small random initialization exhibits an implicit bias towards solutions of low tubal rank. Our theoretical findings are illustrated in an extensive set of numerical simulations show-casing the dynamics predicted by our theory as well as the crucial role of using a small random initialization.

Many algorithms for high-dimensional regression problems require the calibration of regularization hyperparameters. This, in turn, often requires the knowledge of the unknown noise variance in order to produce meaningful solutions. Recent works show, however, that there exist certain estimators that are pivotal, i.e., the regularization parameter does not depend on the noise level; the most remarkable example being the square-root lasso. Such estimators have also been shown to exhibit strong connections to distributionally robust optimization. Despite the progress in the design of pivotal estimators, the resulting minimization problem is challenging as both the loss function and the regularization term are non-smooth. To date, the design of fast, robust, and scalable algorithms with strong convergence rate guarantees is still an open problem. This work addresses this problem by showing that an iteratively reweighted least squares (IRLS) algorithm exhibits global linear convergence under the weakest assumption available in the literature. We expect our findings will also have implications for multi-task learning and distributionally robust optimization.

Uncertainty quantification (UQ) is a crucial but challenging task in many high-dimensional learning problems to increase the confidence of a given predictor. We develop a new data-driven approach for UQ in regression that applies both to classical optimization approaches such as the LASSO as well as to neural networks. One of the most notable UQ techniques is the debiased LASSO, which modifies the LASSO to allow for the construction of asymptotic confidence intervals by decomposing the estimation error into a Gaussian and an asymptotically vanishing bias component. However, in real-world problems with finite-dimensional data, the bias term is often too significant to disregard, resulting in overly narrow confidence intervals. Our work rigorously addresses this issue and derives a data-driven adjustment that corrects the confidence intervals for a large class of predictors by estimating the means and variances of the bias terms from training data, exploiting high-dimensional concentration phenomena. This gives rise to non-asymptotic confidence intervals, which can help avoid overestimating certainty in critical applications such as MRI diagnosis. Importantly, our analysis extends beyond sparse regression to data-driven predictors like neural networks, enhancing the reliability of model-based deep learning. Our findings bridge the gap between established theory and the practical applicability of such methods.

One of the most promising solutions for uncertainty quantification in high-dimensional statistics is the debiased LASSO that relies on unconstrained ℓ1-minimization. The initial works focused on real Gaussian designs as a toy model for this problem. However, in medical imaging applications, such as compressive sensing for MRI, the measurement system is represented by a (subsampled) complex Fourier matrix. The purpose of this work is to extend the method to the MRI case in order to construct confidence intervals for each pixel of an MR image. We show that a sufficient amount of data is $n \gtrsim \max \left\{ {{s_0}{{\log }^2}{s_0}\log p,{s_0}{{\log }^2}p} \right\}$.

Abstract. In this paper, we study error diffusion techniques for digital halftoning from the perspective of 1-bit [Formula: see text] quantization. We introduce a method to generate [Formula: see text] schemes for two-dimensional signals as a weighted combination of their one-dimensional counterparts and show that various error diffusion schemes proposed in the literature can be represented in this framework via [Formula: see text] schemes of first order. Under the model of two-dimensional bandlimited signals, which is motivated by a mathematical model of human visual perception, we derive quantitative error bounds for such weighted [Formula: see text] schemes. We see these bounds as a step towards a mathematical understanding of the good empirical performance of error diffusion, even though they are formulated in the supremum norm, which is known to not fully capture the visual similarity of images. Motivated by the correspondence between existing error diffusion algorithms and first-order [Formula: see text] schemes, we study the performance of the analogous weighted combinations of second-order [Formula: see text] schemes and show that they exhibit a superior performance in terms of guaranteed error decay for two-dimensional bandlimited signals. In extensive numerical simulations for real-world images, we demonstrate that with some modifications to enhance stability this superior performance also translates to the problem of digital halftoning. More concretely, we find that certain second-order weighted [Formula: see text] schemes exhibit competitive performance for digital halftoning of real-world images in terms of the Feature Similarity Index (FSIM), a state-of-the-art measure for image quality assessment.

Recently, experiments have been reported where researchers were able to perform high dynamic range (HDR) tomography in a heuristic fashion, by fusing multiple tomographic projections. This approach to HDR tomography has been inspired by HDR photography and inherits the same disadvantages. Taking a computational imaging approach to the HDR tomography problem, we here suggest a new model based on the modulo Radon transform (MRT), which we rigorously introduce and analyze. By harnessing a joint design between hardware and algorithms, we present a single-shot HDR tomography approach, which to our knowledge, is the only approach that is backed by mathematical guarantees. On the hardware front, instead of recording the Radon transform projections that may potentially saturate, we propose to measure modulo values of the same. This ensures that the HDR measurements are folded into a lower dynamic range. On the algorithmic front, our recovery algorithms reconstruct the HDR images from folded measurements. Beyond mathematical aspects such as injectivity and inversion of the MRT for different scenarios including band-limited and approximately compactly supported images, we also provide a first proof-of-concept demonstration. To do so, we implement MRT by experimentally folding tomographic measurements available as an open source dataset using our custom designed modulo hardware. Our reconstruction clearly shows the advantages of our approach for experimental data. In this way, our MRT based solution paves a path for HDR acquisition in a number of related imaging problems.

In contrast to Shannon sampling theory, where measurements are recorded at equally-spaced time instants, event-driven sampling records values at non-uniform instants dependent on the input. However, both sampling schemes are subject to input dynamic range constraints. This represents a fundamental bottleneck, which can only be alleviated via adjustments in the encoder architecture. Here we explore an alternative strategy based on the recent work on Unlimited Sampling theory, which uses a modulo non-linearity to guarantee a predefined input amplitude range. We propose a cascade model comprising a modulo non-linearity in series with an integrate-and-fire (IF) event-driven encoder. The modulo component does not act on inputs within the IF dynamic range, thus our model is fully compatible with the existing IF methodology. For inputs outside the IF dynamic range, the modulo output is discontinuous, and it currently cannot be recovered from the IF output with existing methods. We introduce theoretical conditions for which the input of the proposed cascade model can be recovered with arbitrary precision. Through numerical simulations, we show the performance of the reconstruction algorithm. The proposed methodology paves the way for a new generation of event-driven models suitable for a much wider range of applications.

Abstract This paper studies the problem of recovering a signal from one-bit compressed sensing measurements under a manifold model; that is, assuming that the signal lies on or near a manifold of low intrinsic dimension. We provide a convex recovery method based on the Geometric Multi-Resolution Analysis and prove recovery guarantees with a near-optimal scaling in the intrinsic manifold dimension. Our method is the first tractable algorithm with such guarantees for this setting. The results are complemented by numerical experiments confirming the validity of our approach.

The fractional Fourier transform has found applications in a variety of topics linked with science and engineering. In this context, sampling theory is one of the most well-studied subjects. Since the fractional Fourier transform or the FrFT generalizes the notion of bandlimitedness, extension of Shannon's sampling theorem to the FrFT domain generalizes the classical result for the Fourier domain. These ideas have further been extended to the class of non-bandlimited functions via shift-invariant subspaces and sparse models. In this paper, we discuss a different approach to sampling theory in the FrFT domain. For the first time, we propose sampling and recovery of bandlimited functions in the FrFT domain that is based on one-bit samples. Our work is inspired by the Sigma-Delta quantization scheme. In particular, we capitalize on the idea of noise shaping and develop a one-bit sampling architecture that allows for recovery of bandlimited functions in the FrFT domain by pushing quantization noise to the higher frequencies. Since the FrFT generalizes the Fourier transform, our work results in a generalized Sigma-Delta architecture. We validate our theoretical concepts through computer experiments and provide an approximation theoretic error bound.

The topic of high dynamic range (HDR) tomography is starting to gain attention due to recent advances in the hardware technology. Registering high-intensity projections that exceed the dynamic range of the detector cause sensor saturation. Existing methods rely on the fusion of multiple exposures. In contrast, we propose a one-shot solution based on the Modulo Radon Transform (MRT). By exploiting the modulo non-linearity, the MRT encodes folded Radon Transform projections so that the resulting measurements do not saturate. Our recovery strategy is pivoted around a property we call compactly λ-supported, which is motivated by practice; in many applications the object to be recovered is of finite extent and the measured quantity has approximately compact support. Our theoretical results are illustrated by numerical simulations with an open-access X-ray tomographic dataset and lead to substantial improvement in the HDR recovery problem. For instance, we report recovery of objects with projections 1000x larger in amplitude than the detector threshold.

Quantization is an integral part of image acquisition but also a major performance bottleneck due to the trade-off between dynamic range and resolution. As we discuss in this paper, in contrast, quantization noise can be acquired reliably even beyond the dynamic range by re-purposing recent hardware development. In this paper, we introduce and mathematically analyze an algorithm to recover images from this information, thus giving rise to a novel, single-shot, high-dynamic-range (HDR) imaging approach. Our method directly works with a refined model for sensor outputs at the digitization stage and crucially exploits smoothing anti-aliasing artifacts. We derive recovery guarantees and demonstrate the validity of our approach via computer experiments. Our work suggests re-thinking of the imaging pipeline as seeming sensing artifacts can lead to improved reconstruction when combined with proper computational methodology.

Conventional analog-to-digital converters (ADCs) are limited in dynamic range. If a signal exceeds some prefixed threshold, the ADC saturates and the resulting signal is clipped, thus becoming prone to aliasing artifacts. Recent developments in ADC design allow to overcome this limitation: using modulo operation, the so called self-reset ADCs fold amplitudes which exceed the dynamic range. A new (unlimited) sampling theory is currently being developed in the context of this novel class of ADCs. In this paper, we make a further step in this direction by coupling modulo sampling with one-bit ΣΔ quantization, or, in other words, consider one-bit unlimited sampling. We show that our scheme overcomes the dynamic range limitations of conventional one-bit quantizer, where no recovery guarantees are possible if the signal's dynamic range substantially exceeds the range of its one-bit output. We provide a constructive recovery algorithm for bandlimited signals from one-bit modulo samples complemented with a bound on the reconstruction error.

In a recent paper [1], we introduced the concept of “Unlimited Sampling”. This unique approach circumvents the clipping or saturation problem in conventional analog-to-digital converters (ADCs) by considering a radically different ADC architecture which resets the input voltage before saturation. Such ADCs, also known as Self-Reset ADCs (SR-ADCs), allow for sensing modulo samples. In analogy to Shannon's sampling theorem, the unlimited sampling theorem proves that a bandlimited signal can be recovered from modulo samples provided that a certain sampling density criterion, that is independent of the ADC threshold, is satisfied. In this way, our result allows for perfect recovery of a bandlimited function whose amplitude exceeds the ADC threshold by orders of magnitude. By capitalizing on this result, in this paper, we consider the inverse problem of recovering a sparse signal from its low-pass filtered version. This problem frequently arises in several areas of science and engineering and in context of signal processing, it is studied in several flavors, namely, sparse or FRI sampling, super-resolution and sparse deconvolution. By considering the SR-ADC architecture, we develop a sampling theory for modulo sampling of lowpass filtered spikes. Our main result consists of a new sparse sampling theorem and an algorithm which stably recovers a K -sparse signal from low-pass, modulo samples. We validate our results using numerical experiments.

In parallel to Shannon's sampling theorem, the recent theory of unlimited sampling yields that a bandlimited function with high dynamic range can be recovered exactly from oversampled, low dynamic range samples. In this way, the unlimited sampling methodology circumvents the dynamic range problem that limits the use of conventional analog-to-digital converters (ADCs) which are prone to clipping or saturation problem. The unlimited sampling theorem is made practicable by using a unique ADC architecture-the self-reset ADC or the SR-ADC-which resets voltage before clipping, thus producing modulo or wrapped samples. While retaining full dynamic range of the input signal, surprisingly, the sampling density prescribed by the unlimited sampling theorem is independent of the maximum recordable voltage of the new ADC and depends only on the signal bandwidth. As the corresponding problem of signal recovery from such modulo samples arises in various applications with different signal models, where the original result does not directly apply, the original paper continues to trigger research follow-ups. In this paper, we investigate the case of sampling and reconstruction of a mixture of K sinusoids from such modulo samples. This problem is at the heart of spectral estimation theory and application areas include active sensing, ranging, source localization, interferometry and direction-of-arrival estimation. By relying on the SR-ADCs, we develop a method for recovery of K-sparse, sum-of-sinusoids from finitely many wrapped samples, thus avoiding clipping or saturation. As our signal model is completely characterized by K pairs of amplitudes and frequencies, we obtain a parametric sampling theorem; we complement it with a recovery algorithm. Numerical demonstrations validate the effectivity of our approach.

We study the problem of passive imaging through convolutive channels. A scene is illuminated with an unknown, unstructured source, and the measured response is the convolution of this source with multiple channel responses, each of which is time-limited. Spectral methods based on the commutativity of convolution, first proposed and analyzed in the 1990s, provide an elegant mathematical framework for attacking this problem. However, these now classical methods are very sensitive to noise, especially when working from relatively small sample sizes. In this paper, we show that a linear subspace model on the coefficients of the impulse responses of the channels can make this problem well-posed. We derive nonasymptotic error bounds for the generic subspace model by analyzing the spectral gap of the cross-correlation (CC) matrix of the channels relative to the perturbation introduced by noise. Numerical results show that this modified spectral method offers significant improvements over the classical method and outperforms other competing methods for multichannel blind deconvolution.

We consider simultaneous blind deconvolution of r source signals from their noisy superposition, a problem also referred to blind demixing and deconvolution. This signal processing problem occurs in the context of the Internet of Things where a massive number of sensors sporadically communicate only short messages over unknown channels. We show that robust recovery of message and channel vectors can be achieved via convex optimization when random linear encoding using i.i.d. complex Gaussian matrices is used at the devices and the number of required measurements at the receiver scales with the degrees of freedom of the overall estimation problem. Since the scaling is linear in r our result significantly improves over recent works.

In the context of the phase retrieval problem, it is known that certain natural classes of measurements, such as Fourier measurements and random Bernoulli measurements, do not lead to the unique reconstruction of all possible signals, even in combination with certain practically feasible random masks. To avoid this difficulty, the analysis is often restricted to measurement ensembles (or masks) that satisfy a small-ball probability condition, in order to ensure that the reconstruction is unique. This paper shows a complementary result: for random Bernoulli measurements, there is still a large class of signals that can be reconstructed uniquely, namely, those signals that are non-peaky. In fact, this result is much more general: it holds for random measurements sampled from any subgaussian distribution 2), without any small-ball conditions. This is demonstrated in two ways: 1) a proof of stability and uniqueness and 2) a uniform recovery guarantee for the PhaseLift algorithm. In all of these cases, the number of measurements m approaches the information-theoretic lower bound. Finally, for random Bernoulli measurements with erasures, it is shown that PhaseLift achieves uniform recovery of all signals (including peaky ones).

In this letter, we provide a new approach to estimating the error of reconstruction from ΣΔ quantized compressed sensing measurements. Our method is based on the restricted isometry property (RIP) of a certain projection of the measurement matrix. Our result yields simple proofs and a slight generalization of the best-known reconstruction error bounds for Gaussian and subGaussian measurement matrices.

In many signal processing applications, one wishes to acquire images that are sparse in transform domains such as spatial finite differences or wavelets using frequency domain samples. For such applications, overwhelming empirical evidence suggests that superior image reconstruction can be obtained through variable density sampling strategies that concentrate on lower frequencies. The wavelet and Fourier transform domains are not incoherent because low-order wavelets and low-order frequencies are correlated, so compressive sensing theory does not immediately imply sampling strategies and reconstruction guarantees. In this paper, we turn to a more refined notion of coherence-the so-called local coherence-measuring for each sensing vector separately how correlated it is to the sparsity basis. For Fourier measurements and Haar wavelet sparsity, the local coherence can be controlled and bounded explicitly, so for matrices comprised of frequencies sampled from a suitable inverse square power-law density, we can prove the restricted isometry property with near-optimal embedding dimensions. Consequently, the variable-density sampling strategy we provide allows for image reconstructions that are stable to sparsity defects and robust to measurement noise. Our results cover both reconstruction by ℓ1-minimization and total variation minimization. The local coherence framework developed in this paper should be of independent interest, as it implies that for optimal sparse recovery results, it suffices to have bounded average coherence from sensing basis to sparsity basis-as opposed to bounded maximal coherence-as long as the sampling strategy is adapted accordingly.

In this note, we show that by quantizing theN-dimensional frame coefficients of signals in Rdusingrth-order Sigma-Delta quantization schemes, it is possible to achieve root-exponential accuracy in the oversampling rate λ: =N/d. In particular, we construct a family of finite frames tailored specifically for coarse Sigma-Delta quantization that admit themselves as both canonical duals and Sobolev duals. Our construction allows for error guarantees that behave ase-c√{λ}, where under a mild restriction on the oversampling rate, the constants are absolute. Moreover, we show that harmonic frames can be used to achieve the same guarantees, but with the constants now depending ond.

Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed from this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.