Rademacher projections work too

ProofAdvanced⏱ 1 hourHigh-Dim Probabilityjlrademachersub-gaussiandatabase-friendly

Problem

Let $A\in\R^{k\times D}$ have i.i.d. entries $A_{rj} = \eps_{rj}/\sqrt k$ with $\eps_{rj}$ Rademacher signs. Prove that for a fixed unit $x$ ,

\P\big(\big|\|Ax\|_2^2-1\big|\ge\eps\big)\le2e^{-ck\eps^2}

for an absolute constant $c$ . Where does the proof differ from the Gaussian case, and what is gained in practice?

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 3 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Johnson–Lindenstrauss dimension arithmetic	High-Dim Probability	Numerical	Beginner	15 min
The psi-2 norm of a Rademacher sign	High-Dim Probability	Numerical	Beginner	15 min
From distance preservation to inner-product preservation	High-Dim Probability	Proof	Intermediate	30 min
Implement random projection and measure the distortion run	High-Dim Probability	Coding	Intermediate	1 hour
Moments from tail bounds via the layer-cake formula	Probability	Proof	Intermediate	30 min