We develop a link between degree estimates for rational sphere maps and compressed sensing. We provide several new ideas and many examples, both old and new, that amplify connections with linear programming. We close with a list of ten open problems.