Full-waveform inversion's high demand on computational resources forms, along with the non-uniqueness problem, the major impediment withstanding its widespread use on industrial-size datasets. Turning modeling and inversion into a compressive sensing problem - where simulated data and/or the model are recovered from a relatively small number of independent simultaneous sources - can effectively mitigate the high cost impediment. The key is in showing that we can design a subsampling operator that commutes with the time-Harmonic Helmholtz system. As in compressive sensing, this leads to a reduction in simulation cost. Moreover, this reduction is commensurate with the transform-domain sparsity of the solution, implying that computational costs are no longer determined by the size of the discretization but by transform-domain sparsity of the solution of the CS problem which forms our data. The combination of this sub-sampling strategy with our recent work on implicit solvers for the Helmholtz equation provides a viable alternative to full-waveform schemes based on explicit time-domain finite-difference methods.