Eigendecomposition of a symmetric matrix: eigenvalues with orthonormal eigenvectors
DefinitionSelfSelReg_Supplement_EigDecomphermite-momentslearning-theorylinear-regressionp2o-gran-per-chapterp2o-plan-paperp2o-v1self-selection
Algorithms 6.2 and 6.3 contain the step "compute the eigenvalues and corresponding orthonormal eigenvectors ". For a real matrix , a pair with and is an eigendecomposition of if
- ;
- the rows of are orthonormal, ;
- for every .
Equivalently ; such a pair exists exactly when is symmetric. The eigenvalues are determined by , the eigenvectors only up to sign and up to a rotation inside each eigenspace of a repeated eigenvalue.
The algorithm specifications of this supplement quantify over all eigendecompositions, so the theorems about them hold for every choice the pseudocode leaves open.
Definition code
import Mathlib
namespace SelfSelReg
namespace Supplement
/-- **An eigendecomposition in the sense of the pseudocode** of Algorithms 6.2 and 6.3.
F. Zhou, *Linear Regression with Self-Selection Bias in Polynomial Time*, STOC 2027 submission
(manuscript sha256 5d65f750…), Algorithm 6.2, line 1, p.39 (PDF p.42): "Compute the eigenvalues
λ̂_1 ≥ ⋯ ≥ λ̂_{p_s} and corresponding orthonormal eigenvectors v̂_1, …, v̂_{p_s} of Â"; Algorithm 6.3,
line 5, p.43 (PDF p.46).
`IsEigDecomp M vals V`: `vals` is nonincreasing, the rows of `V` are orthonormal, and row `h` of `V`
is an eigenvector of the `p × p` matrix `M` for the eigenvalue `vals h`.
**Formalization Note.** The eigenvalues are determined by `M`; the eigenvectors are determined only
up to sign, and up to a rotation inside each eigenspace of a repeated eigenvalue. Every statement
using this predicate holds for every such choice. A matrix with an eigendecomposition is symmetric. -/
def IsEigDecomp {p : ℕ} (M : Matrix (Fin p) (Fin p) ℝ) (vals : Fin p → ℝ)
(V : Matrix (Fin p) (Fin p) ℝ) : Prop :=
Antitone vals ∧ V * V.transpose = 1 ∧ ∀ h, M.mulVec (V h) = vals h • V h
end Supplement
end SelfSelReg
Source
Zhou, Linear Regression with Self-Selection Bias in Polynomial Time, STOC 2027 submission (manuscript sha256 5d65f750…), Algorithm 6.2, line 1, p.39 (PDF p.42); Algorithm 6.3, line 5, p.43 (PDF p.46)