A computer-implemented method for correcting transmission errors. According to the method, a transmitted vector corrupted by error can be recovered solving a linear program. The method has applications in the transmission of Internet media, Internet telephony, and speech transmission. In addition, error correction is embedded as a key building block in numerous algorithms, and data-structures, where corruption is possible; corruption of digital data stored on a hard-drive, CD, DVD or similar media is a good example. In short, progress in error correction has potential to impact several storage and communication systems.