Compressed sensing, quantization and quasi-isometric embedding

Abstract: The advent of Compressed Sensing (CS) ten years ago has precipitated a radical re-thinking of signal acquisition, sensing, processing and transmission system design. A significant aspect of such systems is quantization (or digitization) of the acquired data before further processing or for the purpose of transmission and compression. Recent literature has tackled various aspects of quantization for CS systems and a large body of work has produced results that are often counter to the intuition stemming from classical sensing system design. This presentation will focus on several scalar quantization procedures of compressive signal measurements, starting from high-resolution scalar quantization till the extreme 1-bit quantization retaining only the sign of compressive measurements. We will stress the impact of the non-linear transformation induced by quantization on the signal reconstruction guarantees. Conversely to former attempts considering quantization distortion as an additive Gaussian measurement noise, a “signal consistency quest” will be pursued here: we will study geometrically the theoretical upper and lower bounds that any reconstruction methods must respect when their sparse solutions are consistent with the quantized observations. This will lead us to analyze new embedding relations between the sparse signals set and its quantized random projections. Interestingly, these embeddings differ from the common restricted isometry property (RIP) in that they contain an additive distortion term, that is, they display a quasi-isometric nature directly connected to the information loss induced by quantization.