PaperlayerView exact revision on arXiv

Source-linked AI summary

Unlimited Sampling from Theory to Practice: Fourier-Prony Recovery and Prototype ADC

Ayush Bhandari, Felix Krahmer, Thomas Poskitt

arXiv:2105.05818v1cs.ITeess.SPmath.IT

TL;DR

High-dynamic-range recovery from modulo samples is complicated in practice by non-ideal folds that violate the residue condition used by earlier methods. This paper introduces a Fourier-domain recovery algorithm and tests it with a prototype ADC, reporting hardware recovery up to 24× the ADC threshold. Its signal model assumes a known number of folds.

Abstract

from arXiv · show

Following the Unlimited Sampling strategy to alleviate the omnipresent dynamic range barrier, we study the problem of recovering a bandlimited signal from point-wise modulo samples, aiming to connect theoretical guarantees with hardware implementation considerations. Our starting point is a class of non-idealities that we observe in prototyping an unlimited sampling based analog-to-digital converter. To address these non-idealities, we provide a new Fourier domain recovery algorithm. Our approach is validated both in theory and via extensive experiments on our prototype analog-to-digital converter, providing the first demonstration of unlimited sampling for data arising from real hardware, both for the current and previous approaches. Advantages of our algorithm include that it is agnostic to the modulo threshold and it can handle arbitrary folding times. We expect that the end-to-end realization studied in this paper will pave the path for exploring the unlimited sampling methodology in a number of real world applications.

I. INTRODUCTION

The Unlimited Sensing Framework uses hardware and algorithms together to recover high-dynamic-range signals beyond an ADC’s threshold. It folds the continuous-time input before sampling, leaving an inverse problem of recovering the signal from folded measurements.

I. INTRODUCTION

  • Signals above an ADC’s threshold λ produce clipped or saturated samples, so Nyquist-Shannon sampling theory no longer applies to them.The framework targets signals whose maximum amplitude exceeds λ when the ADC measures up to 2λ peak-to-peak.Source: §I · p. 3
  • The Unlimited Sensing Framework co-designs hardware and algorithms to recover high-dynamic-range signals beyond the ADC threshold.Its hardware folds the continuous-time signal through a modulo nonlinearity before sampling.Source: §I · p. 3
  • Recovering a signal from folded measurements is an ill-posed inverse problem; earlier approaches –[3] use commutativity properties of the modulo nonlinearity.The paper reviews those approaches and their reconstruction guarantees in the following subsection.Source: §I · p. 3

A. Overview of Unlimited Sampling and Reconstruction

The overview presents unlimited sampling as recovery from modulo samples with a sufficient oversampling condition tied to signal bandwidth. Its reconstruction method uses finite differences and bandlimited-function properties to recover the signal, with stability and noise behavior depending on the setting.

A. Overview of Unlimited Sampling and Reconstruction

  • T ≤ 1/(2ωmaxe) is a sufficient sampling condition for recovering a bandlimited function from modulo samples up to an additive constant.The result gives constant-factor oversampling; ωmax is the maximum frequency and e is Euler’s constant.Source: A. Overview of Unlimited Sampling and… · p. 3
  • The sampling criterion is independent of λ and depends only on signal bandwidth, but reconstruction becomes less stable to noise for large amplitudes.For local reconstruction from a finite set of modulo samples, the required sampling rate instead grows with dynamic range relative to λ.Source: A. Overview of Unlimited Sampling and… · p. 3
  • The hardware demonstration folds a 20 V peak-to-peak input (≈10λ) to 4.025 V peak-to-peak and reports testing recovery up to 24λ.The figure shows the continuous-time ground truth and its folded version.Source: Figure 1 · p. 3
  • The recovery procedure estimates successive differences of εg to obtain εγ, then reconstructs the signal as γ = y + εγ.The method uses the restriction εγ ∈ 2λZ and bandlimited-function properties to estimate constants needed when inverting differences.Source: A. Overview of Unlimited Sampling and… · p. 4
  • Stability combines the range restriction εg ∈ 2λZ with bandlimited-function constraints, enabling orders N > 1 unlike similar methods restricted to low orders.The cited comparison also relates those methods to Itoh’s phase-unwrapping method.Source: A. Overview of Unlimited Sampling and… · p. 4

