Efficient Deterministic Compressed Sensing for Images with Chirps and Reed-Muller Codes

A recent approach to compressed sensing using deterministic sensing matrices formed from discrete frequency-modulated chirps or from Reed-Muller codes is extended to support efficient deterministic reconstruction of signals that are much less sparse than envisioned in the original work. In particular, this allows the application of this approach in imaging. The reconstruction algorithm developed for images incorporates several new elements to improve computational complexity and reconstruction fidelity in this application regime.