Insufficient sampling is a key problem that affects seismic data-processing techniques. Although existing interpolation methods can fill in large gaps in the data under certain assumptions, their performance degrades as shot and receiver sampling becomes coarser. Most existing data-interpolation techniques overcome insufficient sampling by making assumptions regarding either the statistical properties of the data or the physics that explain the data. Recognizing that statistical and physics-based constraints can be expressed as convex sets, we propose overcoming some of the deficiencies of existing methods by incorporating multiple types of prior information and equations describing the mapping between different types of data into a mathematically consistent framework based on the projection onto convex sets (POCS) methodology. The proposed method is easy to implement in practice because it relies only upon the iterative application of projection operators (e.g., soft thresholding). At the same time, full advantage of various forms of prior information can be taken. Using a synthetic example of combining conventional streamer and ocean-bottom–cable (OBC) data, we show that our method provides substantial improvement compared to using statistical assumptions alone. Other potential applications include data reconstruction in the case of over-under streamer acquisition, dual-sensor streamer acquisition, multi-azimuth surveys, and vertical seismic profiling.