B. Related Work

Related work extends modulo-sampling recovery across quantized, finite-length, noisy, and other signal settings. The overview also contrasts the prototype’s Fourier-domain reconstruction with earlier unlimited-sampling recovery when non-ideal folds break its residue condition.

B. Related Work

  • Prior work studies modulo recovery with quantization and side information, uniqueness above Nyquist rates,, and finite-length signals,.The constructive method in assumes a subset of unfolded samples is known.Source: B. Related Work · p. 4
  • Using Bernstein’s inequality, the method recovers the unknown polynomial in the kernel of Δ^N up to a constant; a key difficulty is estimating an unknown kernel constant each time Δ is inverted.Source: B. Related Work · p. 4
  • With non-ideal folds, the residue no longer lies on 2λZ, and Fig. 2 reports erroneous recovery by [3] versus near-perfect reconstruction by the Fourier-domain approach.The figure traces the non-ideal mapping, sparse first-difference representation, residue recovery, and reconstructed signal.Source: Figure 2 · p. 5
  • Related extensions address sparse signals, one-bit and multi-channel sampling,, wavelet reconstruction, and denoising under bounded or Gaussian noise.Other work considers recovery of multidimensional functions, spline spaces, modulo Radon transforms, tomography, and sensor-array processing –,.Source: B. Related Work · p. 5

C. Motivation and Contributions

Prototype experiments revealed non-ideal folds that violate the residue condition used by earlier recovery, as well as a stability trade-off between difference order and oversampling. The paper responds with a threshold-agnostic Fourier-domain method and a custom US-ADC, while limiting its signal model to finite-dimensional periodic bandlimited signals.

C. Motivation and Contributions

  • Hardware folds can be delayed or include spurious jumps and threshold inaccuracies, leaving a piecewise-constant residue that no longer belongs to 2λZ and makes earlier recovery erroneous.The authors attribute these artifacts to electronic limits on folding rate and say their method avoids the need for careful calibration to input bandwidth.Source: C. Motivation and Contributions · p. 5
  • Using lower finite-difference orders for stability requires higher oversampling, motivating recovery methods that combine moderate oversampling with low N.The stated condition TΩe ≤ 1 ensures the earlier recovery identity for some N, but smaller N is desirable in practice.Source: C. Motivation and Contributions · p. 5
  • The authors propose a Fourier-domain recovery algorithm for hardware non-idealities and lower sampling rates, and validate unlimited sampling on a custom-designed USF-based prototype ADC.The experiments report recovery of signals as large as 24× the ADC threshold and validate earlier approaches [3].Source: C. Motivation and Contributions · p. 6
  • The method is agnostic to λ and computes only Δ1, while the approach in [3] computes ΔN, which can be sensitive to hardware artifacts.The paper’s signal model is periodic, bandlimited, and finite-dimensional—trigonometric polynomials of finite degree—rather than the infinite-dimensional model of earlier work.Source: C. Motivation and Contributions · p. 6
  • The notation defines real, integer, and complex number sets and the mean squared error between vectors.It also denotes IK = {0, …, K − 1} as the set of K contiguous integers.Source: C. Motivation and Contributions · p. 6

II. FOURIER DOMAIN RECONSTRUCTION APPROACH

The reconstruction model treats the bandlimited signal as periodic and represents the non-ideal modulo operation through a piecewise-constant residue. It uses Fourier-domain samples under a critical sampling condition and includes exact modulo sampling as a special case.

II. FOURIER DOMAIN RECONSTRUCTION APPROACH

  • The signal model assumes a bandlimited, τ-periodic function and represents its generalized residue using piecewise-constant values.The residue coefficients are unrestricted, unlike in [3].Source: §II · pp. 6–7
  • For P = ⌈Ω/ω0⌉, the critical sampling condition is T ⩽ τ/(2P + 1).With KT = τ, this condition applies to the Fourier representation of the periodic bandlimited signal.Source: §II · p. 6
  • The non-ideal modulo operator subtracts a piecewise-constant function with finitely many discontinuities from the bandlimited signal.The exact modulo operation is a special case, making the algorithm compatible with the sampling model in [3].Source: §II · pp. 6–7

