Camera-based experimental modal analysis (EMA) measures the dynamic properties of structures in service to various phases of a product or process’s lifetime, such as structural design and damage identification. Compared with accelerometers, cameras have some advantages, among which contactless sensing (no added mass/damping) and full field measurements with high spatial resolution are the most relevant to EMA, but camera measurements have the drawbacks of low frame rate and low Signal-to-Noise Ratio (SNR). A previously proposed random sampling method is able to measure frequencies above the Nyquist limit of cameras, which is half of the frame rate. Assuming that the modal responses are damped sine wave bases, the measured signals are reconstructed via a nonlinear optimization with these bases. To improve the SNR, a multi-sine excitation containing the resonance frequencies was previously proposed to measure vibration modes, especially those modes higher than the Nyquist frequency. The resonance frequencies are measured by accelerometers in a pre-test. However, reconstructing the high frequency signal from the randomly sampled camera measurements takes a long time due to nonlinear optimization with damped sine wave bases. In this work, a linear fitting with the Fourier bases is adopted to replace the nonlinear optimization. When processing the same spatially dense camera measurements, the linear fitting requires 0.5 s, whereas the nonlinear optimization takes 3 h with the same hardware. From a randomly sampled image sequence with an equivalent frame rate below 50 fps (corresponding to a Nyquist frequency below 25 Hz), the linear method is able to extract four modes up to 250 Hz (i.e., ten times higher than the Nyquist frequency), whose modal complexity is comparable to that of the modes extracted by the nonlinear method.