Frobenius norm setup #
Algebraic helpers for singular value thresholding #
Pointwise SVT error bound. For each singular value, the thresholding error ((thresholded σ̂) - σ)² is at most 9τ² if σ ≠ 0, and 0 if σ = 0.
The four cases:
- S ∩ supp(Θ*): |σ̂| > 2τ, σ ≠ 0 → (σ̂ - σ)² ≤ τ² ≤ 9τ²
- S ∩ supp^c: |σ̂| > 2τ, σ = 0 → impossible (|σ̂| = |σ̂ - 0| ≤ τ < 2τ)
- S^c ∩ supp: |σ̂| ≤ 2τ, σ ≠ 0 → σ² ≤ (3τ)² = 9τ²
- S^c ∩ supp^c: |σ̂| ≤ 2τ, σ = 0 → (0 - 0)² = 0
Core algebraic bound #
Core algebraic bound for SVT (constant 9). Given singular value sequences σ (true) and σ̂ (observed) with pointwise perturbation |σ̂_j - σ_j| ≤ τ, the sum of squared SVT errors satisfies:
Σⱼ ((thresholded σ̂_j) - σ_j)² ≤ 9 · #{j : σ_j ≠ 0} · τ²
The constant 9 = 3² comes from the S^c ∩ supp bound where |σ_j| ≤ 3τ.
Theorem 4.3: SVT Frobenius error bound #
Theorem 4.3 (algebraic form, constant 144). Given singular value sequences σ (true, from Θ*) and σ̂ (observed, from y = Θ* + F) with Weyl's perturbation bound |σ̂_j - σ_j| ≤ τ, the SVT estimator with threshold 2τ satisfies:
Σⱼ ((thresholded σ̂_j) - σ_j)² ≤ 144 · rank(Θ*) · τ²
where rank(Θ*) ≥ #{j : σ_j ≠ 0}.
This is the bound stated in Theorem 4.3 of Rigollet. The constant 144 dominates the tighter constant 9 obtained from the direct pointwise analysis; in the book, the 144 arises from the matrix-level decomposition via the oracle Θ̄ and the inequality ‖A‖_F² ≤ rank(A) · ‖A‖_op².
Theorem 4.3 (matrix-level statement). Consider the sub-Gaussian matrix model (4.2) with ORT assumption. Given:
- SVD decompositions S_star of Θ* and S_obs of y = Θ* + F
- Weyl's perturbation bound: |σ̂_j - σ_j| ≤ τ for all j (which follows from ‖F‖_op ≤ τ, guaranteed by Lemma 4.2 with probability 1-δ)
The SVT estimator Θ̂^SVT = S_obs.svtMatrix τ satisfies the singular value bound:
Σⱼ ((thresholded σ̂_j) - σ_j)² ≤ 144 · rank_bound · τ²
Under orthonormal SVD vectors, the left-hand side equals ‖Θ̂^SVT - Θ*‖_F².
The threshold τ from equation (4.3) is: τ = 4σ√(log(12)(d∨T)/n) + 2σ√(2log(1/δ)/n)
giving the rate: σ² · rank(Θ*) · (d∨T + log(1/δ))/n.
Theorem 4.3 (rate form). The SVT bound combined with the threshold choice (4.3) gives the rate:
Σⱼ ((thresholded σ̂_j) - σ_j)² ≤ 144 · rank(Θ*) · τ²
where τ² ≲ σ² · (d ∨ T + log(1/δ)) / n, yielding
‖Θ̂^SVT - Θ*‖_F² ≲ σ² · rank(Θ*) · (d ∨ T + log(1/δ)) / n
Frobenius norm identities #
Frobenius norm and singular values (standard identity).
For an orthonormal SVD A = Σⱼ σⱼ uⱼ vⱼᵀ with orthonormal {uⱼ} and {vⱼ},
and a matrix B = Σⱼ σ'ⱼ uⱼ vⱼᵀ expressed in the same orthonormal basis,
the squared Frobenius norm of the difference equals the sum of squared
differences of the coefficients:
‖A - B‖_F² = Σⱼ (σⱼ - σ'ⱼ)²
This is the standard Parseval-type identity for orthonormal expansions. In the SVT context, both Θ̂^SVT and Θ* are expressed in the SVD basis of y, so this identity connects the algebraic singular-value bound to the Frobenius norm statement in the book.
The proof requires showing that orthonormal rank-1 matrices {uⱼ vⱼᵀ} form an orthonormal system in the Frobenius inner product space. This is a standard linear algebra fact not directly available in Mathlib as a single lemma.
Corollary: SVT Frobenius norm equals singular value sum.
For an SVD decomposition with orthonormal singular vectors, the squared
Frobenius norm ‖Θ̂^SVT - Θ*‖_F² equals Σⱼ ((thresholded σ̂ⱼ) - σⱼ)².
This bridges the algebraic bound and the Frobenius norm statement.
ORT equality (Assumption ORT). Under the orthonormal design assumption
𝕏ᵀ𝕏/n = I_d, we have for any estimator Θ̂:
(1/n) ‖𝕏Θ̂ - 𝕏Θ*‖_F² = ‖Θ̂ - Θ*‖_F²
This follows because 𝕏(Θ̂ - Θ*) has Frobenius norm:
‖𝕏(Θ̂-Θ*)‖_F² = tr((Θ̂-Θ*)ᵀ 𝕏ᵀ𝕏 (Θ̂-Θ*)) = n · tr((Θ̂-Θ*)ᵀ(Θ̂-Θ*)) = n · ‖Θ̂-Θ*‖_F²
In the book, this is the identity stated in the first equality of Theorem 4.3. The ORT assumption reduces the prediction error to the estimation error.
Theorem 4.3: Frobenius norm form (book statement) #
Theorem 4.3 (Frobenius norm form). Under the sub-Gaussian matrix model (4.2) with ORT assumption, the SVT estimator satisfies:
‖Θ̂^SVT - Θ*‖_F² ≤ 144 · rank(Θ*) · τ²
This is exactly the inequality stated in Theorem 4.3 of Rigollet's book. The proof combines:
- The SVT singular value bound (
theorem_4_3_svt_bound) - The Frobenius norm identity (
svt_frobenius_eq_sv_sum)
The first equality in the book's statement,
(1/n)‖𝕏Θ̂^SVT - 𝕏Θ*‖_F² = ‖Θ̂^SVT - Θ*‖_F², follows from
ort_frobenius_equality.
Theorem 4.3 (Rigollet). Under the sub-Gaussian matrix model (4.2) with ORT
assumption 𝕏ᵀ𝕏 = n·I_d, the SVT estimator with threshold 2τ satisfies:
(1/n)‖𝕏Θ̂ˢⱽᵀ - 𝕏Θ*‖²_F = ‖Θ̂ˢⱽᵀ - Θ*‖²_F ≤ 144·rank(Θ*)·τ²
This bundles both parts of the book statement:
- The ORT equality
(1/n)‖𝕏Θ̂ - 𝕏Θ*‖²_F = ‖Θ̂ - Θ*‖²_F - The Frobenius norm bound
‖Θ̂ˢⱽᵀ - Θ*‖²_F ≤ 144·rank(Θ*)·τ²
The proof composes ort_frobenius_equality (the ORT identity) with
theorem_4_3_frobenius (the Frobenius norm bound).
Probabilistic wrapper (Theorem 4.3 full statement) #
Theorem 4.3 (full probabilistic statement). Under the sub-Gaussian matrix model (4.2), the SVT estimator with threshold τ = svtThreshold σ n d T δ satisfies
Σⱼ ((thresholded σ̂_j) - σ_j)² ≤ 144 · rank_bound · τ²
with probability at least 1 - δ. This wraps theorem_4_3 with the
concentration event from Lemma 4.2.