A. Recovery Approach

The recovery method separates the bandlimited signal’s Fourier coefficients from the contribution of non-ideal folding, then estimates folding parameters using spectral estimation. A theorem gives a sufficient recovery condition for periodic signals, while the paper also describes a theoretical nonperiodic case.

A. Recovery Approach

  • The folding residual cannot be removed by modulo-amplitude filtering when its coefficients are not in 2λZ, and median filtering yields an inexact solution.The number of folding terms depends on the signal’s dynamic range relative to λ.Source: A. Recovery Approach · p. 7
  • Out-of-band Fourier coefficients isolate the contribution of the non-bandlimited folding residual, which is modeled as a sum of complex exponentials.The method uses Prony’s method to identify a filter whose roots encode the folding instants, then estimates the residual coefficients.Source: A. Recovery Approach · pp. 7–8
  • Theorem 2 gives a sufficient condition for recovering a τ-periodic bandlimited signal, up to a constant, from K modulo samples folded at most M times.The stated condition includes T ⩽ τ/K.Source: A. Recovery Approach · p. 9
  • The proof recovers the folding instants from polynomial roots, estimates residual coefficients by least squares, and combines the residuals with modulo samples to recover unfolded samples.The recovered unfolded samples are determined up to an additive constant.Source: A. Recovery Approach · p. 9
  • The nonperiodic case has a theoretical guarantee with infinite samples when DTFT support copies are separated by at least Ω + 2M + 1.The paper notes that periodicity enables its practical recovery approach.Source: A. Recovery Approach · p. 9

B. Summary of Recovery Algorithm

The algorithm transforms first differences of the folded samples into the Fourier domain, estimates folding parameters from out-of-band coefficients, and reconstructs the bandlimited signal from corrected samples.

B. Summary of Recovery Algorithm

  • The algorithm differences the folded samples and computes their DFT, using out-of-band coefficients to isolate the folding parameters.Those coefficients are attributed solely to the residue’s parameters under the Fourier partition.Source: B. Summary of Recovery Algorithm · p. 9
  • Spectral estimation yields folding-time and residue-coefficient estimates, which are used to estimate the residual samples.The algorithm uses a Toeplitz matrix and polynomial roots in its fold-estimation step.Source: B. Summary of Recovery Algorithm · pp. 9–10
  • The estimated residual is used to invert the first-difference operation and form unfolded samples from the modulo samples, up to an unknown constant.The algorithm then applies sinc interpolation to estimate the continuous-time bandlimited signal.Source: B. Summary of Recovery Algorithm · pp. 9–10

1) Implementation Strategy:

The reconstruction is exact without noise; hardware uncertainties can be handled with Matrix Pencil stabilization, whose tuning parameter is difficult to optimize in practice.

1) Implementation Strategy:

  • In noise-free conditions, the method recovers unfolded samples exactly; Matrix Pencil can stabilize reconstruction under noise and hardware uncertainty.Its pencil parameter is not straightforward to tune in practice, so experiments use the choice yielding the best reconstruction.Source: 1) Implementation Strategy · p. 10

III. HARDWARE EXPERIMENTS

The US-ADC prototype was tested on modulo samples of bandlimited signals, including high-dynamic-range inputs, to evaluate the Fourier-domain recovery approach against unlimited sampling. Experiments covered compatibility, non-ideal folds, lower sampling rates, clustered folds, and hardware-scale voltage reconstruction.

Experimental Protocol

  • Across experiments, the prototype simultaneously acquires bandlimited signals and modulo samples; reconstruction MSE is compared for the proposed method and unlimited sampling with fixed or optimized λ.The oscilloscope’s built-in 8-bit sampler provides waveform samples for ground truth, and those measurements are quantized.Source: §III · pp. 10–11

Hardware Prototype

  • The hardware circuit transforms continuous-time inputs into continuous-time modulo outputs and folds signals up to 24λ; the experiments test recovery of signals as large as 48 Vpp and 58 Vpp.The prototype is presented as implementing the unlimited sampling pipeline.Source: §III · p. 10, Figure 4 · p. 11

