Problem 1.5: ℓ_q norms of sub-Gaussian random vectors

Informal statement (Rigollet, Problem 1.5): Let X = (X₁, …, Xₙ) be a vector with independent entries, each Xᵢ ~ subG(σ²) with E(Xᵢ) = 0.

Parts

(a) Deterministic norm comparison: For any q ≥ 2 and any x ∈ ℝⁿ, ‖x‖₂ ≤ ‖x‖_q · n^{1/2 − 1/q}. This is tight (equality at x = (1,…,1)) and follows from the power mean inequality (or Jensen's inequality applied to t ↦ t^{q/2}).

(b) Expected ℓ_q norm bound: For any q > 1, E[‖X‖_q] ≤ 4σ · n^{1/q} · √q. Key idea: Use the sub-Gaussian moment bound E[|Xᵢ|^q] ≤ (2σ²q)^{q/2} combined with Jensen's inequality (or direct computation).

(c) Expected max bound: Recover E[max_{1≤i≤n} |Xᵢ|] ≤ 4eσ√(log n). Key idea: Take q = log n in part (b). Then n^{1/q} = n^{1/log n} = e and √q = √(log n), giving E[‖X‖_q] ≤ 4eσ√(log n). Since ‖X‖q → ‖X‖∞ as q → ∞, for q = log n with n large enough, the ℓ_q norm approximates the max well.

References

• Rigollet, High-Dimensional Statistics, Problem 1.5.

noncomputable def lqNorm (n : ℕ) (q : ℝ) (x : Fin n → ℝ) : ℝ

The ℓ_q norm of a vector x : Fin n → ℝ, defined as (∑ i, |x i|^q)^(1/q). This is the standard ℓ_q norm when q ≥ 1.

Part (a): Deterministic norm comparison

theorem problem_1_5a_norm_comparison (n : ℕ) (q : ℝ) (hq : 2 ≤ q) (x : Fin n → ℝ) : lqNorm n 2 x ≤ lqNorm n q x * ↑n ^ (1 / 2 - 1 / q)

Problem 1.5 (a) (Norm comparison inequality). For any q ≥ 2 and any vector x ∈ ℝⁿ:

‖x‖₂ ≤ ‖x‖_q · n^{1/2 - 1/q}

This is a special case of the general ℓ_p–ℓ_q norm comparison: for 1 ≤ p ≤ q, ‖x‖_p ≤ ‖x‖_q · n^{1/p - 1/q}. Here we take p = 2. The inequality is tight, achieved by x = (1, 1, ..., 1).

Part (b): Expected ℓ_q norm bound

theorem problem_1_5b_lq_norm_bound {n : ℕ} (hn : 0 < n) {Ω : Type u_1} {x✝ : MeasurableSpace Ω} {μ : MeasureTheory.Measure Ω} (x✝¹ : MeasureTheory.IsProbabilityMeasure μ) {X : Fin n → Ω → ℝ} {σ : ℝ} (hσ : 0 ≤ σ) (hXmeas : ∀ (i : Fin n), Measurable (X i)) (hXsubG : ∀ (i : Fin n), IsSubGaussian (X i) (σ ^ 2) μ) (hXindep : ProbabilityTheory.iIndepFun X μ) (q : ℝ) (hq : 1 < q) : ∫ (ω : Ω), lqNorm n q fun (i : Fin n) => X i ω ∂μ ≤ 4 * σ * ↑n ^ (1 / q) * √q

Problem 1.5 (b) (ℓ_q norm bound for sub-Gaussian vectors). Let X = (X₁,...,Xₙ) be a vector with independent entries, each Xᵢ ~ subG(σ²) with E(Xᵢ) = 0. For any q > 1:

E[‖X‖_q] ≤ 4σ · n^{1/q} · √q

The proof uses the bound E[|Xᵢ|^q] ≤ (2σ²q)^{q/2} for sub-Gaussian random variables, combined with Jensen's inequality.

Part (c): Expected maximum bound

theorem problem_1_5c_max_bound {n : ℕ} (hn : 2 ≤ n) {Ω : Type u_1} {x✝ : MeasurableSpace Ω} {μ : MeasureTheory.Measure Ω} (x✝¹ : MeasureTheory.IsProbabilityMeasure μ) {X : Fin n → Ω → ℝ} {σ : ℝ} (hσ : 0 ≤ σ) (hXmeas : ∀ (i : Fin n), Measurable (X i)) (hXsubG : ∀ (i : Fin n), IsSubGaussian (X i) (σ ^ 2) μ) (hXindep : ProbabilityTheory.iIndepFun X μ) : ∫ (ω : Ω), Finset.univ.sup' ⋯ fun (i : Fin n) => |X i ω| ∂μ ≤ 4 * Real.exp 1 * σ * √(Real.log ↑n)

Problem 1.5 (c) (Expected maximum of sub-Gaussian entries). Under the same conditions as part (b), for n ≥ 2:

E[max_{1≤i≤n} |Xᵢ|] ≤ 4eσ√(log n)

This follows from part (b) by choosing q = log n (which satisfies q > 1 when n ≥ 3) and using the bound n^{1/q} = n^{1/log n} = e.

The maximum is expressed using Finset.sup' over Finset.univ (which is nonempty since n ≥ 2).