With respect to gower's gowers' comment, I have a few recommendations about how you might move in a continuous path from algebraic geometry to compressed sensing. I know very little about compressed sensing myself, but some of my colleagues work in the field.
I believe Venkat Chandrasekaran's work with Pablo Parrilo et al. on rank-sparsity incoherence (check Venkat's website) uses some tools from AG. I think this may also be true of Ben Recht's work with Pablo et al. on nuclear norm minimization as a surrogate for rank minimization.
In general, it seems reasonable that problems of finding low-rank solutions to equations are much more interesting from an AG perspective than those of "classical" compressed sensing in which one merely wishes to find sparse solutions. Surely there are many settings in which rank-minimization problems arise beside the two I mentioned above.