Experiment 1: Backwards Compatibility with the Unlimited Sampling Approach

  • In Experiment 1, the proposed approach achieves E(γ, eγFD) = 3.838 × 10−4, a factor of 10 improvement over unlimited sampling, and is comparable to λ-optimized recovery.The signal’s dynamic range is ργ = 19.866 Vpp, about 10 times the US-ADC threshold; the reconstruction uses M = 20 folds.Source: §III · p. 12, Figure 5 · p. 12

Experiment 2: Moderate Number of Non-ideal Folds

  • For Experiment 2, E(γ, eγFD) = 3.43 × 10−4 versus E(γ, eγUS) = 3.7; optimizing λ lowers E(γ, eγUSopt) to 1.87 × 10−2, still two orders worse.With λopt = 1.48, the reconstruction error falls from E(γ, eγUS) = 3.7 to E(γ, eγUSopt) = 18.7 × 10−3; the Fourier approach estimates the breaking points for a proposed hybrid approach.Source: §III · p. 13, Figure 6 · p. 13

Experiment 3: Recovery where Unlimited Sampling Requires Higher Order Differences

  • At T = 1 ms, the Fourier-based approach recovers accurately even though the sampling rate violates the numerical condition |∆x| ⩽ λ required for unlimited sampling with first-order differences.The rate satisfies Theorem 2’s condition, and the experiment illustrates recovery where unlimited sampling requires higher-order differences.Source: §III · p. 13, Figure 7 · p. 14

Experiment 4: Recovery of Burst Signals with Clustered Folds

  • With M = 48 clustered folds, the proposed approach reconstructs the burst signal accurately at (TFD/T) ≈ 1.78, with E(γ, eγFD) = 9.37 × 10−3.The authors note that clustered folds challenge the algorithm’s super-resolution step, which works best for few, well-separated spikes.Source: §III · p. 13, Figure 8 · p. 14

Experiment 5: High Dynamic Range Reconstruction

  • For the uncalibrated ≈48 Vpp UK mains signal, the reconstruction’s Fourier spectrum shows a 50.018 Hz spike despite M = 161 folds; unlimited sampling fails on these non-ideal measurements.The authors attribute the recovery to accurate modeling, exact knowledge of M, and oversampling that avoids algorithmic challenges.Source: §III · p. 14
  • For the calibrated ≈58 Vpp input, non-ideal measurement jumps make unlimited sampling sub-optimal, while optimizing λ enhances its reconstruction performance.The oscilloscope’s built-in ADC provides ground truth for this experiment.Source: §III · pp. 14–15, Figure 10 · p. 15

IV. CONCLUSIONS AND TAKE-HOME MESSAGE

The paper introduces a Fourier-domain recovery approach for finite-dimensional folded signals that is robust to observed hardware non-idealities and agnostic to the sensing threshold. Its Fourier-domain formulation enables recovery with arbitrarily close folding instants, while the conclusion identifies known fold count and unmodeled noise as open boundaries.

IV. CONCLUSIONS AND TAKE-HOME MESSAGE

  • The Fourier-domain algorithm is robust to non-idealities observed in hardware-prototype experiments.The paper presents it as a novel solution approach to recovery from modulo measurements.Source: §IV · p. 16
  • Designed for finite-dimensional folded signals, the algorithm is agnostic to the sensing threshold λ.Source: §IV · p. 16
  • Isolating modulo folds in the Fourier domain turns recovery into frequency estimation using high-resolution spectral estimation, allowing arbitrarily close folding instants.Source: §IV · p. 16
  • The method assumes the number of folds is known, and the Fourier-domain analysis does not yet account for noise.The authors identify estimating fold count and extending the analysis to noise as future work.Source: §IV · p. 16
  • Recovery is also bounded by spectral-estimation limits, including limits on the number of spikes recoverable by current approaches.The authors propose investigating hybrid methods that use the Fourier-domain approach for non-ideality spikes and the original method for other spikes.Source: §IV · p. 16
Loading 2105.05818v1…