Fast dimension reduction through random permutation

This paper studies permutation-based dimension reduction, which can be implemented by first scrambling the input data, then applying the FFT, DCT or Walsh-Hadamard transform and finally using either uniformly random sampling or sparse random projection. By exploiting concentration inequalities of random permutation, we show that this subclass of operators can offer (near) optimal theoretical guarantee. Besides, as random permutation of N elements can be implemented in O(N) time, the proposed algorithm has very low complexity. Some numerical examples are presented to demonstrate the validity of our theoretical development and their promising applications in image processing.