# Connexions

You are here: Home » Content » An Introduction to Compressive Sensing » Sparse error correction

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

# Sparse error correction

Module by: Mark A. Davenport. E-mail the author

Summary: This module illustrates the application of the ideas of compressive sensing to the design and decoding of error correcting codes for vectors of real numbers subject to sparse corruptions.

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 xx with MM entries is coded by taking length-NN linearly independent codewords {φ1,....φM}{φ1,....φM}, with N>MN>M and summing them using the entries of xx as coefficients. The received message is a length-NN code y=m=1Mφixi=Φfy=m=1Mφixi=Φf, where ΦΦ is a matrix that has the different codewords for columns. We assume that the transmission channel corrupts the entries of yy in an additive way, so that the received data is y=Φx+ey=Φx+e, where ee 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 ee — therefore making it possible to correct it and obtain the signal xx — when ee is sufficiently sparse [1]. To estimate the error, we build a matrix ΘΘ that is a basis for the orthogonal subspace to the span of the matrix ΦΦ, i.e., an (N-M)×N(N-M)×N matrix ΘΘ that holds ΘΦ=0ΘΦ=0. When such a matrix is obtained, we can modify the measurements by multiplying them with the matrix to obtain y˜=Θy=ΘΦx+Θe=Θey˜=Θy=ΘΦx+Θe=Θe. If the matrix ΘΘ is well-suited for CS (i.e., it satisfies a condition such as the restricted isometry property) and ee is sufficiently sparse, then the error vector ee can be estimated accurately using CS. Once the estimate e^e^ is obtained, the error-free measurements can be estimated as y^=y-e^y^=y-e^, and the signal can be recovered as x^=Φy^=Φy-Φe^x^=Φy^=Φy-Φe^. As an example, when the codewords φmφm have random independent and identically distributed sub-Gaussian entries, then a KK-sparse error can be corrected if M<N-CKlogN/KM<N-CKlogN/K for a fixed constant CC (see "Matrices that satisfy the RIP").

## References

1. Candès, E. and Rudelson, M. and Tao, T. and Vershynin, R. (2005, Oct.). Error correction via linear programming. In Proc. IEEE Symp. Found. Comp. Science (FOCS). Pittsburg, PA

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks