In this dissertation, a new cubic-spline interpolation (CSI) for both one-dimensional and two-dimensional signals is developed to sub-sample signal, image and video compression data. This new interpolation scheme that is based on the least-squares method with a cubic-spline function can be implemented by the fast Fourier transform (FFT). The result is a simpler and faster interpolation scheme than can be obtained by other conventional means. It is shown by computer simulation that such a new CSI yields a very accurate algorithm for smoothing. Linear interpolation, linear-spline interpolation, cubic-convolution interpolation and cubic B-spline interpolation tend to be inferior in performance. In addition it is shown in this dissertation that the CSI scheme can be performed by a fast and efficient computation. The proposed method uses a simpler technique in the decimation process. It requires substantially fewer additions and multiplications than the original CSI algorithm. Moreover, a new type of overlap-save scheme is utilized to solve the boundary-condition problems that occur between two neighboring subimages in the actual image. It is also shown in this dissertation that a very efficient 9-point Winograd discrete Fourier transform (Winograd DFT) can be used to replace the FFT needed to implement the CSI scheme. Furthermore, the proposed fast new CSI scheme is used along with the Joint Photographic Experts Group (JPEG) standard to design a modified JPEG encoder- decoder for image data compression. As a consequence, for higher compression ratios the proposed modified JPEG encoder-decoder obtains a better quality of reconstructed image and also requires less computational time than both the conventional JPEG method and the America on Line (AOL) algorithm. Finally, the new fast CSI scheme is applied to the JPEG 2000, MPEG-1 and MPEG-2 algorithms, respectively. A computer simulation shows that in the encoding and decoding, the proposed modified JPEG 2000 encoder-decoder speeds up the JPEG 2000 standard, respectively, and still obtains a good quality of reconstructed image that is similar to JPEG 2000 standard for high compression ratios. Additionally, the reconstructed video using the modified MPEG encoder-decoder indicates a better quality than the conventional MPEG-1 and MPEG-2 algorithms for high compression ratios or low-bit rates.