← ALL STATEMENTS
AcceptedCorollary · Statement with omitted proof

Expected spectral error after power iteration

Power iteration sharpens the expected spectral error of a Gaussian rangefinder.

Halko, Martinsson & Tropp ↗
Source label: cor:power-method-spec-gauss

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

01 / MATHEMATICAL STATEMENT

Meaning & conditions

Mathematical summary

Power iteration sharpens the expected spectral error of a Gaussian rangefinder.

E∥(I−PZ)A∥≤[(1+kp−1)σk+12q+1+ek+pp(∑j>kσj2(2q+1))1/2]1/(2q+1)\mathbb E\|(I-P_Z)A\|\le\left[\left(1+\sqrt{\frac{k}{p-1}}\right)\sigma_{k+1}^{2q+1}+\frac{e\sqrt{k+p}}p\left(\sum_{j>k}\sigma_j^{2(2q+1)}\right)^{1/2}\right]^{1/(2q+1)}

Assumptions & context

  • A is real, k ≥ 2, p ≥ 2, k+p ≤ min(m,n), q is a nonnegative integer, and Z = (AAᵀ)^q AΩ with standard Gaussian Ω.

Source

Halko, Martinsson & Tropp. Finding structure with randomness.

Source label: cor:power-method-spec-gauss

02 / LEAN REPRESENTATION

Formal statement

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

theorem power_method_spec_gauss
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (k p q : ℕ)
    (hk : 2 ≤ k) (hp : 2 ≤ p) (hkp : k + p ≤ min m n)
    (G : Ω → Matrix (Fin n) (Fin (k + p)) ℝ)
    (hG : StandardGaussianTestMatrix P G) :
    ∫ ω, ‖(1 - orthogonalProjector (sampleMatrix A q (G ω))) * A‖ ∂P ≤
      ((1 + Real.sqrt ((k : ℝ) / ((p : ℝ) - 1))) * singularValue A (k + 1) ^ (2 * q + 1)
        + Real.exp 1 * Real.sqrt ((k : ℝ) + (p : ℝ)) / (p : ℝ) *
          Real.sqrt (∑ j ∈ Finset.Ioc k (min m n), singularValue A j ^ (2 * (2 * q + 1))))
        ^ ((1 : ℝ) / (2 * (q : ℝ) + 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.PowerMethodSpecGauss

/-- The `j`th singular value (1-based) of a real `m × n` matrix, `σ_j(A)`.
It is given by the standard rank characterization (Schmidt–Mirsky/Eckart–Young
in the spectral norm): `σ_j(A) = inf { ‖A - X‖ : rank X < j }`, where `‖·‖` is
the ℓ₂ operator norm. This equals the `j`th largest singular value for
`1 ≤ j ≤ min m n` and is `0` (zero padding) for `j > min m n`. -/
noncomputable def singularValue {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (j : ℕ) : ℝ :=
  sInf {r : ℝ | ∃ X : Matrix (Fin m) (Fin n) ℝ, X.rank < j ∧ r = ‖A - X‖}

/-- The source's matrix `B = (A A^*)^q A` (real case, so `A^* = Aᵀ`). -/
noncomputable def powerMatrix {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (q : ℕ) :
    Matrix (Fin m) (Fin n) ℝ :=
  (A * Aᵀ) ^ q * A

/-- The source's sample matrix `Z = B Ω` with `B = (A A^*)^q A`. -/
noncomputable def sampleMatrix {m n ℓ : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (q : ℕ)
    (Omega : Matrix (Fin n) (Fin ℓ) ℝ) : Matrix (Fin m) (Fin ℓ) ℝ :=
  powerMatrix A q * Omega

/-- HMT2011, Corollary cor:power-method-spec-gauss. Hypotheses of
Theorem thm:avg-frob-error-gauss: `A` real `m × n`, target rank `k ≥ 2`,
oversampling `p ≥ 2`, `k + p ≤ min{m,n}`, `Ω` an `n × (k+p)` standard Gaussian
matrix. With `B = (AA^*)^q A` (`q` a nonnegative integer) and `Z = BΩ`,
`E ‖(I - P_Z) A‖ ≤ [(1 + √(k/(p-1))) σ_{k+1}^{2q+1}
   + (e √(k+p)/p) (∑_{j>k} σ_j^{2(2q+1)})^{1/2}]^{1/(2q+1)}`,
with `‖·‖` the spectral (ℓ₂ operator) norm and `σ_j` the singular values of `A`. -/
theorem power_method_spec_gauss
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (k p q : ℕ)
    (hk : 2 ≤ k) (hp : 2 ≤ p) (hkp : k + p ≤ min m n)
    (G : Ω → Matrix (Fin n) (Fin (k + p)) ℝ)
    (hG : StandardGaussianTestMatrix P G) :
    ∫ ω, ‖(1 - orthogonalProjector (sampleMatrix A q (G ω))) * A‖ ∂P ≤
      ((1 + Real.sqrt ((k : ℝ) / ((p : ℝ) - 1))) * singularValue A (k + 1) ^ (2 * q + 1)
        + Real.exp 1 * Real.sqrt ((k : ℝ) + (p : ℝ)) / (p : ℝ) *
          Real.sqrt (∑ j ∈ Finset.Ioc k (min m n), singularValue A j ^ (2 * (2 * q + 1))))
        ^ ((1 : ℝ) / (2 * (q : ℝ) + 1)) := by
  sorry

end RNLAPhaseB.HMT2011.PowerMethodSpecGauss

How to read the formalization

  • The outer exponent is 1/(2q+1); the singular-value tail is raised to the matching power before it is summed.
← Back to all statements