The NASA InSight lander successfully placed a seismometer on the surface of Mars. Alongside, a hammering device was deployed that penetrated into the ground to attempt the first measurements of the planetary heat flow of Mars. The hammering of the heat probe generated repeated seismic signals that were registered by the seismometer and can potentially be used to image the shallow subsurface just below the lander. However, the broad frequency content of the seismic signals generated by the hammering extends beyond the Nyquist frequency governed by the seismometer's sampling rate of 100 samples per second. Here, we propose an algorithm to reconstruct the seismic signals beyond the classical sampling limits. We exploit the structure in the data due to thousands of repeated, only gradually varying hammering signals as the heat probe slowly penetrates into the ground. In addition, we make use of the fact that repeated hammering signals are sub-sampled differently due to the unsynchronised timing between the hammer strikes and the seismometer recordings. This allows us to reconstruct signals beyond the classical Nyquist frequency limit by enforcing a sparsity constraint on the signal in a modified Radon transform domain. Using both synthetic data and actual data recorded on Mars, we show how the proposed algorithm can be used to reconstruct the high-frequency hammering signal at very high resolution. In this way, we were able to constrain the seismic velocity of the top first meter of the Martian regolith.