The application of compressed sensing (CS) to biomedical imaging is exciting because it allows a reasonably accurate reconstruction of images from far fewer measurements. For biomedical imaging, CS can increase the imaging speed and consequently decrease the radiation dose. While the idea of CS has been used to reduce the acquisition time of magnetic resonance imaging (MRI), x-ray computed tomography (CT) and microwave imaging (MWI), unfortunately the computation time of image recovery has increased as the nonlinear CS reconstruction algorithms are fairly slow. Reconstructing high-dimensional signals or biomedical images from compressively sampled data is a fundamental challenge faced by the CS. In this dissertation, we propose a suite of novel CS recovery methods that can efficiently recover the Fourier encoded biomedical images (MRI, parallel-beam CT and MWI) from a small set of randomized measurements. The initial part of the current work presents CS based reconstruction of sub-sampled biomedical imaging modalities using projection onto convex sets (POCS) and separable surrogate functional (SSF) methods. The iterative shrinkage based SSF algorithm incorporates the linear estimate of the error to improve the reconstruction quality. It does not involve any matrix inversion and is used to estimate the missing Fourier samples of the original image by applying data consistency in the frequency domain and soft thresholding in the sparsifying domain. The idea of using hybrid evolutionary techniques for the sparse signal recovery is presented next. It proposes how to combine the heuristic techniques such as Differential evolution (DE), genetic algorithms (GA), and Particle Swarm Optimization (PSO) with v iterative shrinkage algorithms to faithfully reconstruct sparse signals from a small number of measurements. Based on the notion of GA, a modified POCS based algorithm is developed. This novel CS recovery technique uses two different estimates for the initialization and iteratively combines them to recover the original Fourier encoded image. In the last part, we use hyperbolic tangent function separately to develop a reconstruction algorithm and a non-linear shrinkage curve for thresholding. As the ?1-norm penalty is not differentiable, the proposed hyperbolic tangent based function is used to closely approximate the ?1-norm regularization by a differentiable surrogate function. Using the method of gradient descent, a simple update rule is developed. The algorithm is shown to perform well for one dimensional (1-D) sparse signal recovery as well as CS reconstruction of Fourier encoded biomedical imaging. The idea is further extended by using hyperbolic tangent based approximations for the soft-thresholding that provide flexibility in terms of its adjustable parameters. Besides using synthetic data, the effectiveness of the proposed techniques are also validated using the real data collected from the MRI and MWI scanners.