Medical imaging technology efficiency is determined by how accurate, rapid, invasive, or non-invasive it is. Photoacoustic tomography (PAT) is a noninvasive emerging technology for medical imaging that is able to produce images with high resolution and high contrast in long penetration depths. In PAT, image reconstruction accuracy relies on the accuracy of the system model. Accurate model-based methods can be made use of for efficiently reconstructing a PAT image from the sensor measurements using a pseudo-spectral method which is suggested to produce exactly the same results as that of the k-Wave toolbox in MATLAB. Compressive sensing has been successfully applied for medical image reconstruction as it allows for sparse sampling and sparse reconstruction. Compressive sensing combined with PAT allows for deep tissue imaging at higher resolution at a much lower computational time. A fast and efficient PAT image reconstruction compressive sensing algorithm is needed to be developed, which can image dense tissues (such as breast tissue) rapidly, for early detection of cancer. In this paper, relaxed-Basis pursuit using alternating direction method of multipliers and split Bregman formulation of the total variation regularized least-squares problem is proposed and is observed to work under practical scenarios with fewer samples and sensors. Moreover, a comparative study for the performance analysis of the different compressive sensing algorithms, both iterative and non-iterative, is carried out for a decreased number of sensors and samples. The proposed split Bregman total variation algorithm is fast and produces a high-resolution sparsity preserving image compared to the state-of-the-art algorithms. Moreover, for a reduced number of samples, the proposed relaxed-Basis Pursuit is desired and performs much better than all the algorithms discussed. Implementing Cholesky factorization to the proposed algorithms further reduces the computation time of the split-Bregman algorithm by 90%. The new methods outperform existing ones in practical circumstances recreating a high-resolution image, even when the number of sensors and samples is reduced.