Seismic data reconstruction on a dense periodic grid from data acquired on a coarse grid allows oil & gas companies to save on operationally challenging and expensive dense seismic data acquisition. Dense seismic data especially at high frequencies is desired for generating highresolution subsurface image for exploration and production decisions. Although, low-rank based data reconstruction methods perform well at lower frequencies and scalable for large data, their performance degrades at higher frequencies due to increase in rank of approximating matrices.