It is a well-known fact that the Discrete Fourier Transform (DFT) \vec X of an arbitrary n -length input signal \vec {x} , can be computed from all the n time-domain samples in O( n\log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum k -sparse (where k\ll n ), can we do better? We show that asymptotically in k and n , when k ), where 0 \leq \delta <1 ), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of from O( k) samples of \vec x in O( k\log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when \delta < 0.99 , which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than 4 k . Although, in this paper we assume that the samples of the signal \vec x observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal \vec x is designed to create aliasing patterns of the non-zero coefficients of the spectrum \vec X to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT \vec X is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings. [ABSTRACT FROM PUBLISHER]