Column randomization and almost-isometric embeddings

Abstract

The matrix A : Rn → Rm is (δ, k)-regular if for any k-sparse vector x, | ∥Ax∥22 - ∥x∥22 | ≤ δ √ k∥x∥22 . We show that if A is (δ, k)-regular for 1 ≤ k ≤ 1/δ2, then by multiplying the columns of A by independent random signs, the resulting random ensemble Aϵ acts on an arbitrary subset T ⊂ Rn (almost) as if it were Gaussian, and with the optimal probability estimate: if ℓ*(T) is the Gaussian mean-width of T and dT = supt∈T ∥t∥2, then with probability at least 1 - 2 exp(-c(ℓ*(T)/dT )2), sup t∈T | ∥Aϵt∥22 - ∥t∥22 | ≤ C ( ΛdTδℓ*(T) + (δℓ*(T))2 ) , where Λ = max{1, δ2 log(nδ2)}. This estimate is optimal for 0 < δ ≤ 1/ √ log n. Show more