Short and smooth sampling trajectories for compressed sensing

This paper explores a novel setting for compressed sensing (CS) in which the sampling trajectory length is a critical bottleneck and must be minimized subject to constraints on the desired reconstruction accuracy. In contrast to the existing CS literature, where the focus is on reducing the number of measurements, this contribution describes a short and smooth sampling trajectory guaranteed to satisfy the Restricted Isometry Property if the underlying signal is sparse in an appropriate basis. A naïve path based on randomly choosing a collection of sample locations and using a Traveling Salesman Problem solver to choose a “short” trajectory is shown to be dramatically longer than the nearly straight and very smooth path proposed in this paper. Theoretical justification for the proposed path is presented, and applications to MRI, electro-magnetics, and ecosystem monitoring are discussed.