# zbMATH — the first resource for mathematics

Geometric approach to error-correcting codes and reconstruction of signals. (English) Zbl 1103.94014
The authors discuss aspects regarding error-correcting and transform coding form three equivalent points of view: the sparse recovery problem, the error-correction and the existence of extremal polytopes. Their results validate the idea of the basis pursuit for most subspaces under asymptotically sharp conditions on $$m,n$$ and $$r$$ where $$m$$ ($$>n$$) is the dimension of the encoded words consisting of $$n$$ letters and $$r$$ is the number of corrupted coordinates in the encoded word. They prove that the basis pursuit yields exact reconstruction for most subspaces in the Grassmanian $$G_{m,n}$$ of $$n$$-dimensional subspaces of $$R^m$$ equipped with the normalized Haar measure. The results are improvements of those reported by Donoho and Candes and Tao.

##### MSC:
 94A24 Coding theorems (Shannon theory) 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 94B70 Error probability in coding theory 52B11 $$n$$-dimensional polytopes
##### Keywords:
error-correcting codes; basis pursuit; sensing; polytopes
Full Text: