Reusable low-error compressive sampling schemes through privacy

A compressive sampling algorithm recovers approximately a nearly sparse vector x from a much smaller “sketch” given by the matrix vector product Φ_x. Different settings in the literature make different assumptions to meet strong requirements on the accuracy of the recovered signal. Some are robust to noise (that is, the signal may be far from sparse), but the matrix Φ is only guaranteed to work on a single fixed x with high probability-it may not be re-used arbitrarily many times. Others require Φ to work on all x simultaneously, but are much less resilient to noise. In this note, we examine the case of compressive sampling of a RADAR signal. Through a combination of mathematical theory and assumptions appropriate to our scenario, we show how a single matrix Φ can be used repeatedly on multiple input vectors x, and still give the best possible resilience to noise.