Chapter 5 · Robust, Scalable Recovery

The USF-ARA Algorithm

The proof of Theorem 2 assumes ideal, on-grid folds. Real hardware adds thermal noise and non-ideal folds, and audio arrives in millions of samples. USF-ARA works frame by frame. In each frame, the first difference is a smooth part plus a sparse train of spikes. The DCT separates the two: the audio compacts into low indices, and the spikes spread into every index as cosines. Recover the spikes from the out-of-band coefficients, sum them into the residue, and add it back.

Start from

$\DRX$

Oversampling $\OF$

Bit depth $B$

Thermal noise $\sigma_w/\lambda$

Frame shown $l$

Why the DCT, and Why Out-of-Band

Within frame $l$, the noisy measurements decompose as $\bar y_{l}=\bar g_{l}-\bar\varepsilon_{l}+\bar q_{l}+\bar w_{l}$ (bars denote first differences). In the DCT domain (eq. (14)),

$$\widehat{\bar y}_l[k]=\widehat{\bar g}_l[k]-\widehat{\bar\varepsilon}_l[k]+\widehat{\bar q}_l[k]+\widehat{\bar w}_l[k],$$

where $\widehat{\bar g}_l[k]\approx0$ for $k\ge K$ (energy compaction), and $\widehat{\bar\varepsilon}_l$ is a sum of cosines, one per spike $c_m\delta[n-n_m]$. So the out-of-band coefficients $k\in[K,N_g-2]$ see only the residue and noise. Recovering the residue is a frequency-estimation problem (eq. (16)): spike locations are frequencies, spike heights are amplitudes.

The DCT rather than the DFT: a finite frame is not periodic, and the DFT's implied wrap-around leaks audio energy into every bin. The DCT's even extension avoids the jump at the frame edge, so the audio stays compact.

Algorithm 1 · USF-ARA

for frames $l=1,\dots,L$:
DCT of $\bar y_l$, keep $k\ge K$ (eq. 13)
model order $\widetilde M=|\{n:|\bar y_l[n]|>\epsilon\}|$ (eq. 25)
fit $\mathsf P/\mathsf Q$ by iterative weighted LS (eqs. 18–23)
roots of $\mathsf Q$ → $\{c_m,n_m\}$ (eq. 24)
rebuild $\bar\varepsilon_l$; concatenate
anti-difference → $\varepsilon$; $\tilde g\leftarrow\yq+\varepsilon$

In this demo, line 3–4 is replaced by greedy on-grid matching of cosines to the out-of-band coefficients, with amplitudes snapped to $2\lambda\Z$. The paper's rational-model fit is more robust to non-ideal folds.

Fig. 3 of the paper: visual breakdown of USF-ARA on the Kennedy dataset — **Fig. 3 of the paper.** USF-ARA on the hardware *Kennedy* recording: 3.37 × 10⁶ samples, frames of $N_g=500$. The audio concentrates in DCT indices below about 60; the residue fills the rest.

Fig. 9 of the paper: histograms of frame-wise processing time — **Fig. 9 of the paper.** Frame-wise run time grows with $\DRX$: median 0.003 s per frame for *Ketterle* ($\DRX=6.60$), 0.008 s for *Heart-MM* (7.95), 0.02 s for *AWM* (14.33).

In the paper Section IV: frame-wise model, eqs. (13)–(25), Algorithm 1, model-order estimation with $\epsilon=0.5\lambda$, error mitigation; Section V-F (run time).

Simulation: 1500 samples of a bandlimited signal with $\Omega T=\pi/\OF$, scaled to $\DRX\cdot\lambda$ with $\lambda=0.5$; ideal folds, $B$-bit quantization, then additive Gaussian noise $w$. Frames of $N_g=300$ samples (299 differences). The band edge is set from the known bandwidth: $K=\lceil(N_g-1)/\OF\rceil$ plus a 4% guard. Spike count per frame follows eq. (25) with $\epsilon=0.5\lambda$; greedy matching stops early when the best amplitude rounds to 0. The recovered signal is shown with the unrecoverable global offset taken from the truth.