← ALL STATEMENTS
AcceptedProposition · Statement with omitted proof

Rangefinder error as a Schur complement

The Gram matrix of a projection residual equals a generalized Schur complement.

Martinsson & Tropp ↗
Source label: prop:rrf-schur

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

01 / MATHEMATICAL STATEMENT

Meaning & conditions

Mathematical summary

The Gram matrix of a projection residual equals a generalized Schur complement.

E=(I−PBX)B,E∗E=(B∗B)/X⪰0E=(I-P_{BX})B,\qquad E^*E=(B^*B)/X\succeq0

Assumptions & context

  • Y = BX for any compatible test matrix X, and the inverse in the complement is the Moore–Penrose inverse of X*B*BX.

Source

Martinsson & Tropp. Randomized numerical linear algebra: Foundations and algorithms.

Source label: prop:rrf-schur

02 / LEAN REPRESENTATION

Formal statement

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

theorem prop_rrf_schur {𝕜 : Type*} [RCLike 𝕜] {m n ℓ : ℕ}
    (B : Matrix (Fin m) (Fin n) 𝕜) (X : Matrix (Fin n) (Fin ℓ) 𝕜)
    (W : Matrix (Fin ℓ) (Fin ℓ) 𝕜)
    (hW : IsMoorePenroseInverse (Xᴴ * (Bᴴ * B) * X) W) :
    (approxError B X)ᴴ * approxError B X = schurComplement (Bᴴ * B) X W ∧
      ((approxError B X)ᴴ * approxError B X).PosSemidef := 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
open scoped ComplexOrder

namespace RNLAPhaseB.MT2020.PropRrfSchur

/-- `W` is the Moore–Penrose pseudoinverse `M^†` of the matrix `M`: the four
Penrose conditions. The pseudoinverse is unique, so a binder constrained by
these equations denotes the source's `M^†`. -/
structure IsMoorePenroseInverse {𝕜 : Type*} [RCLike 𝕜] {p q : Type*}
    [Fintype p] [Fintype q] (M : Matrix p q 𝕜) (W : Matrix q p 𝕜) : Prop where
  mul_mul_self : M * W * M = M
  self_mul_mul : W * M * W = W
  mul_selfAdjoint : (M * W)ᴴ = M * W
  selfAdjoint_mul : (W * M)ᴴ = W * M

/-- The Nyström approximation (eqn:nys-def)
`A⟨X⟩ := (A X) (X^* A X)^† (A X)^*`, where `W` is the pseudoinverse
`(X^* A X)^†` (constrained separately by `IsMoorePenroseInverse`). -/
def nystromApprox {𝕜 : Type*} [RCLike 𝕜] {n k : ℕ}
    (A : Matrix (Fin n) (Fin n) 𝕜) (X : Matrix (Fin n) (Fin k) 𝕜)
    (W : Matrix (Fin k) (Fin k) 𝕜) : Matrix (Fin n) (Fin n) 𝕜 :=
  (A * X) * W * (A * X)ᴴ

/-- The Schur complement (eqn:schur-complement) `A / X := A - A⟨X⟩`, with `W`
standing for `(X^* A X)^†`. -/
def schurComplement {𝕜 : Type*} [RCLike 𝕜] {n k : ℕ}
    (A : Matrix (Fin n) (Fin n) 𝕜) (X : Matrix (Fin n) (Fin k) 𝕜)
    (W : Matrix (Fin k) (Fin k) 𝕜) : Matrix (Fin n) (Fin n) 𝕜 :=
  A - nystromApprox A X W

/-- The approximation error `E(B, X) := (I - P_Y) B` with `Y = B X` and `P_Y`
the orthogonal projector onto the range of `Y`. -/
noncomputable def approxError {𝕜 : Type*} [RCLike 𝕜] {m n ℓ : ℕ}
    (B : Matrix (Fin m) (Fin n) 𝕜) (X : Matrix (Fin n) (Fin ℓ) 𝕜) :
    Matrix (Fin m) (Fin n) 𝕜 :=
  (1 - orthogonalProjector (B * X)) * B

/-- mt2020 Proposition (prop:rrf-schur). For an arbitrary test matrix
`X ∈ F^{n×ℓ}` (F = ℝ or ℂ, realized as `RCLike 𝕜`), with `Y = B X` and
`E = (I - P_Y) B`, the squared error `|E|^2 := E^* E` equals the Schur
complement `(B^* B) / X`, i.e. `B^*B - (B^*B X)(X^* B^*B X)^† (B^*B X)^*`;
and `|E|^2` is a psd matrix. The pseudoinverse is represented by any matrix
satisfying the Penrose conditions (it is unique). -/
theorem prop_rrf_schur {𝕜 : Type*} [RCLike 𝕜] {m n ℓ : ℕ}
    (B : Matrix (Fin m) (Fin n) 𝕜) (X : Matrix (Fin n) (Fin ℓ) 𝕜)
    (W : Matrix (Fin ℓ) (Fin ℓ) 𝕜)
    (hW : IsMoorePenroseInverse (Xᴴ * (Bᴴ * B) * X) W) :
    (approxError B X)ᴴ * approxError B X = schurComplement (Bᴴ * B) X W ∧
      ((approxError B X)ᴴ * approxError B X).PosSemidef := by
  sorry

end RNLAPhaseB.MT2020.PropRrfSchur

How to read the formalization

  • The conclusion explicitly states that E*E is positive semidefinite. The slash notation denotes the generalized Schur complement.
← Back to all statements