Qubit noise spectroscopy is an important tool for the experimental investigation of open quantum systems. However, conventional techniques for implementing noise spectroscopy are time-consuming, because they require multiple measurements of the noise spectral density at different frequencies. Here we describe an alternative method for quickly characterizing the spectral density. Our method utilizes random pulse sequences, with carefully-controlled correlations among the pulses, to measure arbitrary linear functionals of the noise spectrum. Such measurements allow us to estimate $k$'th-order moments of the noise spectrum, as well as to reconstruct sparse noise spectra via compressed sensing. Our simulations of the performance of the random pulse sequences on a realistic physical system, self-assembled quantum dots, reveal a speedup of an order of magnitude in extracting the noise spectrum compared to conventional dynamical decoupling approaches.