Subsampled Randomized Hadamard Transform Subspace Embedding

Subsampled Randomized Hadamard Transform Subspace Embedding is a structured fast oblivious dimension-reduction operator Phi = sqrt(n / l) R H D in R^{l x n} (for n = 2^q) analyzed via matrix Chernoff bounds by Tropp (2011) that embeds any fixed k-dimensional subspace of R^n spanned by an n x k orthonormal basis matrix V (V^T V = I_k) into R^l in O(n k log l) arithmetic operations instead of the O(n l k) cost of dense Gaussian projections. Here D in R^{n x n} is a diagonal Rademacher sign matrix with i.i.d. +-1 diagonal entries, H in R^{n x n} is the normalized Walsh-Hadamard matrix with entries +-1/sqrt(n), and R in R^{l x n} uniformly samples l rows without replacement. The proof decouples into two stages: (1) Lemma 3.3 uses availability of convex Lipschitz concentration for Rademacher series (Lemma 2.1) to prove that W = H D V equalizes row norms (leverage scores) across all n rows so that max_{j=1..n} ||e_j^T (H D V)||_2 <= sqrt(k / n) + sqrt(8 log(beta n) / n) with probability at least 1 - 1/beta, and (2) Lemma 3.4 applies the matrix Chernoff bound for sampling without replacement (Lemma 2.2) to the rank-1 decomposition X = sum_{j in T} x_j x_j^T of R W to guarantee that l = Omega((k + log n) log k) sampled rows preserve all k singular values of Phi V within [sqrt(1 - delta), sqrt(1 + delta)] (Theorem 3.1).