We demonstrate a photonic system for pseudorandom sampling of multi-tone sparse radio-frequency (RF) signals in an 11.95-GHz bandwidth using <1% of the measurements required for Nyquist sampling. Pseudorandom binary sequence (PRBS) patterns are modulated onto highly chirped laser pulses, encoding the patterns onto the optical spectra. The pulses are partially compressed to increase the effective sampling rate by 2.07×, modulated with the RF signal, and fully compressed yielding optical integration of the PRBS-RF inner product prior to photodetection. This yields a 266× reduction in the required electronic sampling rate. We introduce a joint-sparsity-based matching-pursuit reconstruction via bagging to achieve accurate recovery of tones at arbitrary frequencies relative to the reconstruction basis.