2021/03/09 by Mendelson, Shahar
#FOS: Mathematics #Functional Analysis (math.FA) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2103.05237
The matrix A:ℝn → ℝm 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 ⊂ ℝn (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-2exp(-c(ℓ_*(T)/dT)2), supt ∈ T | ‖Aεt‖22-‖t‖22 | ≤ C(ΛdT δℓ_*(T)+(δℓ_*(T))2 ), where Λ=max\1,δ2log(nδ2)\. This estimate is optimal for 0