  Traditional compressed sensing considers sampling a 1D signal. For a
multidimensional signal, if reshaped into a vector, the required size of the
sensing matrix becomes dramatically large, which increases the storage and
computational complexity significantly. To solve this problem, we propose to
reshape the multidimensional signal into a 2D signal and sample the 2D signal
using compressed sensing column by column with the same sensing matrix. It is
referred to as parallel compressed sensing, and it has much lower storage and
computational complexity. For a given reconstruction performance of parallel
compressed sensing, if a so-called acceptable permutation is applied to the 2D
signal, we show that the corresponding sensing matrix has a smaller required
order of restricted isometry property condition, and thus, storage and
computation requirements are further lowered. A zigzag-scan-based permutation,
which is shown to be particularly useful for signals satisfying a layer model,
is introduced and investigated. As an application of the parallel compressed
sensing with the zigzag-scan-based permutation, a video compression scheme is
presented. It is shown that the zigzag-scan-based permutation increases the
peak signal-to-noise ratio of reconstructed images and video frames.
