PaperlayerView exact revision on arXiv

Source-linked AI summary

On Unlimited Sampling and Reconstruction

Ayush Bhandari, Felix Krahmer, Ramesh Raskar

arXiv:1905.03901v2cs.ITeess.SPmath.IT

TL;DR

Conventional ADCs clip signals that exceed their recordable range, creating a practical bottleneck for sampling theory. The paper develops modulo-based sensing and recovery for bandlimited signals. It provides sufficient sampling conditions for recovery and stability under bounded noise.

Abstract

from arXiv · show

Shannon's sampling theorem is one of the cornerstone topics that is well understood and explored, both mathematically and algorithmically. That said, practical realization of this theorem still suffers from a severe bottleneck due to the fundamental assumption that the samples can span an arbitrary range of amplitudes. In practice, the theorem is realized using so-called analog-to-digital converters (ADCs) which clip or saturate whenever the signal amplitude exceeds the maximum recordable ADC voltage thus leading to a significant information loss. In this paper, we develop an alternative paradigm for sensing and recovery, called the Unlimited Sampling Framework. It is based on the observation that when a signal is mapped to an appropriate bounded interval via a modulo operation before entering the ADC, the saturation problem no longer exists, but one rather encounters a different type of information loss due to the modulo operation. Such an alternative setup can be implemented, for example, via so-called folding or self-reset ADCs, as they have been proposed in various contexts in the circuit design literature. The key task that we need to accomplish in order to cope with this new type of information loss is to recover a bandlimited signal from its modulo samples. In this paper we derive conditions when perfect recovery is possible and complement them with a stable recovery algorithm. The sampling density required to guarantee recovery is independent of the maximum recordable ADC voltage and depends on the signal bandwidth only. Our recovery guarantees extend to measurements affected by bounded noise, which includes the case of round-off quantization. Numerical experiments validate our approach. Applications of the unlimited sampling paradigm can be found in a number of fields such as signal processing, communication and imaging.

I. INTRODUCTION

Sampling theory is framed around an amplitude-axis challenge: conventional ADCs clip signals beyond their recordable range, while the paper proposes modulo sensing and algorithmic recovery as a co-designed alternative. Existing recovery approaches have limitations in guarantees, hardware requirements, and dynamic range.

I. INTRODUCTION

  • The paper places its approach among sampling problems that exploit assumptions about amplitude rather than variations in time sampling.It describes the work as an amplitude analogue of time-warped sampling.Source: §I · p. 3

A. The Sampling Theorem and a Practical Bottleneck

  • Conventional ADCs saturate signals beyond the threshold, and clipping can create high-frequency distortions and aliasing while impairing imaging, communication, and other applications.Examples include bright scenes, strong reflections, clipped audio, and communication performance degradation.Source: A. The Sampling Theorem and a… · p. 3
  • Computational de-clipping lacks explored sampling-density guarantees and continuous-signal error objectives, while hardware-only fixes can be sophisticated and application-specific.The paper identifies bandwidth-governed sampling density as a desired guarantee.Source: A. The Sampling Theorem and a… · p. 3

B. A Solution via Modular Arithmetic

  • The proposed co-design replaces saturation with modulo folding into [−λ, λ], pairing sensing hardware with recovery algorithms.Self-reset or folding ADCs implement the mapping; the prototype figure shows folded amplitudes, reset counts, and an unfolded image.Source: B. A Solution via Modular Arithmetic · pp. 3–5, Figure 1 · p. 4
  • Prior hardware recovery uses modulo samples plus residuals or reset counts, requiring complex circuitry and additional power and storage.The feasibility of reset counts at arbitrarily small modulo thresholds had not been investigated.Source: B. A Solution via Modular Arithmetic · p. 5
  • The framework seeks recovery without residual or reset-count knowledge, drawing on redundant sensed information because phase-unwrapping approaches are ill-posed and dynamically limited.The paper notes that redundant representations can alleviate ill-posedness and allow guaranteed recovery in other settings.Source: B. A Solution via Modular Arithmetic · p. 5

C. Contributions and Overview of Results

The paper establishes sampling and reconstruction guarantees for modulo samples, then situates the framework among related problems including phase unwrapping and quantized recovery.

C. Contributions and Overview of Results

  • Finite-energy bandlimited functions are identifiable from modulo samples at rates just above Nyquist, and the paper gives sufficient conditions for sampling and reconstruction.The stated sampling theorem also covers stability under bounded noise.Source: C. Contributions and Overview of Results · p. 5
  • A constructive recovery algorithm complements the sampling conditions and is guaranteed to recover the signal stably with respect to noise.The theorem’s stability result includes bounded noise such as round-off quantization.Source: C. Contributions and Overview of Results · pp. 5–6
  • T ≤ 1/(2Ωe) is sufficient for recovering a bandlimited signal from modulo samples, up to additive multiples of 2λ.The required sampling rate depends on bandwidth, not on the ratio between ADC threshold and signal amplitude.Source: C. Contributions and Overview of Results · p. 6

