This paper considers the model problem of recovering an input vector f ? R n from corrupted measurements y = Af +e. Here, A is an m by n matrix (we will assume throughout the paper that m > n), and e is an arbitrary and unknown vector of errors. The problem we consider is whether it is possible to recover f exactly from the data y. And if so, how?
In its abstract form, our problem is of course equivalent to the classical error correcting problem which arises in coding theory as we may think of A as a linear code; a linear code is a given collection of codewords which are vectors a 1 ,...,a n ? R m the columns of the matrix A. Given a vector f ? R n (the “plaintext”) we can then generate a vector Af in R m (the “ciphertext”); if A has full rank, then one can clearly recover the plaintext f from the ciphertext Af. But now we suppose that the ciphertext Af is corrupted by an arbitrary vector e ? R m giving rise to the corrupted ciphertext Af + e. The question is then: given the coding matrix A and Af + e, can one recover f exactly?
As is well-known, if the fraction of the corrupted entries is too large, then of course we have no hope of reconstructing f from Af + e; for instance, assume that m = 2n and consider two distinct plaintexts f,f and form a vector g ? R m by setting half of its m coefficients equal to those of Af and half of those equal to those of Af .
Decoding by Linear Programming