← ALL STATEMENTS
AcceptedProposition · Statement with omitted proof

Exact Frobenius second moment of a Gaussian pseudoinverse

The expected squared Frobenius norm has a closed form determined by the rectangular dimensions.

Halko, Martinsson & Tropp ↗
Source label: prop:inv-gauss-frob-expect

Formal statement. The assumptions and conclusion are explicit; the theorem proof is omitted (sorry).

01 / MATHEMATICAL STATEMENT

Meaning & conditions

Mathematical summary

The expected squared Frobenius norm has a closed form determined by the rectangular dimensions.

E∥G†∥F2=mn−m−1\mathbb E\|G^\dagger\|_F^2=\frac{m}{n-m-1}

Assumptions & context

  • G is standard Gaussian m × n with n−m ≥ 2.

Source

Halko, Martinsson & Tropp. Finding structure with randomness.

Source label: prop:inv-gauss-frob-expect

02 / LEAN REPRESENTATION

Formal statement

Statement with omitted proof. Expand the complete file below to read imports, local definitions and surrounding context.

theorem inv_gauss_frob_expect
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    (m n : ℕ) (hnm : 2 ≤ n - m)
    (G : Ω → Matrix (Fin m) (Fin n) ℝ)
    (hG : RNLAPhaseB.StandardGaussianTestMatrix P G)
    (Gpinv : Ω → Matrix (Fin n) (Fin m) ℝ)
    (hGpinv : ∀ ω, IsMoorePenroseInverse (G ω) (Gpinv ω)) :
    ∫ ω, frobeniusNormSq (Gpinv ω) ∂P = (m : ℝ) / ((n : ℝ) - (m : ℝ) - 1) := by
  sorry
Complete Lean file and local definitions
import RNLAPhaseB.B3Base
import RNLAPhaseB.Complexity

open MeasureTheory
open scoped Matrix
open scoped Matrix.Norms.L2Operator
open scoped BigOperators
open scoped ENNReal

namespace RNLAPhaseB.HMT2011.InvGaussFrobExpect

/-- `X` is the Moore–Penrose pseudoinverse of the real matrix `A`. The source writes this
as `A^†`. The four Penrose conditions determine it uniquely: `A X A = A`, `X A X = X`,
and `A X` and `X A` are symmetric. Over `ℝ`, self-adjoint means `Mᵀ = M`. -/
def IsMoorePenroseInverse {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
    (X : Matrix (Fin n) (Fin m) ℝ) : Prop :=
  A * X * A = A ∧ X * A * X = X ∧ (A * X)ᵀ = A * X ∧ (X * A)ᵀ = X * A

/-- The squared Frobenius norm `‖M‖_F^2`, which is the sum of the squared entries. -/
noncomputable def frobeniusNormSq {p q : ℕ} (M : Matrix (Fin p) (Fin q) ℝ) : ℝ :=
  ∑ i, ∑ j, (M i j) ^ 2

/-- HMT 2011, Proposition (prop:inv-gauss-frob-expect).

Let `G` be an `m × n` standard Gaussian matrix with `n - m ≥ 2`. Then
`𝔼 ‖G^†‖_F^2 = m / (n - m - 1)`.

The pseudoinverse `G^†` is represented by the sample-wise matrix `Gpinv ω`. That matrix
satisfies the Penrose conditions for `G ω` at every sample point. Because the
Moore–Penrose inverse is unique, this pins it down exactly. -/
theorem inv_gauss_frob_expect
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    (m n : ℕ) (hnm : 2 ≤ n - m)
    (G : Ω → Matrix (Fin m) (Fin n) ℝ)
    (hG : RNLAPhaseB.StandardGaussianTestMatrix P G)
    (Gpinv : Ω → Matrix (Fin n) (Fin m) ℝ)
    (hGpinv : ∀ ω, IsMoorePenroseInverse (G ω) (Gpinv ω)) :
    ∫ ω, frobeniusNormSq (Gpinv ω) ∂P = (m : ℝ) / ((n : ℝ) - (m : ℝ) - 1) := by
  sorry

end RNLAPhaseB.HMT2011.InvGaussFrobExpect

How to read the formalization

  • The denominator is the real quantity n−m−1. The dimensional gap prevents it from vanishing.
← Back to all statements