6.1 Sparse error correction

In communications, error correction refers to mechanisms that can detect and correct errors in the data that appear duet to distortion in the transmission channel. Standard approaches for error correction rely on repetition schemes, redundancy checks, or nearest neighbor code search. We consider the particular case in which a signal $x$ with $M$ entries is coded by taking length- $N$ linearly independent codewords $\{{\phi }_1,....{\phi }_M\}$ , with $N>M$ and summing them using the entries of $x$ as coefficients. The received message is a length- $N$ code $y={\sum }_{m=1}^M{\phi }_i{x}_i=\Phi f$ , where $\Phi$ is a matrix that has the different codewords for columns. We assume that the transmission channel corrupts the entries of $y$ in an additive way, so that the received data is $y=\Phi x+e$ , where $e$ is an error vector.

The techniques developed for sparse recovery in the context of compressive sensing (CS) provide a number of methods to estimate the error vector $e$ — therefore making it possible to correct it and obtain the signal $x$ — when $e$ is sufficiently sparse [link] . To estimate the error, we build a matrix $\Theta$ that is a basis for the orthogonal subspace to the span of the matrix $\Phi$ , i.e., an $(N-M)\times N$ matrix $\Theta$ that holds $\Theta \Phi =0$ . When such a matrix is obtained, we can modify the measurements by multiplying them with the matrix to obtain $\tilde{y}=\Theta y=\Theta \Phi x+\Theta e=\Theta e$ . If the matrix $\Theta$ is well-suited for CS (i.e., it satisfies a condition such as the restricted isometry property ) and $e$ is sufficiently sparse, then the error vector $e$ can be estimated accurately using CS. Once the estimate $\widehat{e}$ is obtained, the error-free measurements can be estimated as $\widehat{y}=y-\widehat{e}$ , and the signal can be recovered as $\widehat{x}={\Phi }^{†}\widehat{y}={\Phi }^{†}y-{\Phi }^{†}\widehat{e}$ . As an example, when the codewords ${\phi }_m$ have random independent and identically distributed sub-Gaussian entries, then a $K$ -sparse error can be corrected if $M<N-CKlogN/K$ for a fixed constant $C$ (see "Matrices that satisfy the RIP" ).