Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations

T. S. Jayram, Soumitra Pal, Vijay Arya

We consider a system of m linear equations in n variables Ax=b where A is a given m x n matrix and b is a given m-vector known to be equal to Ax' for some unknown solution x' that…