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.


94A24 Coding theorems (Shannon theory)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94B70 Error probability in coding theory
52B11 \(n\)-dimensional polytopes
Full Text: DOI arXiv