D. Related Problems in Other Fields and Recent Work

  • Modulo operations also appear in communications: precoding addresses inter-symbol interference, and integer-forcing communication uses modulo operations, though links to sampling theory remain unclear.Source: D. Related Problems in Other Fields… · p. 6
  • Earlier modulo-quantized recovery approaches were limited to lower dimensions or costly at scale, while this paper’s method is described as stable, efficient, scalable, and not requiring side information.The cited prediction-based alternatives use non-modulo samples as side information.Source: D. Related Problems in Other Fields… · p. 7
  • The paper compares its use of an ADC threshold to modular exponentiation, where a modulus controls the information or bits needed to represent dynamic range.Source: D. Related Problems in Other Fields… · p. 7
  • Related work also applies unlimited sampling to Lipschitz and Hölder functions, sparse signals, Gaussian measurements, graph signals, computed tomography, and multichannel settings.The survey describes distinct recovery methods across these settings, including wavelet-based, QCQP, message-passing, and integer-programming approaches.Source: D. Related Problems in Other Fields… · pp. 7–8
  • In phase unwrapping, Itoh’s condition recovers phase by inverting first-order differences bounded by λ; oversampling lets this framework handle smaller λ with higher-order differences.The paper relates its approach to Itoh’s condition and attributes gains in admissible amplitudes and stability to redundancy from oversampling.Source: D. Related Problems in Other Fields… · p. 6, Figure 2 · p. 8

E. Organization of this Paper

The paper outlines its sections and establishes notation for functions, sequences, norms, differences, and bandlimited spaces.

E. Organization of this Paper

  • The paper covers ADC architectures in Section II, uniqueness in Section III, recovery conditions and the algorithm in Section IV, numerical examples in Section V, and future directions in Section VI.Source: E. Organization of this Paper · p. 8

F. Notation

  • Notation distinguishes continuous functions from discrete sequences and defines standard spaces, norms, derivatives, and finite differences.The text also specifies conventions for sets, sequence spaces, and Fourier transforms.Source: F. Notation · p. 8
  • The notation section defines bandlimited functions and the Paley-Wiener space as bandlimited, square-integrable functions.It notes that the space PWΩ is contained in PWΩ+ϵ for ϵ > 0.Source: F. Notation · p. 9

II. SR-ADCS AND MODULO SAMPLES

Self-reset ADCs fold out-of-range amplitudes back into the recordable range, enabling modulo samples. The model filters a signal, folds it, samples it uniformly, and accounts for bounded quantization noise.

A. Background on Self-Reset ADCs

  • Self-reset ADCs reset at saturation thresholds, capturing voltage variations beyond conventional ADC limits and supporting inherently HDR imaging.The section also notes applications in consumer photography, autonomous navigation, scientific imaging, and bio-imaging.Source: A. Background on Self-Reset ADCs · p. 9

B. Mathematical Model for Unlimited Sampling

C. The Structure of Discontinuities in Modulo Representation

A bandlimited signal decomposes into its modulo representation and a stepwise residual, which the paper calls a simple function. This structure supports residual estimation and robust recovery, while oversampling yields unique identification.

C. The Structure of Discontinuities in Modulo Representation

III. ON IDENTIFIABILITY IN UNLIMITED SAMPLING

  • For any sampling interval 0 < T < π/Ω, modulo samples uniquely determine the bandlimited signal.The section normalizes the bandwidth to Ω = π and the critical sampling interval to T = 1.Source: §III · p. 11
  • Higher-order finite differences commute with modulo folding, enabling recovery when the differences of the bandlimited samples are small enough that folding has no effect.The figure overview describes recovering the differences from modulo measurements and using the residual to reconstruct the samples.Source: Figure 5 · p. 12, §III · p. 12

A. Uniqueness of Modulo Representation

Oversampling makes modulo samples uniquely identify a bandlimited function. The recovery scheme applies higher-order differences, estimates the structured residual, and reconstructs the continuous-time signal.

A. Uniqueness of Modulo Representation

  • At any sampling interval Tϵ = π/(π+ϵ), ϵ > 0, a bandlimited function is uniquely characterized even when any finite set of sample locations is omitted.The injectivity theorem applies this uniqueness result to modulo samples on the oversampled grid.Source: A. Uniqueness of Modulo Representation · p. 12

IV. RECOVERY CONDITIONS AND A RECONSTRUCTION ALGORITHM; A. Overview of the Recovery Scheme

  • The constructive recovery scheme uses the fact that higher-order finite differences commute with modulo operation under appropriate conditions.It starts from differences of the modulo samples to recover the higher differences of the original bandlimited samples.Source: §IV · p. 13, A. Overview of the Recovery Scheme · p. 13
  • The scheme estimates the residual from its higher differences, rounds it to the 2λ grid, and combines it with modulo samples to recover bandlimited samples and then the continuous signal.The anti-difference estimate is recovered up to an unknown constant or integer multiple of 2λ before low-pass reconstruction.Source: A. Overview of the Recovery Scheme · p. 13

B. Towards a Recovery Guarantee for Unlimited Sampling

The recovery analysis bounds higher-order differences of sampled signals using derivative information. For bandlimited signals, Bernstein’s inequality supplies a bandwidth-based bound used to ensure modulo folding does not alter those differences.

B. Towards a Recovery Guarantee for Unlimited Sampling

  • The recovery analysis seeks sampling conditions that make higher-order differences small enough for modulo folding to have no effect.The section uses the difference bounds to analyze how sampling can shrink their amplitudes.Source: B. Towards a Recovery Guarantee for… · p. 13
  • Taylor’s theorem relates higher-order differences of sampled values to derivative bounds for sufficiently smooth bounded functions.The proof evaluates derivatives over intervals containing contiguous sample locations.Source: B. Towards a Recovery Guarantee for… · pp. 13–14
  • For an Ω-bandlimited signal sampled with T ≤ π/Ω, the lemma gives a bound on higher-order sample differences.The proof uses Bernstein’s inequality to bound the derivatives in the Taylor-based estimate.Source: B. Towards a Recovery Guarantee for… · pp. 13–14

1) Recovering Higher Order Differences from Modulo Samples:

The method relates higher-order differences of the bandlimited samples to differences of the modulo samples. Its key step uses modulo decomposition to remove the integer-valued residual contribution, while oversampling and an appropriate difference order bound the remaining error.

1) Recovering Higher Order Differences from Modulo Samples:

  • Choosing T < 1/Ωe and N logarithmically in ∥g∥∞ makes the bound on ∆Nγ arbitrarily small, ultimately ensuring ∥∆Nγ∥∞ < λ.The passage states that the right-hand side of inequality (11) can be made to shrink arbitrarily.Source: 1) Recovering Higher Order Differences… · p. 14
  • Modulo decomposition writes a = Mλ(a) + εa, so ∆NMλ(a) = ∆Na − ∆Nεa.Because εa takes values in 2λZ and the finite-difference filter has integer coefficients, ∆Nεa lies in 2λZ and is removed by Mλ.Source: 1) Recovering Higher Order Differences… · p. 15
  • The resulting relation lets the method obtain higher-order differences of the bandlimited samples from the modulo samples.This is the bridge from the modulo observations y[k] to higher-order differences of γ[k].Source: 1) Recovering Higher Order Differences… · p. 15

2) Recovery of Samples from Higher Order Differences:

The recovery procedure first estimates higher-order differences of the residual sequence from modulo samples, then recursively reverses the differencing while resolving integer-multiple ambiguities. A sufficient sampling condition guarantees recovery up to the unavoidable additive ambiguity of 2λ.

2) Recovery of Samples from Higher Order Differences:

  • The method estimates ∆Nεγ directly from the modulo samples, then recursively applies the anti-difference operator and rounds to multiples of 2λ.The restriction ∆Nεγ ∈ 2λZ makes recovery less ill-posed than recovering γ directly from its differences.Source: 2) Recovery of Samples from Higher… · p. 15
  • Anti-differencing recovers the residual up to a constant, and applying S resolves that ambiguity for difference orders 1 < n ≤ N.At n = 1, adding a constant in 2λZ cannot be resolved because it gives the same modulo samples.Source: 2) Recovery of Samples from Higher… · p. 16
  • Applying S turns the constant ambiguity into a linear sequence with slope 2λ, which the method uses to identify the required integer offset.The passage identifies (Sl)[k] as a linear sequence with slope 2λ.Source: 2) Recovery of Samples from Higher… · p. 16
  • For J = 6βg/λ, the candidate interval has length 1/2 and therefore contains only one integer, enabling the recursive recovery procedure.The estimated κn values are then used to compute the sequence recursively.Source: 2) Recovery of Samples from Higher… · p. 17
  • Theorem 2 gives a sufficient condition for recovering g from modulo samples up to additive multiples of 2λ, and Algorithm 1 achieves that recovery under the stated bound.The theorem assumes a known βg ∈ 2λZ with ∥g∥∞ ≤ βg and chooses N so that (TΩe)^N∥g∥∞ < λ.Source: 2) Recovery of Samples from Higher… · p. 17

3) Recovery Conditions for the Case of Bounded Noise:

The noisy-sample guarantee assumes bounded perturbations of the modulo measurements and imposes a sufficient condition on the recovery algorithm. Under that condition, reconstruction preserves the measurement noise sample by sample, up to an unavoidable constant ambiguity.

3) Recovery Conditions for the Case of Bounded Noise:

  • The noisy modulo measurements are modeled as yη[k] = y[k] + η[k], with |η[k]| ≤ b0.The noise amplitude is bounded by a positive constant b0.Source: 3) Recovery Conditions for the Case of… · p. 17
  • For b0 below a fixed threshold, recovery returns γ[k] + η[k] + 2mλ, preserving the measurement noise entrywise up to an unknown additive constant.The theorem states a sufficient condition for Algorithm 1 to approximately recover the bandlimited samples in this sense.Source: 3) Recovery Conditions for the Case of… · pp. 17–18
  • The noisy modulo measurements still allow exact computation of the residual sequence εγ[k].The proof uses Proposition 2 and bounds on the higher-order differences.Source: 3) Recovery Conditions for the Case of… · p. 18
  • The induction argument recovers the noisy bandlimited samples, after which Shannon’s sampling theorem reconstructs the continuous-time signal.The recovered samples include the input noise and the unavoidable 2λ constant ambiguity.Source: 3) Recovery Conditions for the Case of… · p. 18

V. NUMERICAL EXPERIMENTS

The numerical experiments examine theorem behavior, comparison with phase unwrapping, and stability under quantization noise. In a representative realization, Algorithm 1 recovers the samples with near-machine-precision error, while the tested phase-unwrapping method fails.

A. Verifying the Unlimited Sampling Theorem

  • The theorem experiment uses 1000 randomly generated bandlimited-function realizations with piecewise-constant Fourier spectra.The spectral values are selected uniformly at random.Source: A. Verifying the Unlimited Sampling… · p. 19
  • 6.2455×10−33 mean squared error was measured between the bandlimited samples and recovered samples in the reported realization.The realization used λ = 809/3125, βg = 20λ, T = 11/200, and estimated N = 5.Source: A. Verifying the Unlimited Sampling… · p. 20
  • The phase-unwrapping reconstruction based on Itoh’s condition fails in the reported case because |∆y| < λ does not hold.The figure caption also reports failure of the phase-unwrapping method to recover the bandlimited samples.Source: Figure 6 · p. 19, A. Verifying the Unlimited Sampling… · p. 20

B. Exploring Sharpness of the Unlimited Sampling Theorem

The experiments examine recovery below the theorem’s sampling guarantee and stability under quantization. The conclusion states the recovery guarantees and identifies broader signal classes, implementation, and noise settings as open directions.

B. Exploring Sharpness of the Unlimited Sampling Theorem

  • Recovery succeeded in trials for T ∈ (TUS, TShannon), below the theorem’s guarantee; higher-order differences extended recovery to smaller oversampling factors, but failures appeared around T = 0.4.The experiment tested 1,000 randomly generated bandlimited functions across sampling rates and difference orders.Source: B. Exploring Sharpness of the… · p. 20

C. Quantization and Bounded Noise

  • 5.1×10−3 MSE between γ and its estimate eγ matched the MSE between y and yη, and was below the 3 × 10−1 MSE for 3-bit non-modulo quantization.The experiment used modulo samples with quantization noise of approximately λ/8; Fig. 7 illustrates the recovery.Source: C. Quantization and Bounded Noise · p. 20, Figure 7 · p. 21

A. Summary of Results

  • For Ω-bandlimited signals, T ≤ 1/(2Ωe) guarantees recovery; modulo samples uniquely characterize signals above critical density, and Theorem 3 establishes stability to bounded noise.Source: A. Summary of Results · p. 21

B. Future Directions

  • Practical implementation remains future work, including addressing hardware inaccuracies and instabilities, timing jitter, and the greater noise sensitivity of ADCs without anti-aliasing filters.Source: B. Future Directions • · pp. 21–22
  • Extending the results to smooth, sparse, and parametric signal classes remains open, alongside questions about multidimensional models on arbitrary lattices.The paper also notes prior partial answers and recent discussion of unlimited sampling in spline-spaces.Source: B. Future Directions • · p. 22
  • The framework may combine with other inverse problems; the paper cites the Modulo Radon Transform for high-dynamic-range computed tomography as an example.Source: B. Future Directions • · p. 22
  • The framework may also combine with sampling architectures such as sigma-delta modulation for one-bit recovery and multi-channel acquisition.Source: B. Future Directions • · p. 22
  • The method is not yet stable to outliers, and recovery under unbounded Gaussian or Poissonian noise remains a proposed direction.Source: B. Future Directions • · p. 22
Loading 1905.03901v2…