Simultaneous marine acquisition is an economic way to sample seismic data and speed up acquisition, wherein single or multiple source vessels fire sources at near-simultaneous or slightly random times, resulting in overlapping shot records. The current paradigm for simultaneous towed-streamer marine acquisition incorporates “low variability” in source firing times, i.e., or 2 s because the sources and receivers are moving. This results in a low degree of randomness in simultaneous data, which is challenging to separate (into its constituent sources) using compressed-sensing-based separation techniques because randomization is key to successful recovery via compressed sensing. We have addressed the challenge of source separation for simultaneous towed-streamer acquisitions via two compressed-sensing-based approaches, i.e., sparsity promotion and rank minimization. We have evaluated the performance of the sparsity-promotion- and rank-minimization-based techniques by simulating two simultaneous towed-streamer acquisition scenarios, i.e., over/under and simultaneous long offset. A field data example from the Gulf of Suez for the over/under acquisition scenario was also developed. We observed that the proposed approaches gave good and comparable recovery qualities of the separated sources, but the rank-minimization technique outperformed the sparsity-promoting technique in terms of the computational time and memory. We also compared these two techniques with the normal-moveout-based median-filtering-type approach, which had comparable results.