Unlimited Sensing Framework
\[ \require{amssymb ,mathrsfs} \require{mathrsfs} \def\Z{\in \mathbb{Z}} \def\R{\in \mathbb{R}} \def\iC{\in \mathbb{C}} \newcommand{\PW}[1]{\mathsf{PW}_{#1}} \def\T{\mathrm{T}} \def\B{\beta_g} \def\DR{\mathsf{DR}} \def\kn{\kappa_{\l \ell \r}} \def\S{\mathsf{S}} \def\bo{b_0} \newcommand{\rob}[1]{\left( #1 \right)} \def\dtft{\hat{\mathrm{C}}\rob{\w}} \def\dtftm{\hat{\mathrm{C}}_m\rob{\w}} \newcommand{\cmi}[1]{\hat{\mathrm{C}}_{m_{#1}}\rob{\w}} \newcommand{\cmc}[1]{\hat{\mathrm{C}}^*_{m_{#1}}\rob{\w}} \newcommand{\gram}[1]{\mathsf{G}^{\rob{#1}}_{m_1,m_2}\rob{\w}} \newcommand{\todo}[1]{\hl{\sf\small{#1}}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\ft}[1]{\left[\kern-0.15em\left[#1\right]\kern-0.15em\right]} \newcommand{\fe}[1]{\left[\kern-0.30em\left[#1\right]\kern-0.30em\right]} \newcommand{\flr}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\MO}[1]{\mathscr{M}_\lambda\l #1 \r} \newcommand{\VO}[1]{\varepsilon_{#1}} \newcommand{\ab}[1]{{\color{red} #1}} \newcommand{\sqb}[1]{\left[ #1 \right]} \def\l{\left(} \def\r{\right)} \newcommand{\todo}[1]{\hl{\sf\small{#1}}} \newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\ft}[1]{\left[\kern-0.15em\left[#1\right]\kern-0.15em\right]} \newcommand{\fe}[1]{\left[\kern-0.30em\left[#1\right]\kern-0.30em\right]} \newcommand{\flr}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\MO}[1]{\mathscr{M}_\lambda\l #1 \r} \newcommand{\VO}[1]{\varepsilon_{#1}} \newcommand{\ab}[1]{{\color{red} #1}} \newcommand{\sqb}[1]{\left[ #1 \right]} \newcommand{\rob}[1]{\left( #1 \right)} \def\l{\left(} \def\r{\right)} \newcommand{\conv}{\mathop{\scalebox{1}{\raisebox{0ex}{\(\circledast\)}}}}% \def\sdh{\circledast_h} \def\sdH{\circledast_{\mat{H}}} \def\sd{\circledast} \newcommand{\mat}[1]{\mathbf{#1}} \def\Hi{\mathbf{H}^{-1}} \newcommand{\EQc}[1]{\stackrel{(\ref{#1})}{=}} \def\YN{{\color{black}y _{\eta}}} \def\DO{N} \def\Do{n} \newcommand{\lp}[1]{{\ell}_{#1}} \newcommand{\Lp}[1]{\mathbf{L}_{#1}} \newcommand{\normt}[3]{ {\| {#1} \|}_{ {\mathbf{L}_{#2}} \left( #3\right)}} \newcommand{\normT}[3]{ {\| {#1} \|}_{ {\boldsymbol{\ell}_{#2}} \left( #3\right)}} \newcommand{\fk}[1]{{\mathsf{F}}_{#1}} \def\e{\mathrm{e}} \]
The Unlimited Sensing framework is our patented technology (US10651865B2) that allows for recovery of arbitrarily high dynamic range signals from a constant factor oversampling of its low dynamic range samples. Remarkably, the oversampling factor is independent of the maximum recordable voltage.
Conventional sensing systems such as the analog-to-digital convertor saturate or clip whenever the signal crosse the maximum recordable voltage. In contrast, the unlimited sensing strategy is based on a radically new sampling architecture and comes with recovery guarantees.
Sensing Model
The key novelty of our approach is that instead of (potentially clipped) pointwise samples of the bandlimited function, we work with folded amplitudes with values in the range \(\left[ { - \lambda ,\lambda } \right]\). Mathematically, this folding corresponds to injecting a non-linearity in the sensing process. This amounts to,
\[ \begin{equation} \mathscr{M}_{\lambda}:f \mapsto 2\lambda \left( {\fe{ {\frac{f}{{2\lambda }} + \frac{1}{2} } } - \frac{1}{2} } \right), \label{map} \end{equation} \]
where \(\ft{f} = f - \flr{f} \) defines the fractional part of \(f\) and \(\lambda>0\) is the ADC threshold. Note that \(\eqref{map}\) is equivalent to a centered modulo operation. By implementing the mapping \(\eqref{map}\), it is clear that out-of-range amplitudes are folded back into the dynamic range \(\left[ { - \lambda ,\lambda } \right]\). This is shown in Fig:1.
Example of Real Experiment
To appreciate the practical utility of the Unlimited Sampling strategy, here we show an experiment based on our prototype hardware. We show that voltages from the UK Mains (power socket, 50V) can be stored and reconstructed on a digital device such as a µ-controller or a MacBook. This cannot be possible using any existing, digitizing technology which will either saturate or crash.
Recovery — A First Result: The Unlimited Sampling Theorem
Recovery Conditions
In analogy to Shannon’s sampling theorem, our first result [1], 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.
Theorem (BKR, 2017 [1]) Let \(f(t)\) be a function with no frequencies higher than \(\Omega\) (rad/s), then a sufficient condition for recovery of \(f(t)\) from its modulo samples \(y_k = \MO{f(t)}, t = kT\), \(k\in\mathbb{Z}\) is,
\[ \begin{equation} T \leq \frac{1}{2\Omega e}. \label{TUS} \end{equation} \]
Uniqueness Conditions
In fact, there is a one-to-one mapping between a bandlimited function and its modulo samples provides that the sampling rate is higher than the critical rate of the Nyquist rate, \(T<\pi/\Omega\). The Injectivity Conditions are proved in [2].
Theorem (BK, 2019 [2]) Let \(f(t)\) be a finite-energy function with no frequencies higher than \(\Omega\) (rad/s). Then the function \(f(t)\) is uniquely determined by its modulo samples \(y_k = \MO{f(t_k)}\) taken on grid \(t = kT_\epsilon\), \(k\in\mathbb{Z}\) where
\[ 0<T_\epsilon< \frac{\pi}{\Omega+\epsilon}, \quad \epsilon>0. \]
Bounded Noise and Quantization
When working with bounded noise, we assume that the modulo samples \(y[k]\) are affected by noise \(\eta\) of amplitude bounded by a constant \( \bo > 0\). That is,
\[ \begin{equation} \forall k \Z, \quad \YN\left[ k \right] = y[k] + \eta\left[ k \right], \quad \left| {\eta \left[ k \right]} \right| \leqslant {\bo}. \end{equation} \]
Note that due the presence of noise, it may happen that \(\YN [k] \not\in [-\lambda,\lambda]\). Nonetheless, for \(\bo\) below some fixed threshold, our recovery method provably recovers noisy bandlimited samples \(\gamma[k]\) from the associated noisy modulo samples \(\YN[k]\) up to an unknown additive constant, where the noise appearing in the recovered samples is in entry-wise agreement with the one affecting the modulo samples. That is, \(\widetilde \gamma \left[ k \right] = \gamma \left[ k \right] + \eta \left[ k \right] + 2m\lambda, m\in \mathbb{Z}\).
Theorem (BKR, 2020 [3]) Let \(g\l t\r\) be an \(\Omega\)-bandlimited and finite-energy signal. Assume that \(\B\in 2\lambda \mathbb{Z}\) is known with \(\|g\|_\infty\leqslant \B\). For the dynamic range we work with the normalization \(\DR = {\B}/{\lambda}\). Let the noisy modulo samples with a noise bound given in terms of the dynamic range as,
\[ \begin{equation} \label{eq:mns} \left\| \eta \right\|_\infty \leqslant \tfrac{\lambda }{4}{\left( {{{2\cdot\DR}}} \right)^{ - \frac{1}{\alpha}}}, \qquad \alpha \in \mathbb{N}. \end{equation} \]
Then a sufficient condition for approximate recovery of the bandlimited samples \(\gamma[k]\) is that,
\[ \begin{equation} \label{MSBN} T \leqslant \frac{1}{2^\alpha \Omega e}. \end{equation} \]
The recovery is approximate in the sense that, \(\widetilde \gamma \left[ k \right] = \gamma \left[ k \right] + \eta \left[ k \right] + 2m\lambda, m\in \mathbb{Z}\).
Wider Classes of Inverse Problems and Function Spaces
Physical models arising in sciences and engineering are typically modeled as a linear system of equations, namely, \(\mat{y} = \mat{Ax}\). In the context of our work, the modulo non-linearity results in a wider class of inverse problems,
\[ y\rob{t} = \MO{\mathcal{A} x\rob{t}} \]
where \(\mathcal{A}\) is a continuous operator (e.g. low-pass filter or Radon transform) and the goal is to recovery \(x\) from sampled measurements \(y\).
Example 1: High Dynamic Range Imaging
To facilitate imaging beyond the conventional dynamic range, often referred to as high-dynamic-range (HDR) imaging, several algorithmic and hardware solutions have been proposed in the literature. These approaches rely on oversampling. The most common algorithmic solution is to fuse multiple images at different exposures
(Debevec (1997)). Hardware-only solutions use multiple ADCs and are exorbitantly priced. For instance, state-of-the-art ALEV III CMOS sensor designed by ARRI (for cinematography) uses Dual Gain Architecture. As the name suggests, each pixel simultaneously reads information with high and low amplification factors corresponding to clipped and non-clipped values, respectively. Both read-outs are fed to a \(14\)-bit ADC and combined into a single \(16\)-bit HDR image.
As we have pointed out earlier, HDR sensing is an in-built feature of the Unlimited Sensing architecture. However, images are non-bandlimited functions and hence the existing results do no apply. To overcome this bottleneck, we model images as objects in the shift-invariant space spanned by B-splines. Our main result is as follows. For any image \(g\l x \r \in {\sf{V}}_h^\DO \cap \Lp{\infty}\l \mathbb{R} \r \) where \({\sf{V}}_h^\DO\) is the space generated by shifts of B-splines of order \(\DO\) and refinement \(h\), it one has that,
\[ \begin{equation*} \label{MR} \normT{\Delta^\Do \gamma}{\infty}{\mathbb{R}} \leqslant \l\frac{T\pi \e}{h}\r^\Do \l \frac{\fk{\DO-\Do}}{\fk{\DO}} \r \normt{g}{\infty}{\mathbb{R}} , \quad \Do = 0,\ldots,\DO, \mbox{ where } \forall \ \DO \geq 0, \ \ {\mathsf{F}_N = \frac{4}{\pi } {\sum\limits_{k \geq0} \rob{\frac{\rob{-1}^k}{2k+1}}^{N + 1}}} \in \sqb{1,\frac{\pi}{2}}. \end{equation*} \]
The implication is that as shown in [4], the sampling rate,
\[ T < \frac{h}{{\pi e}}{\left( {\frac{\lambda }{{{{\left\| g \right\|}_\infty }\mathsf{C}_{\Do,\DO}}}} \right)^{\frac{1}{\Do}}}, \qquad \mathsf{C}_{\Do,\DO} = \frac{\fk{\DO-\Do}}{\fk{\DO}} \]
guarantees recovery of images modeled by splines. Examples of HDR imaging are shown below.
Example 2: Modulo Tomography
Recent advances in hardware have led to high dynamic range solutions for computed tomography. However, much in the same way as conventional imaging, HDR tomography requires fusion of multiple, calibrated Radon Transform projections. The inherent HDR feature of the modulo non-linearity can be leveraged in this context. To this end, we recently introduced the *Modulo Radon Transform in [6] and practical algorithm for HDR tomography was proposed in [7]. An example of the new approach is shown below.
References
On Unlimited Sampling
Ayush Bhandari, Felix Krahmer and Ramesh Raskar
Intl. Conf. on Sampling Theory and Applications (SampTA), (Jul. 2017).On Identifiability in Unlimited Sampling
Ayush Bhandari and Felix Krahmer
Intl. Conf. on Sampling Theory and Applications (SampTA), (Jul. 2019).On Unlimited Sampling and Reconstruction
Ayush Bhandari, Felix Krahmer and Ramesh Raskar
IEEE Transactions on Signal Processing, (Dec. 2020).HDR Imaging From Quantization Noise
Ayush Bhandari and Felix Krahmer
IEEE Intl. Conf. on Image Processing (ICIP), (Oct. 2020).Unlimited Sampling from Theory to Practice: Fourier-Prony Recovery and Prototype ADC
Ayush Bhandari, Felix Krahmer and Thomas Poskitt
IEEE Transactions on Signal Processing, (Sep. 2021).The Modulo Radon Transform and Its Inversion
Ayush Bhandari, Matthias Beckmann and Felix Krahmer
European Sig. Proc. Conf. (EUSIPCO), (Oct. 2020).The Modulo Radon Transform: Theory, Algorithms, and Applications
Matthias Beckmann, Ayush Bhandari and Felix Krahmer
SIAM Journal on Imaging Sciences, (Apr. 2022).Back in the US-SR: Unlimited Sampling and Sparse Super-Resolution with its Hardware Validation
Ayush Bhandari
IEEE Signal Processing Letters, (Mar. 2022).The Surprising Benefits of Hysteresis in Unlimited Sampling: Theory, Algorithms and Experiments
Dorian Florescu, Felix Krahmer and Ayush Bhandari
IEEE Transactions on Signal Processing, (Jan. 2022).Computational Array Signal Processing via Modulo Non-Linearities
Samuel Fernandez-Menduina, Felix Krahmer, Geert Leus and Ayush Bhandari
IEEE Transactions on Signal Processing, (Mar. 2021).Unlimited Sampling with Sparse Outliers: Experiments with Impulsive and Jump or Reset Noise
Ayush Bhandari
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (May. 2022).Unlimited Sampling with Local Averages
Dorian Florescu and Ayush Bhandari
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (May. 2022).Modulo Event-driven Sampling: System Identification and Hardware Experiments
Dorian Florescu and Ayush Bhandari
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (May. 2022).Unlimited Sampling for FMCW Radars: A Proof of Concept
Thomas Feuillen, Mohammad Alaee-Kerahroodi, Ayush Bhandari, Bhavani Shankar M. R and Bjorn Ottersten
IEEE Radar Conference (RadarConf22), (Mar. 2022).Event-Driven Modulo Sampling
Dorian Florescu, Felix Krahmer and Ayush Bhandari
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (Jun. 2021).Unlimited Sampling with Hysteresis
Dorian Florescu, Felix Krahmer and Ayush Bhandari
55th Asilomar Conf. on Signals, Systems, and Computers, (Oct. 2021).HDR Tomography via Modulo Radon Transform
Matthias Beckmann, Felix Krahmer and Ayush Bhandari
IEEE Intl. Conf. on Image Processing (ICIP), (Oct. 2020).Multidimensional Unlimited Sampling: A Geometrical Perspective
Vincent Bouis, Felix Krahmer and Ayush Bhandari
European Sig. Proc. Conf. (EUSIPCO), (Oct. 2020).DoA Estimation Via Unlimited Sensing
Samuel Fernandez-Menduina, Felix Krahmer, Geert Leus and Ayush Bhandari
European Sig. Proc. Conf. (EUSIPCO), (Oct. 2020).One-bit Unlimited Sampling
Olga Graf, Ayush Bhandari and Felix Krahmer
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (May. 2019).Unlimited Sampling of Sparse Sinusoidal Mixtures
Ayush Bhandari, Felix Krahmer and Ramesh Raskar
IEEE Intl. Sym. on Information Theory (ISIT), (Jun. 2018).Unlimited Sampling of Sparse Signals
Ayush Bhandari, Felix Krahmer and Ramesh Raskar
IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP), (Apr. 2018).Methods and Apparatus for Modulo Sampling and Recovery
Ayush Bhandari, Felix Krahmer and Ramesh Raskar
US10651865B2, (May. 2020).
Assignee: Massachusetts Institute of Technology
MATLAB Code
| Code | DIY Guide for Modulo Sampling Hardware | Link |
| Code & Data | Fourier-Prony Approach for Modulo Sampling | Coming Soon |
| Code & Data | Reconstruction with the Generalized Modulo Sampling Architecture | Coming Soon |