Compressed sensing (aka compressive sampling) is a technique by which, given certain mild constraints based on the uniform uncertainty principal, a sparse signal can be recovered from far fewer samples than the dimensionality of the original signal. An N dimensional signal is first sampled by taking M << N linear combinations of subsets of the original signal. This original signal can be reconstructed at the receiver by performing an ℓ1 minimization of a sparse representation of the original signal subject to a constraint representing the sampling operation.
In a realistic implementation, the minimization constraint will not be based on perfect samples but on a distorted version of those samples. Distortion mainly comes from channel errors (from noise and interference) and from quantization (i.e. precision loss due to quantization). Since the precision loss can be kept very low, the main cause of reconstruction errors is the distortion caused from noise and interference. The error from this distortion will be bounded by a constant amount times the magnitude of the distortion.
In the case of multimedia signals such as audio or video, these reconstruction errors can be directly associated to distortion in the received video or audio file. As the signal is incorrectly reconstructed at the receiver, the quality of the multimedia content will decrease. In the case of video, it can be shown empirically that as the bit error rate increases beyond 10-4, the quality of the reconstructed video will drop off sharply. However, if the incorrect samples are removed from the reconstruction process, the amount of distortion is directly proportional to the number of samples which are incorrect, resulting in an structural similarity (SSIM) loss of only around 1-2% for realistic channels. This is much more error resiliency than is observed in traditional video encoding techniques (such as MPEG-2). A simple adaptive parity error detection scheme can accomplish this for realistic bit error rates with some errors. However, a more sophisticated error detection scheme could potentially allow compressed sensed video to be correctly reconstructed even with very high sample error rates.