Stolt migration is a Fourier-domain imaging operator that assumes a constant-velocity media. We have developed a multivelocity version of the Stolt migration and demigration operators to derive a transform that can decompose seismic data into a sparse collection of coefficients in the image space. This Stolt-based transform is similar to the apex-shifted hyperbolic Radon transform (ASHRT). However, the Stolt-based transform is considerably faster than the classical ASHRT because it uses two fast operators (forward and inverse fast Fourier transforms) to estimate the data coefficients in the image space. We used this Stolt-based transform as a tool for simultaneous seismic source separation by removing erratic interference noise in common receiver gathers. Estimating the coefficients of interference-free seismic data using the Stolt-based transform was posed as an inverse problem. The solution of this inverse problem was found by minimizing a cost function that included a sparsity-promoting regularization term. In addition, the cost function incorporated a robust misfit function that was not sensitive to erratic interferences. Our tests on synthetic and field data examples determined that this new transform can efficiently remove interference noise and achieve fast simultaneous seismic source separation.