Online Codes for Analog Signals

This paper revisits a classical scenario in communication theory: a waveform sampled at regular intervals is to be encoded so as to minimize distortion in its reconstruction, despite the noise. This transformation must be online (causal), to enable real-time signaling, and should use no more power than the original signal. The noise model we consider is an atomic norm convex relaxation of the standard (discrete alphabet) Hammingweight-bounded model, namely adversarial ℓ_1 -bounded. In the block coding (noncausal) setting, such encoding is possible due to the existence of large almost-Euclidean sections in ℓ_1 spaces, a notion first studied in the work of Dvoretzky in 1961. Our main result is that an analogous result is achievable even casually. Equivalently, our work may be seen as a lower triangular version of ℓ_1 Dvoretzky theorems. In terms of communication, the guarantees are expressed in terms of certain time-weighted norms: the time-weighted ℓ_2 norm imposed on the decoder forces increasingly accurate reconstruction of the distant past signal, while the time-weighted ℓ_1 norm on the noise ensures vanishing interference from distant past noise. Encoding is linear (hence easy to implement in analog hardware). Decoding is performed by an LP analogous to those used in compressed sensing.