Tensor product of random orthogolal matrices

In this short note, we introduce a class of orthogonal matrices of order n for which the matrix by vector product can be be computed in O(nlogn) instead o fO(n2). The matricesin this class form a proper Lie subgroup of the set of the orthogonal matrices random generatedfollowing the Haar’s measure distribution. Given a vector that has the absolute values of its entriespresenting large variations of magnitude, the product of a matrix in the subgroup by this vector willproduce a new vector where the magnitude of the absolute values of the entries does not vary by avery large amount.