noncomputable def Chapter3.weakLqNorm {M : ℕ} (q : ℝ) (θ : Fin M → ℝ) : ℝ

Weak ℓ_q quasi-norm: |θ|{wℓ_q} = sup{t>0} t · #{i : |θ_i| ≥ t}^{1/q}.

theorem Chapter3.problem_3_3_maurey_weak_lq {n M : ℕ} (hn : 0 < n) (hM : 0 < M) (Φ : Matrix (Fin n) (Fin M) ℝ) (f : Fin n → ℝ) (q : ℝ) (hq0 : 0 < q) (hq2 : q < 2) (D : ℝ) (hD : 0 < D) (k : ℕ) (hk1 : 1 ≤ k) (hkM : k ≤ M) (hNorm : ∀ (j : Fin M), ∑ i : Fin n, Φ i j ^ 2 ≤ ↑n) : ∃ (Cq : ℝ), 0 < Cq ∧ ⨅ (θ : Fin M → ℝ), ⨅ (_ : support_size θ ≤ 2 * k), MSE (Φ.mulVec θ) f ≤ (⨅ (θ : Fin M → ℝ), ⨅ (_ : weakLqNorm q θ ≤ 1), MSE (Φ.mulVec θ) f) + Cq * D ^ 2 * (↑k ^ (1 - 1 / q) - ↑M ^ (1 - 1 / q)) ^ 2 / ↑k

Problem 3.3 — Maurey's argument generalized to weak ℓ_q norms.

Rigollet, High-Dimensional Statistics, Problem 3.3 (line 2576).

Let {φ₁, …, φ_M} be a dictionary normalised so that max_j ‖φⱼ‖₂ ≤ √n, and let 0 < q < 2. Show that for any integer k with 1 ≤ k ≤ M,

min_{|θ|₀ ≤ 2k} MSE(φ_θ) ≤ min_{|θ|_{wℓ_q} ≤ 1} MSE(φ_θ) + C_q D² (k^{1/q̄} − M^{1/q̄})² / k

where |θ|{wℓ_q} = sup{t>0} t · #{i : |θᵢ| ≥ t}^{1/q} is the weak ℓ_q quasi-norm and q̄ denotes the conjugate exponent (1/q + 1/q̄ = 1).

This extends the basic Maurey sparsification argument (Proposition 3.5) from ℓ₁ balls to weak-ℓ_q balls, yielding rates that adapt to finer notions of approximate sparsity.