Decoding by linear programming
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f is an element of R-n from corrupted measurements y = Af + e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y?
linear programming basis pursuit decoding of (random) linear codes duality in optimization gaussian random matrices l(1) minimization linear codes principal angles restricted orthonormality singular values of random matrices sparse solutions to underdetermined systems