RIP bounds for naively subsampled Scrambled Fourier sensing matrices

We present an analysis concerning the RIP of naively (deterministically) subsampled DFT and Scrambled DFT (SDFT) matrices. First, we show that for an s-sparse vector of length K, O(s logK) or O (s√K) measurements suffice for a SDFT sensing matrix to satisfy the RIP-δ_s with constant but arbitrarily high probability (with the latter bound holding with greater probability than the former, for the same multiplicative constant). Second, we show that the same RIP bounds hold for any deterministically subsampled DFT matrix, assuming an equiprobable sparsity pattern model for the set of the regression vectors of interest. To the best of our knowledge, the results presented in this work are the first to demonstrate logarithmic dependence of the required number of measurements on the dimension of the sparse vectors of interest, K, for deterministically subsampled Fourier and Scrambled Fourier matrices.