Documentation

Averaging.ReconstructionSpectral

Contraction off two eigenvectors of a real symmetric matrix #

The linear-algebra inputs of Lemma C.1 of Becchetti et al. (arXiv:1511.03927), on top of the plain-vector eigenbasis API of Dynamics/Spectral.lean (orthonormality, Parseval, the spectral bound ‖Aᵗ y‖² ≤ λ²ᵗ ‖y‖² for vectors y without components along eigenvectors whose eigenvalue exceeds λ in absolute value): at most two eigenvalues exceed a bound on the rest of the sorted spectrum, Bessel's inequality for the projection on the span of two orthogonal vectors of equal norm, and the resulting contraction off two eigenvectors.

theorem Averaging.card_filter_lt_abs_eigenvalues_le_two {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) {lam : ℝ} (hlam : ∀ (i : Fin (Fintype.card V)), 2 ≤ ↑i → |hA.eigenvalues₀ i| ≤ lam) :
{j : V | lam < |hA.eigenvalues j|}.card ≤ 2

At most two eigenvalues exceed in absolute value a bound on all but the two largest ones of the decreasingly sorted spectrum eigenvalues₀.

Projection on the span of two orthogonal vectors of equal norm #

theorem Averaging.residual_dotProduct_left {V : Type u_1} [Fintype V] {u₁ u₂ : V → ℝ} {m : ℝ} (hm : m ≠ 0) (h₁ : u₁ ⬝ᵥ u₁ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) (w : V → ℝ) :
(w - (w ⬝ᵥ u₁ / m) • u₁ - (w ⬝ᵥ u₂ / m) • u₂) ⬝ᵥ u₁ = 0
theorem Averaging.residual_dotProduct_right {V : Type u_1} [Fintype V] {u₁ u₂ : V → ℝ} {m : ℝ} (hm : m ≠ 0) (h₂ : u₂ ⬝ᵥ u₂ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) (w : V → ℝ) :
(w - (w ⬝ᵥ u₁ / m) • u₁ - (w ⬝ᵥ u₂ / m) • u₂) ⬝ᵥ u₂ = 0
theorem Averaging.residual_dotProduct_self {V : Type u_1} [Fintype V] {u₁ u₂ : V → ℝ} {m : ℝ} (hm : m ≠ 0) (h₁ : u₁ ⬝ᵥ u₁ = m) (h₂ : u₂ ⬝ᵥ u₂ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) (w : V → ℝ) :
(w - (w ⬝ᵥ u₁ / m) • u₁ - (w ⬝ᵥ u₂ / m) • u₂) ⬝ᵥ (w - (w ⬝ᵥ u₁ / m) • u₁ - (w ⬝ᵥ u₂ / m) • u₂) = w ⬝ᵥ w - ((w ⬝ᵥ u₁) ^ 2 + (w ⬝ᵥ u₂) ^ 2) / m
theorem Averaging.sq_add_sq_le {V : Type u_1} [Fintype V] {u₁ u₂ : V → ℝ} {m : ℝ} (hm : 0 < m) (h₁ : u₁ ⬝ᵥ u₁ = m) (h₂ : u₂ ⬝ᵥ u₂ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) {w : V → ℝ} (hw : w ⬝ᵥ w = 1) :
(w ⬝ᵥ u₁) ^ 2 + (w ⬝ᵥ u₂) ^ 2 ≤ m

A unit vector has squared projection on span {u₁, u₂} at most 1 (Bessel).

theorem Averaging.dotProduct_eq_zero_of_sq_add_sq_eq {V : Type u_1} [Fintype V] {u₁ u₂ : V → ℝ} {m : ℝ} (hm : 0 < m) (h₁ : u₁ ⬝ᵥ u₁ = m) (h₂ : u₂ ⬝ᵥ u₂ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) {w : V → ℝ} (hw : w ⬝ᵥ w = 1) (heq : (w ⬝ᵥ u₁) ^ 2 + (w ⬝ᵥ u₂) ^ 2 = m) {y : V → ℝ} (hy₁ : u₁ ⬝ᵥ y = 0) (hy₂ : u₂ ⬝ᵥ y = 0) :
w ⬝ᵥ y = 0

Equality in Bessel's inequality: then w ∈ span {u₁, u₂}, so w ⊥ y whenever y ⊥ u₁, u₂.

theorem Averaging.pow_mulVec_dotProduct_self_le_of_orthogonal {V : Type u_1} [Fintype V] [DecidableEq V] {A : Matrix V V ℝ} (hA : A.IsHermitian) {lam c₁ c₂ m : ℝ} {u₁ u₂ : V → ℝ} (hK : {j : V | lam < |hA.eigenvalues j|}.card ≤ 2) (hc₁ : lam < |c₁|) (hc₂ : lam < |c₂|) (hu₁ : A.mulVec u₁ = c₁ • u₁) (hu₂ : A.mulVec u₂ = c₂ • u₂) (hm : 0 < m) (h₁ : u₁ ⬝ᵥ u₁ = m) (h₂ : u₂ ⬝ᵥ u₂ = m) (h₁₂ : u₁ ⬝ᵥ u₂ = 0) {y : V → ℝ} (hy₁ : u₁ ⬝ᵥ y = 0) (hy₂ : u₂ ⬝ᵥ y = 0) (t : ℕ) :
(A ^ t).mulVec y ⬝ᵥ (A ^ t).mulVec y ≤ (lam ^ t) ^ 2 * y ⬝ᵥ y

Contraction off two eigenvectors. Let u₁, u₂ be orthogonal eigenvectors of A of equal squared norm m > 0, with eigenvalues c₁, c₂ exceeding λ in absolute value, and assume that at most two eigenvalues of A exceed λ in absolute value. Then ‖Aᵗ y‖² ≤ λ²ᵗ ‖y‖² for every y orthogonal to u₁ and u₂.