✔️ Universal Sampling Setss
✔️ 1 Introduction
Subsampling an image is often used for compression or computational purposes (i.e. to work with less pixels). The problem of when an image (or any DT signal) can be represented by uniformly spaced subsamples is answered by the Shannon-Nyquist sampling theorem. Under an appropriate band-limiting condition, a DT signal can be perfectly reconstructed from these subsamples. Using the framework of universal sampling sets, we can generalize this idea to work with non-uniformly spaced subsamples [1]. For one-dimensional, length N DT signals f[n], a universal sampling set is a set of indices {mi} ⊂ {1, 2, . . . , N} such that any J -bandlimited signal f[n] can be reconstructed from the samples f[mi]. A J -bandlimited signal is a signal whose DFT is supported only on the set of indices J . If N is a prime power p k
, then [1] gives a complete characterization of all such universal sampling sets.2 Project
For this project I plan to investigate the use of universal sampling sets in subsampling
and reconstructing images. I will take images which are relatively sparse in the DFT
domain (such as the radiograph images from HW4), and construct universal sampling
sets according to their size. For two dimensional signals, the cartesian product of two
one-dimensional universal sampling sets can be used. So, for the example of a 512 × 512
image, we could find any universal sampling set for length 512 = 29 signals via the results from [1] and form the cartesian product of it with itself. Using this universal sampling set I will subsample the image and attempt to reconstruct it. The interesting part will be to see how faithfully an image can be reconstructed and to what extent noise affects the reconstruction. Using this method, the reconstruction algorithm amounts to inverting a
specific submatrix of the DFT matrix, and requires knowledge of the bandlimit set J .
As a final part of this project, time-permitting, I will compare the results of this
reconstruction to those from popular compressed sensing methods such as the CoSaMP
algorithm [4]. These methods have the nice property that the support J does not need
to be known, although they generally do require more samples than simply the sparsity
|J |. I will not be using an android device for this project.
✔️ Bibliography
[1] Brad Osgood, Aditya Siripuram, and William Wu, Discrete Sampling and Interpolation: UniversalSampling Sets for Discrete Bandlimited Spaces, IEEE Transactions on Information Theory 58 (2012),4176-4200.
[2] Aditya Siripuram, William Wu, and Brad Osgood, Discrete Sampling and Interpolation: OrthogonalInterpolation for Discrete Bandlimited Signals (Accesed 10/28/2015), available at http://arxiv.org/abs/1411.7086.
[3] Boris Alexeev, Jameson Cahill, and Dustin G Mixon, Full Spark Frames, The Journal of FourierAnalysis and Applications 18 (2012), 1167-1194.
[4] D. Needell and J. A. Tropp, CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples (Accessed 4/7/2014), available at http://arxiv.org/pdf/0803.2392v2.pdf.
SOURCE CODE CLICK HERE
0 Comments