We have developed a novel strategy for simultaneous interpolation and denoising of prestack seismic data. Most seismic surveys fail to cover all possible source-receiver combinations, leading to missing data especially in the midpoint-offset domain. This undersampling can complicate certain data processing steps such as amplitude-variation-with-offset analysis and migration. Data interpolation can mitigate the impact of missing traces. We considered the prestack data as a 5D multidimensional array or otherwise referred to as a 5D tensor. Using synthetic data sets, we first found that prestack data can be well approximated by a low-rank tensor under a recently proposed framework for tensor singular value decomposition (tSVD). Under this low-rank assumption, we proposed a complexity-penalized algorithm for the recovery of missing traces and data denoising. In this algorithm, the complexity regularization was controlled by tuning a single regularization parameter using a statistical test. We tested the performance of the proposed algorithm on synthetic and real data to show that missing data can be reliably recovered under heavy downsampling. In addition, we demonstrated that compressibility, i.e., approximation of the data by a low-rank tensor, of seismic data under tSVD depended on the velocity model complexity and shot and receiver spacing. We further found that compressibility correlated with the recovery of missing data because high compressibility implied good recovery and vice versa.