Embracing nonuniform samples

Many empirical studies suggest that samples of continuous-time signals taken at locations randomly deviated from an equispaced grid can benefit signal acquisition (e.g., undersampling and anti-aliasing). However, rigorous statements of such advantages and the respective conditions are scarce in the literature. This thesis provides some theoretical insight on this topic when the deviations are known and generated i.i.d. from a variety of distributions. By assuming the signal of interest is s-compressible (i.e., can be expanded by s coefficients in some basis), we show that O(s polylog(N))$ samples randomly deviated from an equispaced grid are sufficient to recover the N/2-bandlimited approximation of the signal. For sparse signals (i.e., s ≪ N), this sampling complexity is a great reduction in comparison to equispaced sampling where O(N) measurements are needed for the same quality of reconstruction (Nyquist-Shannon sampling theorem). The methodology consists of incorporating an interpolation kernel into the basis pursuit problem. The main result shows that this technique is robust with respect to measurement noise and stable when the signal of interest is not strictly sparse. Analogous results are provided for signals that can be represented as an N × N matrix with rank r. In this context, we show that O(rN polylog (N)) random nonuniform samples provide robust recovery of the N/2-bandlimited approximation of the signal via the nuclear norm minimization problem. This result has novel implications for the noisy matrix completion problem by improving known error bounds and providing the first result that is stable when the data matrix is not strictly low-rank.Science, Faculty ofMathematics, Department ofGraduat