The RandNLA case study in VSCL: statements and proofs

Lean has checked proofs of the spectral-norm bound for element-wise sparsification, the structural bound for sketched low-rank approximation, the subspace embedding property and the relative-error least-squares bound of the subsampled randomized Hadamard transform, a sparse subspace embedding, and the relative-error least-squares bound with approximate leverage-score sampling, all in exact arithmetic. The bound for sparsification, the two results for the subsampled randomized Hadamard transform and the least-squares bound with leverage-score sampling rest on Lieb's concavity theorem, which the library proves. These results come from the survey by Drineas and Mahoney, RandNLA: Randomized Numerical Linear Algebra, Communications of the ACM 59(6), 2016, which this case study formalizes in VSCL. Lean reports that all 35 proofs use no axiom beyond its three standard ones (propext, Classical.choice and Quot.sound). Our paper discusses this case study.

Each statement is published apart from its proof, so that a reader can compare it with the survey without reading any proof. No expert outside our group has been asked to make this comparison. At commit 55a62f4 of 2026-11-16 the library publishes 47 statements from the survey, and 35 of them have a published proof. The subspace embedding for leverage-score sampling is among the 12 statements whose proof is not published.

The sparsification bound is proved for square matrices and a thresholded sampler. The low-rank bound adds a condition on the singular vectors and bounds the error rather than its square, which is weaker for the spectral and Frobenius norms. The sparse embedding, the two Hadamard results and the leverage-score least-squares bound fix choices that the survey leaves open. The two results for the subsampled randomized Hadamard transform take the number of rows to be a power of two, and no statement concerns running time. The library's notes on the groups of statements record each choice and change.

What the proofs depend on

For each of the six results above, the table gives its place in the survey and the number of theorems of the library that its proof depends on. We count a theorem if the proof refers to it directly or through a chain of references in Lean's elaborated statements and proofs, and leave out the theorems of Mathlib and the 57 further theorems in the case study's own files that the proofs reach.

ResultPlace in the surveyLibrary theorems
Spectral-norm bound for element-wise sparsificationEquation (2)430
Structural bound for sketched low-rank approximationEquation (9)184
Subspace embedding of the subsampled randomized Hadamard transformAlgorithm 3565
Relative-error least squares with that transformPage 87589
Relative-error least squares with approximate leverage-score samplingPage 87451
Sparse subspace embeddingAlgorithm 391
All 35 published proofs1,053

The proofs share many theorems, so the rows add up to more than the last. Together, the 35 proofs depend on 1,053 theorems of the library. Among them, 771 of the 1,053 theorems, on RandNLA, matrix inequalities and finite probability, entered the library with this case study, including a proof of Lieb's concavity theorem. Of the other 282, on general linear algebra, a search of the source text finds 117 to 136 also in the library's files for Higham's Accuracy and Stability of Numerical Algorithms, depending on how repeated short names are counted. The proofs differ in size, and twelve of the 35 depend on at most three theorems outside the RandNLA modules.

How to check a statement

  1. Read the statement's Lean text and the definitions it uses. The name of each statement and of each definition below leads to it in the library.
  2. Compare it with the survey at the place given under "In the survey".
  3. Read the library's note on its group, which records where a statement differs from the printed claim or adds a condition.
  4. Lean checks each published proof. Anyone can rebuild the library at commit 55a62f4, and Lean's #print axioms lists the axioms that a proof uses, here only the three standard ones.

How to cite

Cite this record with the commit of the library that it describes.

FieldValue
TitleThe RandNLA case study in VSCL: statements and proofs
Library commit55a62f4
Date2026-11-16
Repositoryhttps://github.com/the-numerical-proving-ground/lean-computational-mathematics

The library itself carries its own citation, in its citation file.

The statements

The list holds the 47 statements, grouped by the file of the library that holds them, and the five definitions that some of them use, last in their file. Each group carries the title that the library gives its file, and the library's own note on the file where there is one.

Each entry gives the name of the statement in Lean, the library's own description of it, its place in the survey as the library names it, the definitions that its Lean text uses, its Lean text, and whether its proof is published. For six statements a few plain words come first, which say what the statement asserts and how it differs from the survey. For a published proof the entry gives the number of theorems of the library that the proof depends on, counted as in the table. The name leads to the statement, each definition to its place, and the words "Proof published" to the proof, in the library at commit 55a62f4 of 2026-11-16. We do not reproduce the text of the survey.

Proof-free contracts for subspace invariance and geometry

BasisGeometry.lean · 2 statements, each with a published proof

CACM 59(6), p. 85, Eq. (6) and the prose after Eq. (7). These targets isolate basis independence and the deterministic consequences of an embedding event; they do not replace the separate randomized Eq. (7) construction.

  • leverageBasisInvariance

    The normalized leverage law is independent of the orthonormal basis chosen for the same positive-dimensional column space. Frame widths may be supplied independently; orthonormality and equal ranges force consistency.

    In the survey: Equation (6), page 85.

    Uses: HasOrthonormalColumns, leverageScore, leverageScoreProb

    Lean statement
    def leverageBasisInvariance : Prop :=
      ∀ (m n p : ℕ) (U : Matrix (Fin m) (Fin n) ℝ)
        (V : Matrix (Fin m) (Fin p) ℝ),
        0 < n → 0 < p → HasOrthonormalColumns U → HasOrthonormalColumns V →
        Set.range U.mulVec = Set.range V.mulVec →
          (U * U.transpose = V * V.transpose) ∧
          (∀ i, leverageScore U i = leverageScore V i) ∧
          (∀ i, leverageScoreProb U i = leverageScoreProb V i)

    Proof published. It depends on 4 theorems of the library.

  • subspaceEmbeddingGeometry

    Eq. (7), with ε in (0,1), preserves all squared norms in the specified column space, is injective there, and preserves the rank of the original matrix. S acts on the original vectors and S*U is its coordinate sketch.

    In the survey: Equation (7), page 85, and the text after it.

    Uses: HasOrthonormalColumns, idMatrix, opNorm2Le, rowSketchGram, vecNorm2Sq

    Lean statement
    def subspaceEmbeddingGeometry : Prop :=
      ∀ (m n d r : ℕ) (A : Matrix (Fin m) (Fin n) ℝ)
        (U : Matrix (Fin m) (Fin d) ℝ) (S : Matrix (Fin r) (Fin m) ℝ),
        HasOrthonormalColumns U →
        Set.range A.mulVec = Set.range U.mulVec →
        ∀ ε : ℝ, 0 < ε → ε < 1 →
        opNorm2Le (fun j k => idMatrix d j k - rowSketchGram (S * U) j k) ε →
          (∀ y ∈ Set.range A.mulVec,
            (1 - ε) * vecNorm2Sq y ≤ vecNorm2Sq (S.mulVec y) ∧
            vecNorm2Sq (S.mulVec y) ≤ (1 + ε) * vecNorm2Sq y) ∧
          Set.InjOn S.mulVec (Set.range A.mulVec) ∧
          (S * A).rank = A.rank

    Proof published. It depends on 19 theorems of the library.

Covered-support entry-residual moment contract

EntryResidualMoments.lean · 1 statement, with a published proof

Original row016, p83, concerns zero mean and bounded variance of entries of the raw Algorithm1 residual. This conditional contract explicitly retains the nonzero-entry support coverage required by corrected unbiasedness. It does not silently repair the original unrestricted claim. The supplied distribution is normalized by its finite-probability type, and draws use its literal iid law. No truncation or independence between different residual coordinates is asserted.

  • entryResidualMeanVariance

    Coordinate mean, exact variance, finite support bound and zero-atom branch for the original zero-initialized iid importance sketch on covered support.

    In the survey: Page 83, Algorithm 1, the mean and variance of the entries of its error.

    Uses: FiniteProbability, FiniteProbability.eventProb, FiniteProbability.expectationReal, FiniteProbability.iid, FiniteProbability.prob, FiniteProbability.varianceReal, entrySamplingResidual

    Lean statement
    def entryResidualMeanVariance : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ)
        (P : FiniteProbability (Fin m × Fin n)),
        0 < m → 0 < n → 0 < s →
        (∀ i j, A i j ≠ 0 → 0 < P.prob (i,j)) →
        ∀ i j,
          (P.iid s).expectationReal (fun ω => entrySamplingResidual A P ω i j) = 0 ∧
          (0 < P.prob (i,j) →
            (P.iid s).varianceReal (fun ω => entrySamplingResidual A P ω i j) =
              A i j ^ 2 * (1 / P.prob (i,j) - 1) / (s : ℝ) ∧
            0 ≤ A i j ^ 2 * (1 / P.prob (i,j) - 1) / (s : ℝ) ∧
            ∀ ω, 0 < (P.iid s).prob ω →
              |entrySamplingResidual A P ω i j| ≤ |A i j| * (1 + 1 / P.prob (i,j))) ∧
          (P.prob (i,j) = 0 →
            A i j = 0 ∧
            (P.iid s).eventProb {ω | entrySamplingResidual A P ω i j = 0} = 1 ∧
            (P.iid s).varianceReal (fun ω => entrySamplingResidual A P ω i j) = 0)

    Proof published. It depends on 29 theorems of the library.

Corrected, thresholded entry-sparsification contract

EntrySparsification.lean · 1 statement, with a published proof

This is the square theorem supported by Drineas--Zouzias (survey reference18), with its explicit zero branch and upward-compatible integer sample condition. It is a correction to applying survey Equation(2) to the unchanged raw sampler. The strict-threshold convention is the printed algorithm-box convention.

  • correctedTruncatedEntryGuarantee

    In plain words: For a square n × n matrix A, the entries smaller than ε/(2n) in absolute value are set to zero, and s samples are drawn independently from the remaining entries, with probabilities proportional to their squares. If 14 n log(2n/δ) times the squared Frobenius norm of A is at most s ε², then with probability at least 1 − δ the error in the spectral norm is at most ε and the sketch has at most s nonzero entries. The survey states Equation (2) for the sampler without this threshold, and this is the thresholded form of its reference 18.

    Corrected reference18 guarantee, including all matrices and at most s nonzero entries. The sample condition is multiplied by the positive eps².

    In the survey: Equation (2), in the corrected form of the survey's reference 18.

    Uses: ElementwiseSample, ElementwiseTrace, FiniteProbability.eventProb, frobNormSqRect, rectOpNorm2Le, truncatedElementwiseProbability, truncatedElementwiseSketch

    Lean statement
    def correctedTruncatedEntryGuarantee : Prop :=
      ∀ (n s : ℕ) (A : Fin n → Fin n → ℝ) (eps δ : ℝ),
        0 < n → 0 < s → 0 < eps → 0 < δ → δ < 1 →
        14 * (n : ℝ) * frobNormSqRect A * Real.log ((2 * (n : ℝ)) / δ) ≤
          (s : ℝ) * eps ^ 2 →
        1 - δ ≤
          (truncatedElementwiseProbability (s := s) (eps / (2 * (n : ℝ))) A).eventProb
            {outcome |
              rectOpNorm2Le (fun i j => A i j -
                truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome i j) eps ∧
              (Finset.univ.filter (fun ij : Fin n × Fin n =>
                truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s}

    Proof published. It depends on 430 theorems of the library.

Corrected entry sparsification on bounded accuracy

EntrySparsificationAccuracy.lean · 1 statement, with a published proof

This source-local contract selects strict thresholding, the actual squared-entry law with its deterministic zero branch, and accuracy and failure tolerance in (0,1). It states the support count for every output as well as the spectral error probability. The broader positive-accuracy contract remains unchanged.

  • correctedTruncatedEntryGuaranteeUnitAccuracy

    Corrected finite sampling guarantee for 0 < eps < 1, with deterministic support size and the actual Option-valued thresholded sampling law.

    In the survey: Equation (2), in the corrected form of the survey's reference 18, for an accuracy below one.

    Uses: ElementwiseSample, ElementwiseTrace, FiniteProbability.eventProb, frobNormSqRect, rectOpNorm2Le, truncatedElementwiseProbability, truncatedElementwiseSketch

    Lean statement
    def correctedTruncatedEntryGuaranteeUnitAccuracy : Prop :=
      ∀ (n s : ℕ) (A : Fin n → Fin n → ℝ) (eps δ : ℝ),
        0 < n → 0 < s → 0 < eps → eps < 1 → 0 < δ → δ < 1 →
        14 * (n : ℝ) * frobNormSqRect A * Real.log ((2 * (n : ℝ)) / δ) ≤
          (s : ℝ) * eps ^ 2 →
        (∀ outcome : Option (ElementwiseTrace n n s),
          (Finset.univ.filter (fun ij : Fin n × Fin n =>
            truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s) ∧
        1 - δ ≤
          (truncatedElementwiseProbability (s := s) (eps / (2 * (n : ℝ))) A).eventProb
            {outcome |
              rectOpNorm2Le (fun i j => A i j -
                truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome i j) eps ∧
              (Finset.univ.filter (fun ij : Fin n × Fin n =>
                truncatedElementwiseSketch (eps / (2 * (n : ℝ))) A outcome ij.1 ij.2 ≠ 0)).card ≤ s}

    Proof published. It depends on 430 theorems of the library.

Equation (7) as a success criterion

GramEmbeddingCriterion.lean · 1 statement, with a published proof

This is a condition on an arbitrary sketch, not a claim that a particular randomized construction succeeds. Its quadratic criterion holds simultaneously for every coefficient vector and includes zero coefficient dimension.

  • gramEmbeddingCriterion

    Eq. (7)'s identity-Gram equality and its exact all-vector interpretation.

    In the survey: Equation (7).

    Uses: HasOrthonormalColumns, idMatrix, opNorm2, rowGram, rowSketchGram, vecNorm2Sq

    Lean statement
    def gramEmbeddingCriterion : Prop :=
      ∀ (m d t : ℕ) (U : Matrix (Fin m) (Fin d) ℝ)
        (B : Matrix (Fin t) (Fin d) ℝ), HasOrthonormalColumns U →
        ∀ ε : ℝ, 0 < ε → ε < 1 →
          opNorm2 (fun i j => rowGram U i j - rowSketchGram B i j) =
            opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ∧
          (opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ≤ ε ↔
            ∀ x : Fin d → ℝ,
              |vecNorm2Sq (B.mulVec x) - vecNorm2Sq x| ≤ ε * vecNorm2Sq x) ∧
          (opNorm2 (fun i j => idMatrix d i j - rowSketchGram B i j) ≤ ε ↔
            ∀ x : Fin d → ℝ,
              (1 - ε) * vecNorm2Sq x ≤ vecNorm2Sq (B.mulVec x) ∧
              vecNorm2Sq (B.mulVec x) ≤ (1 + ε) * vecNorm2Sq x)

    Proof published. It depends on 18 theorems of the library.

Leading-subspace leverage distribution

LeadingSubspaceLeverage.lean · 1 statement, with a published proof

The footnote-e variant of equation (6) selects the first k left singular vectors of a supplied compatible ordered SVD. Thus the matrix A and the selected leading subspace are linked by reconstruction, rank and orthonormality, rather than by an unspecified leading-subspace predicate. Choices at a repeated singular value are fixed by the supplied SVD. An arbitrary orthonormal basis of that fixed subspace is allowed, specified by equality of actual matrix-vector image sets. Rank-deficient inputs are allowed.

  • leadingSubspaceLeverageDistribution

    Equation (6), footnote e: normalized leverage probabilities of one chosen leading rank-k left singular subspace. The denominator is k.

    In the survey: Equation (6), footnote e.

    Uses: HasOrthonormalColumns, IsRealMatrixSVD, leadingLeftSingularColumns, leadingLeftSingularProjector, leverageScoreProb, rowSqNormProbDen

    Lean statement
    def leadingSubspaceLeverageDistribution : Prop :=
      ∀ (m n : ℕ) (A : Matrix (Fin m) (Fin n) ℝ),
        0 < m → 0 < n →
        ∀ (k : ℕ) (_hkpos : 0 < k) (hk : k ≤ A.rank)
          (s : Fin n → ℝ)
          (u : Fin A.rank → EuclideanSpace ℝ (Fin m))
          (v : Fin A.rank → EuclideanSpace ℝ (Fin n)),
          IsRealMatrixSVD A A.rank s u v →
          ∀ W : Matrix (Fin m) (Fin k) ℝ,
            HasOrthonormalColumns W →
            Set.range W.mulVec = Set.range (leadingLeftSingularColumns u hk).mulVec →
            rowSqNormProbDen W = (k : ℝ) ∧
            (∀ i, 0 ≤ leverageScoreProb W i) ∧
            (∑ i : Fin m, leverageScoreProb W i) = 1 ∧
            (∀ i, leverageScoreProb W i = (∑ j : Fin k, W i j ^ 2) / (k : ℝ)) ∧
            ∀ i, leverageScoreProb W i = leadingLeftSingularProjector u hk i i / (k : ℝ)

    Proof published. It depends on 10 theorems of the library.

Page-87 joint least-squares sketch constructions

LeastSquaresConstructions.lean · 2 statements, each with a published proof

Original claims026/027 specify constructions separately from their quantitative children. Scores in026 are supplied relative approximations, not silently exact scores. The Walsh realization in027 has 2^q rows; padding is not implicit. Neither contract asserts score-computation cost, running time or sketch quality.

  • relativeLeverageLeastSquaresConstruction

    Original026 construction: normalize supplied relative scores, use an iid common A/b row sampler, and return actual sketch minimizers. Rank zero returns0 without introducing a leverage denominator.

    In the survey: Page 87, the least-squares sketch, with approximate leverage scores.

    Uses: FiniteProbability, FiniteProbability.eventProb, FiniteProbability.iid, FiniteProbability.prob, IsLeastSquaresMinimizer, RelativeLeverageScores, RowTrace, augmentedDataSpan, lsColumnSpaceBasisMatrix, lsResidual, rowNormSq, rowSampleSketchWithProb, rowSampleVectorWithProb, vecNorm2

    Lean statement
    def relativeLeverageLeastSquaresConstruction : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
        (a : Fin m → ℝ) (α : ℝ),
        0 < m → 0 < n → 0 < s → 0 ≤ α → α < 1 →
        (∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α) →
          (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 →
            IsLeastSquaresMinimizer A b (fun _ => 0)) ∧
          ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
            ∃ (P : FiniteProbability (Fin m)) (xHat : RowTrace m s → Fin n → ℝ),
              (∀ i, P.prob i = a i / ∑ j : Fin m, a j) ∧
              (∀ i, ((1 - α) / (1 + α)) *
                (rowNormSq (lsColumnSpaceBasisMatrix A) i /
                  (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) ≤ P.prob i) ∧
              (∀ samples, (P.iid s).prob samples = ∏ t, P.prob (samples t)) ∧
              (P.iid s).eventProb {samples | ∀ t, 0 < P.prob (samples t)} = 1 ∧
              (∀ (samples : RowTrace m s) (t : Fin s) (j : Fin n), rowSampleSketchWithProb s A P.prob samples t j =
                A (samples t) j / Real.sqrt ((s : ℝ) * P.prob (samples t))) ∧
              (∀ (samples : RowTrace m s) (t : Fin s), rowSampleVectorWithProb P.prob b samples t =
                b (samples t) / Real.sqrt ((s : ℝ) * P.prob (samples t))) ∧
              ∀ samples, IsLeastSquaresMinimizer
                (rowSampleSketchWithProb s A P.prob samples)
                (rowSampleVectorWithProb P.prob b samples) (xHat samples) ∧
                ∀ x, vecNorm2 (lsResidual
                  (rowSampleSketchWithProb s A P.prob samples)
                  (rowSampleVectorWithProb P.prob b samples) (xHat samples)) ≤
                  vecNorm2 (lsResidual
                    (rowSampleSketchWithProb s A P.prob samples)
                    (rowSampleVectorWithProb P.prob b samples) x)

    Proof published. It depends on 18 theorems of the library.

  • walshUniformLeastSquaresConstruction

    Original027 construction: independent signs then independent uniform row sampling, with the same HD transform and scale on A and b. All input ranks are allowed; minimizers are actual outputs rather than hypotheses.

    In the survey: Page 87, the least-squares sketch, with a randomized Hadamard transform.

    Uses: FiniteProbability.prob, HadamardFlat, IsLeastSquaresMinimizer, IsOrthogonal, RademacherTrace, RowSample, RowTrace, leastSquaresWalshMatrix, diagMatrix, lsResidual, matMul, matMulVec, preconditionRows, rademacherSignVector, rademacherTraceProbability, rowSampleSketchWithProb, rowSampleVectorWithProb, signedHadamardUniformRowTraceProbability, uniformRowProb, uniformRowTraceProbability, vecNorm2

    Lean statement
    def walshUniformLeastSquaresConstruction : Prop :=
      ∀ (q n s : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ)
        (hm : 0 < 2 ^ q), 0 < n → 0 < s →
          let m := 2 ^ q
          let H := leastSquaresWalshMatrix q
          IsOrthogonal m H ∧ HadamardFlat m H ∧
          ∃ xHat : RademacherTrace m × RowTrace m s → Fin n → ℝ,
            (∀ z, (signedHadamardUniformRowTraceProbability (m := m) (s := s) hm).prob z =
              (rademacherTraceProbability m).prob z.1 *
                (uniformRowTraceProbability (steps := s) hm).prob z.2) ∧
            (∀ samples, (uniformRowTraceProbability (steps := s) hm).prob samples =
              ∏ _t : Fin s, ((m : ℝ)⁻¹)) ∧
            ∀ (ω : RademacherTrace m) (samples : RowTrace m s),
              let T := matMul m H (diagMatrix (rademacherSignVector ω))
              let B := preconditionRows T A
              let c := matMulVec m T b
              (∀ t j, rowSampleSketchWithProb s B uniformRowProb samples t j =
                Real.sqrt ((m : ℝ) / (s : ℝ)) * B (samples t) j) ∧
              (∀ t, rowSampleVectorWithProb uniformRowProb c samples t =
                Real.sqrt ((m : ℝ) / (s : ℝ)) * c (samples t)) ∧
              IsLeastSquaresMinimizer
                (rowSampleSketchWithProb s B uniformRowProb samples)
                (rowSampleVectorWithProb uniformRowProb c samples) (xHat (ω, samples)) ∧
              ∀ x, vecNorm2 (lsResidual
                (rowSampleSketchWithProb s B uniformRowProb samples)
                (rowSampleVectorWithProb uniformRowProb c samples) (xHat (ω, samples))) ≤
                vecNorm2 (lsResidual
                  (rowSampleSketchWithProb s B uniformRowProb samples)
                  (rowSampleVectorWithProb uniformRowProb c samples) x)

    Proof published. It depends on 49 theorems of the library.

  • leastSquaresWalshMatrix

    The concrete normalized Walsh matrix used by original027.

    Lean statement
    noncomputable def leastSquaresWalshMatrix (q : ℕ) : Fin (2 ^ q) → Fin (2 ^ q) → ℝ :=
      fun i k => Real.sqrt (((2 ^ q : ℕ) : ℝ)⁻¹) * sylvesterHadamardSignPattern q i k

    A definition that statements of this file use.

Least-squares existence and exact-leverage output contracts

LeastSquaresExistence.lean · 2 statements, 1 with a published proof

Equation (8), p. 86, has a minimizer for every finite real input, including rank-deficient and empty matrices. The separate page-87 exact-leverage case selects both an original minimizer and exact sketch minimizers and proves their relative residual guarantee. Classical selection makes no computational-cost or approximate-leverage-score assertion.

  • leastSquaresMinimizerExists

    Equation (8): existence of a minimizer for both the squared library objective and the paper's unsquared Euclidean residual, without rank hypotheses.

    In the survey: Equation (8), page 86.

    Uses: IsLeastSquaresMinimizer, lsResidual, vecNorm2

    Lean statement
    def leastSquaresMinimizerExists : Prop :=
      ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ),
        ∃ xOpt : Fin n → ℝ,
          IsLeastSquaresMinimizer A b xOpt ∧
          ∀ x, vecNorm2 (lsResidual A b xOpt) ≤ vecNorm2 (lsResidual A b x)

    Proof published. It depends on 4 theorems of the library.

  • exactLeverageLeastSquaresOutput

    Mathematical exact-leverage case of the page-87 algorithm: original and sampled minimizers exist and their returned residual satisfies the guarantee. No minimizer or final error bound is supplied as a premise. Positive input rank includes one; the all-rank minimizer-existence contract above includes rank zero.

    In the survey: Page 87, the least-squares algorithm, with exact leverage scores.

    Uses: FiniteProbability.eventProb, IsLeastSquaresMinimizer, RowSample, RowTrace, augmentedDataSpan, leverageTraceProbability, lsColumnSpaceBasisMatrix, lsResidual, rowSampleLSMatrixWithBasisScale, rowSampleLSVectorWithBasisScale, vecNorm2

    Lean statement
    def exactLeverageLeastSquaresOutput : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
        (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0))) (η δ : ℝ),
        0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 →
        10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) *
          Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) →
        8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) →
          ∃ (xOpt : Fin n → ℝ) (xHat : RowTrace m s → Fin n → ℝ),
            IsLeastSquaresMinimizer A b xOpt ∧
            (∀ samples, IsLeastSquaresMinimizer
              (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples)
              (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples)
              (xHat samples)) ∧
            1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A)
              (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb
              {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤
                (1 + η) * vecNorm2 (lsResidual A b xOpt)}

    No proof published.

Exact leverage sketching source contracts

LeverageSketching.lean · 5 statements, 1 with a published proof

Equation (7), p. 85, is instantiated by Algorithm 2 with the exact normalized leverage distribution of a positive-dimensional orthonormal basis. The stated sample budget is an explicit sufficient second-moment budget; the survey does not specify an equation-(7) sample count. Equation (8), p. 86, minimizes the unsquared Euclidean residual. Its page-87 sampling consequence is represented here for exact leverage probabilities and exact sketch minimizers, with the same sampled rows and scaling for A and b. Positive input rank includes one. Rank zero has a separate deterministic branch because the normalized leverage distribution is undefined there. These contracts concern mathematical guarantees. Approximate leverage-score construction, its computational cost, and the survey's running-time assertions are separate obligations and are not asserted by these contracts.

  • leverageSubspaceEmbedding

    Equation (7), with a literal independent leverage row sketch and a sufficient sample budget, including the displayed identity-Gram equality.

    In the survey: Equation (7), page 85, with Algorithm 2 and leverage-score sampling.

    Uses: FiniteProbability.eventProb, HasOrthonormalColumns, RowSample, RowTrace, idMatrix, leverageTraceProbability, opNorm2, rowGram, rowSampleGram

    Lean statement
    def leverageSubspaceEmbedding : Prop :=
      ∀ (m n s : ℕ) (U : Fin m → Fin n → ℝ)
        (hU : HasOrthonormalColumns U) (hn : 0 < n)
        (ε δ : ℝ),
        0 < s → 0 < ε → ε < 1 → 0 < δ → δ < 1 →
        1 / ((s : ℝ) * (ε / (n : ℝ)) ^ 2) ≤ δ →
          1 - δ ≤ (leverageTraceProbability (steps := s) U hU hn).eventProb
            {samples |
              opNorm2 (fun j k => rowGram U j k - rowSampleGram s U samples j k) =
                opNorm2 (fun j k => idMatrix n j k - rowSampleGram s U samples j k) ∧
              opNorm2 (fun j k => idMatrix n j k - rowSampleGram s U samples j k) ≤ ε}

    No proof published.

  • leastSquaresResidualMinimum

    Equation (8)'s residual-norm minimization agrees with the squared objective used by the library. Neither uniqueness nor exact solvability is required.

    In the survey: Equation (8), page 86.

    Uses: IsLeastSquaresMinimizer, lsResidual, vecNorm2

    Lean statement
    def leastSquaresResidualMinimum : Prop :=
      ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (xOpt : Fin n → ℝ),
        IsLeastSquaresMinimizer A b xOpt ↔
          ∀ x, vecNorm2 (lsResidual A b xOpt) ≤ vecNorm2 (lsResidual A b x)

    Proof published. It depends on 3 theorems of the library.

  • leverageLeastSquaresObjective

    Exact-leverage mathematical case of the page-87 LS guarantee, measured in squared residual objective. The sample count depends reciprocally on accuracy at fixed confidence. Basis dimension is the input rank, not augmented rank.

    In the survey: Page 87, the least-squares guarantee, with exact leverage scores.

    Uses: FiniteProbability.eventProb, IsLeastSquaresMinimizer, RowSample, RowTrace, augmentedDataSpan, leverageTraceProbability, lsColumnSpaceBasisMatrix, lsObjective, rowSampleLSMatrixWithBasisScale, rowSampleLSVectorWithBasisScale

    Lean statement
    def leverageLeastSquaresObjective : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
        (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)))
        (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ)
        (η δ : ℝ),
        0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 →
        IsLeastSquaresMinimizer A b xOpt →
        (∀ samples, IsLeastSquaresMinimizer
          (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples)
          (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples)
          (xHat samples)) →
        10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) *
          Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) →
        8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) →
          1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A)
            (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb
            {samples | lsObjective A b (xHat samples) ≤ (1 + η) * lsObjective A b xOpt}

    No proof published.

  • leverageLeastSquaresResidualNorm

    The same exact-leverage sampler and exact sketch solution, measured in Equation (8)'s unsquared Euclidean residual norm.

    In the survey: Page 87, the least-squares guarantee, with exact leverage scores, measured as in Equation (8).

    Uses: FiniteProbability.eventProb, IsLeastSquaresMinimizer, RowSample, RowTrace, augmentedDataSpan, leverageTraceProbability, lsColumnSpaceBasisMatrix, lsResidual, rowSampleLSMatrixWithBasisScale, rowSampleLSVectorWithBasisScale, vecNorm2

    Lean statement
    def leverageLeastSquaresResidualNorm : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
        (hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)))
        (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ)
        (η δ : ℝ),
        0 < s → 0 < η → η < 1 → 0 < δ → δ < 1 →
        IsLeastSquaresMinimizer A b xOpt →
        (∀ samples, IsLeastSquaresMinimizer
          (rowSampleLSMatrixWithBasisScale s (lsColumnSpaceBasisMatrix A) A samples)
          (rowSampleLSVectorWithBasisScale s (lsColumnSpaceBasisMatrix A) b samples)
          (xHat samples)) →
        10 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) *
          Real.log ((4 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ)) / δ) ≤ (s : ℝ) →
        8 * (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) : ℝ) / (η * δ) ≤ (s : ℝ) →
          1 - δ ≤ (leverageTraceProbability (steps := s) (lsColumnSpaceBasisMatrix A)
            (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd).eventProb
            {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤
              (1 + η) * vecNorm2 (lsResidual A b xOpt)}

    No proof published.

  • zeroRankLeastSquares

    Zero input rank: every coefficient vector has the same residual objective; no normalized leverage sampler or probability law is introduced.

    In the survey: Page 87, the least-squares guarantee, extended to an input of rank zero.

    Uses: augmentedDataSpan, lsObjective, lsResidual, vecNorm2

    Lean statement
    def zeroRankLeastSquares : Prop :=
      ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ),
        Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 →
        ∀ (xHat xOpt : Fin n → ℝ) (η : ℝ), 0 ≤ η →
          lsObjective A b xHat ≤ (1 + η) * lsObjective A b xOpt ∧
          vecNorm2 (lsResidual A b xHat) ≤ (1 + η) * vecNorm2 (lsResidual A b xOpt)

    No proof published.

Corrected source contract for the structural low-rank bound

LowRankApproximation.lean · 1 statement, with a published proof

The literal arbitrary-spanning-matrix wording preceding equation (9) on printed page 88 of Drineas--Mahoney (2016) is false. This proposed corrected contract requires compatible orthonormal right singular coordinates from one ordered SVD. It does not assert that the printed wording was already correct or that the correction has been admitted or independently reviewed. The orthonormal SVD convention is explicit in Boutsidis--Mahoney--Drineas, SODA09 §2.1 and corrected arXiv:0812.4293v2 §2.1. Mahoney--Drineas, Structural properties underlying high-quality Randomized Numerical Linear Algebra algorithms (2016), §§3.1--3.3, supplies the unsquared bound for every unitarily invariant norm and arbitrary sketch width. Its printed tail-dimension and undefined-Y defects are not adopted here. HMT11 Theorem 9.1 separately supports oversampling and the zero-tail case, but states only spectral/Frobenius bounds. The full right basis has n = k + q coordinates; left null coordinates are zero. Thus the tail includes the null singular directions even for wide matrices. All shapes use the same norm family, with exact isometric coherence. Full row rank of the sampled head is surjectivity of its matrix-vector map. The explicit k ≤ r retains the printed oversampling condition; it is also implied by that surjectivity. No rank or positive-leading-singular-value restriction is imposed.

  • correctedLowRankApproximationStructuralBound

    In plain words: For every unitarily invariant norm, ‖A − PA‖ ≤ ‖Σ⊥‖ + ‖Σ⊥ V⊥ᵀ Z (Vₖᵀ Z)⁺‖, where P is the orthogonal projector onto the range of AZ, Σ⊥ and V⊥ hold the trailing singular values and right singular vectors of one singular value decomposition of A, Z has at least k columns, and Vₖᵀ Z has full row rank. The bound is on the error itself, not on its square. For the spectral and Frobenius norms this is weaker, by a factor of at most √2, than the same bound on the square of the error. The library's note says that the wording before Equation (9), which allows any matrix spanning the same space as Vₖ, fails, and Lean does not check that remark.

    Corrected equation (9): compatible orthonormal singular coordinates, arbitrary oversampling, and one coherent unitarily invariant norm family.

    In the survey: Equation (9), page 88, in a corrected form.

    Uses: Ch14Ext.ch14ext_rectMoorePenrosePseudoinverse, ComplexMatrixUnitaryInvariantNormFamily, ComplexMatrixUnitaryInvariantNormFamily.realNorm, IsRealFullRightSVD, columnSketchMoorePenroseProjector, finiteTranspose, rectMatMul, rectMatMulVec, squareSVDHeadRight, squareSVDTailDiagonal, squareSVDTailRight

    Lean statement
    def correctedLowRankApproximationStructuralBound : Prop :=
      ∀ (m k q r : ℕ) (N : ComplexMatrixUnitaryInvariantNormFamily)
        (A Ufull : Matrix (Fin m) (Fin (k + q)) ℝ)
        (sigma : Fin (k + q) → ℝ)
        (Vfull : Matrix (Fin (k + q)) (Fin (k + q)) ℝ)
        (Z : Fin (k + q) → Fin r → ℝ),
        k ≤ r →
        IsRealFullRightSVD A Ufull sigma Vfull →
        Function.Surjective
          (rectMatMulVec (rectMatMul (finiteTranspose (squareSVDHeadRight Vfull)) Z)) →
        N.realNorm (fun i j => A i j -
          rectMatMul (columnSketchMoorePenroseProjector A Z) A i j) ≤
          N.realNorm (squareSVDTailDiagonal sigma) +
            N.realNorm (rectMatMul
              (rectMatMul (squareSVDTailDiagonal sigma)
                (rectMatMul (finiteTranspose (squareSVDTailRight Vfull)) Z))
              (Ch14Ext.ch14ext_rectMoorePenrosePseudoinverse
                (rectMatMul (finiteTranspose (squareSVDHeadRight Vfull)) Z)))

    Proof published. It depends on 184 theorems of the library.

Joint Walsh sketch geometry and actual sampled-system coherence

PreprocessingCoherence.lean · 4 statements, each with a published proof

These contracts instantiate the admitted real-Walsh realization. Rows are iid with replacement independently of the signs. The historical child identifier also mentions Fourier; no complex Fourier realization is asserted here. The actual sampled leverage is the normalized diagonal of W (WᵀW)⁻¹ Wᵀ, with its full-rank domain proved from sketch geometry. Ambient logarithms are retained; the d log d specialization has an explicit rank-versus-ambient-log regime. No running-time assertion is made.

  • signedWalshJointEmbedding

    In plain words: There is a constant C > 0 such that, for an orthonormal basis U of a d-dimensional subspace of R^m with m = 2^p and d ≤ m, 0 < ε < 1, 0 < δ < 1, and a sketch by random signs, the Walsh–Hadamard transform and at least C (d + log(2m/δ)) log(2d/δ)/ε² rows sampled uniformly, with probability at least 1 − δ the rows of the transformed basis have squared norms at most (√d + √(8 log(2m/δ)))²/m, the Gram matrix of the sketch is within ε of the identity in the spectral norm, and every squared length in the subspace is kept within a factor 1 ± ε. The statement asserts that some constant exists, and the proof takes C = 1000.

    The full joint child022 guarantee, including simultaneous geometry for all vectors of the represented fixed subspace and the sharp row radius.

    In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform and uniform sampling of rows.

    Uses: FiniteProbability.eventProb, HasOrthonormalColumns, RademacherTrace, RowSample, RowTrace, walshRotation, finiteIdMatrix, hadamardJointRowRadius, opNorm2, rectMatMulVec, rowGram, rowNormSq, signedHadamardBasis, signedHadamardUniformRowTraceProbability, uniformScaledRowSketch, vecNorm2Sq

    Lean statement
    def signedWalshJointEmbedding : Prop :=
      ∃ C : ℝ, 0 < C ∧ ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ),
        HasOrthonormalColumns U → 0 < d → d ≤ 2 ^ p → 0 < s →
        ∀ ε δ : ℝ, 0 < ε → ε < 1 → 0 < δ → δ < 1 →
        C / ε ^ 2 * ((d : ℝ) + Real.log ((2 * ((2 ^ p : ℕ) : ℝ)) / δ)) *
          Real.log ((2 * (d : ℝ)) / δ) ≤ (s : ℝ) →
        1 - δ ≤ (signedHadamardUniformRowTraceProbability
          (m := 2 ^ p) (s := s) (pow_pos (by norm_num) p)).eventProb
          {z | let Q := signedHadamardBasis (walshRotation p) U z.1
               let W := uniformScaledRowSketch Q z.2
               (∀ i, rowNormSq Q i ≤ hadamardJointRowRadius (2 ^ p) d δ / ((2 ^ p : ℕ) : ℝ)) ∧
               opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ ε ∧
               ∀ x : Fin d → ℝ,
                 (1 - ε) * vecNorm2Sq (rectMatMulVec U x) ≤ vecNorm2Sq (rectMatMulVec W x) ∧
                 vecNorm2Sq (rectMatMulVec W x) ≤ (1 + ε) * vecNorm2Sq (rectMatMulVec U x)}

    Proof published. It depends on 565 theorems of the library.

  • sampledWalshProjectorCoherence

    Actual sampled-projector coherence on every stated successful geometry event, rather than the unnormalized row norm of the sampled table.

    In the survey: Algorithm 3, the same preprocessing, the leverage scores of the sampled rows.

    Uses: HasOrthonormalColumns, RademacherTrace, RowTrace, walshRotation, finiteIdMatrix, fullRankLeverageProb, opNorm2, rowGram, rowNormSq, signedHadamardBasis, uniformScaledRowSketch

    Lean statement
    def sampledWalshProjectorCoherence : Prop :=
      ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ),
        HasOrthonormalColumns U → 0 < d → 0 < s →
        ∀ δ : ℝ, 0 < δ → δ < 1 →
        ∀ (ω : RademacherTrace (2 ^ p)) (samples : RowTrace (2 ^ p) s),
        let Q := signedHadamardBasis (walshRotation p) U ω
        let W := uniformScaledRowSketch Q samples
        let L := (Real.sqrt (d : ℝ) +
          Real.sqrt (8 * Real.log (((2 ^ p : ℕ) : ℝ) / δ))) ^ 2
        (∀ i, rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ)) →
        opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ (1 / 2 : ℝ) →
          Matrix.rank (W : Matrix (Fin s) (Fin d) ℝ) = d ∧
          (∀ t, 0 ≤ fullRankLeverageProb W t) ∧
          (∑ t : Fin s, fullRankLeverageProb W t) = 1 ∧
          ∀ t, fullRankLeverageProb W t ≤ 2 * L / ((s : ℝ) * (d : ℝ))

    Proof published. It depends on 31 theorems of the library.

  • signedWalshCoherenceSampleScale

    Fixed-confidence joint geometry and actual sampled projector coherence at the general count, and its rank-dominates-log specialization. The same positive universal confidence and sample constant work for all fixed inputs.

    In the survey: Algorithm 3, the same preprocessing, its number of sampled rows.

    Uses: FiniteProbability, FiniteProbability.eventProb, HasOrthonormalColumns, RademacherTrace, RowSample, RowTrace, walshRotation, finiteIdMatrix, fullRankLeverageProb, hadamardJointRowRadius, opNorm2, rowGram, rowNormSq, signedHadamardBasis, signedHadamardUniformRowTraceProbability, uniformScaledRowSketch

    Lean statement
    def signedWalshCoherenceSampleScale : Prop :=
      ∃ C q0 : ℝ, 0 < C ∧ 0 < q0 ∧ q0 < 1 ∧
        ∀ (p d s : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ),
          HasOrthonormalColumns U → 0 < d → d ≤ 2 ^ p → 0 < s →
          let success := {z : RademacherTrace (2 ^ p) × RowTrace (2 ^ p) s |
            let Q := signedHadamardBasis (walshRotation p) U z.1
            let W := uniformScaledRowSketch Q z.2
            let L := hadamardJointRowRadius (2 ^ p) d (1 / 2)
            (∀ i, rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ)) ∧
            opNorm2 (fun j k => finiteIdMatrix j k - rowGram W j k) ≤ (1 / 2 : ℝ) ∧
            Matrix.rank (W : Matrix (Fin s) (Fin d) ℝ) = d ∧
            ∀ t, fullRankLeverageProb W t ≤ 2 * L / ((s : ℝ) * (d : ℝ))}
          let P := signedHadamardUniformRowTraceProbability
            (m := 2 ^ p) (s := s) (pow_pos (by norm_num) p)
          (C * ((d : ℝ) + Real.log (2 * ((2 ^ p : ℕ) : ℝ))) * Real.log (2 * (d : ℝ)) ≤ (s : ℝ) →
            q0 ≤ P.eventProb success) ∧
          (Real.log (2 * ((2 ^ p : ℕ) : ℝ)) ≤ (d : ℝ) →
            (2 * C) * (d : ℝ) * Real.log (2 * (d : ℝ)) ≤ (s : ℝ) →
            q0 ≤ P.eventProb success)

    Proof published. It depends on 570 theorems of the library.

  • signedWalshCoherenceGuarantees

    Complete selected row023 geometry, rotated spreading, actual sampled projector coherence, and quantified sample-scale contract.

    In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform, its guarantees together.

    Uses: sampledWalshProjectorCoherence, signedWalshCoherenceSampleScale, signedWalshExactGeometry, signedWalshMassSpreading

    Lean statement
    def signedWalshCoherenceGuarantees : Prop :=
      signedWalshExactGeometry ∧ signedWalshMassSpreading ∧
        sampledWalshProjectorCoherence ∧ signedWalshCoherenceSampleScale

    Proof published. It depends on 583 theorems of the library.

Selected preprocessing geometry for Algorithm 3

PreprocessingGeometry.lean · 5 statements, 4 with a published proof

The survey's qualitative statement is instantiated by two distinct laws. The square Sylvester/Walsh transform preserves geometry exactly and spreads the leverage of a fixed positive-dimensional subspace. Its logarithmic constant comes from the primary signed-Hadamard row-norm bound, not from the survey. The signed-hash sparse family directly embeds a subspace and makes no claim that its output leverage is flattened. Zero-dimensional subspaces are handled without dividing a leverage score by zero.

  • signedWalshExactGeometry

    Exact geometry for every realization of the actual independent sign law.

    In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform.

    Uses: HasOrthonormalColumns, RademacherTrace, walshRotation, diagMatrix, matMul, preconditionRows, rademacherSignVector

    Lean statement
    def signedWalshExactGeometry : Prop :=
      ∀ (p d : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U →
        ∀ ω : RademacherTrace (2 ^ p),
          HasOrthonormalColumns
            (preconditionRows
              (matMul (2 ^ p) (walshRotation p) (diagMatrix (rademacherSignVector ω))) U)

    Proof published. It depends on 44 theorems of the library.

  • signedWalshMassSpreading

    Sharp simultaneous row-norm and normalized-leverage bound for a fixed subspace. The two bounds hold on the same sign event.

    In the survey: Algorithm 3, the preprocessing with a randomized Hadamard transform, with a constant from outside the survey.

    Uses: FiniteProbability.eventProb, HasOrthonormalColumns, RademacherTrace, walshRotation, diagMatrix, leverageScoreProb, matMul, preconditionRows, rademacherSignVector, rademacherTraceProbability, rowNormSq

    Lean statement
    def signedWalshMassSpreading : Prop :=
      ∀ (p d : ℕ) (U : Fin (2 ^ p) → Fin d → ℝ), HasOrthonormalColumns U →
        0 < d → ∀ δ : ℝ, 0 < δ → δ < 1 →
          1 - δ ≤ (rademacherTraceProbability (2 ^ p)).eventProb
            {ω | ∀ i : Fin (2 ^ p),
              let Q := preconditionRows
                (matMul (2 ^ p) (walshRotation p) (diagMatrix (rademacherSignVector ω))) U
              let L := (Real.sqrt (d : ℝ) +
                Real.sqrt (8 * Real.log (((2 ^ p : ℕ) : ℝ) / δ))) ^ 2
              rowNormSq Q i ≤ L / ((2 ^ p : ℕ) : ℝ) ∧
              leverageScoreProb Q i ≤ L / (((2 ^ p : ℕ) : ℝ) * (d : ℝ))}

    Proof published. It depends on 149 theorems of the library.

  • sparseSignedHashSubspaceGeometry

    In plain words: For an orthonormal basis U of a d-dimensional subspace, 0 < ε < 1 and 0 < δ < 1, and a sparse sign-and-hash sketch with at least (d² + d)/(ε² δ) rows, with probability at least 1 − δ the sketch keeps every squared length in the subspace within a factor 1 ± ε. The threshold is the library's, and the survey states this kind of result qualitatively.

    Signed-hash sparse preprocessing directly embeds a fixed subspace. Each input coordinate has an independent uniform hash and independent unbiased sign. The same event gives the spectral Gram bound and geometry for every subspace vector, with the dimension threshold (d²+d)/(ε²δ).

    In the survey: Algorithm 3, the preprocessing with a sparse sign-and-hash transform.

    Uses: CountSketchHash, FiniteProbability.eventProb, HasOrthonormalColumns, RademacherTrace, countSketchProbability, countSketchRows, idMatrix, opNorm2, preconditionRows, rademacherSignVector, rectMatMulVec, rowGram, vecNorm2Sq

    Lean statement
    def sparseSignedHashSubspaceGeometry : Prop :=
      ∀ (m d t : ℕ) (ht : 0 < t) (U : Fin m → Fin d → ℝ),
        0 < m → HasOrthonormalColumns U →
        ∀ ε δ : ℝ, 0 < ε → ε < 1 → 0 < δ → δ < 1 →
        ((d : ℝ) ^ 2 + (d : ℝ)) / (ε ^ 2 * δ) ≤ (t : ℝ) →
          1 - δ ≤ (countSketchProbability (r := t) (m := m) ht).eventProb
            {x | let Pi := countSketchRows x.1 (rademacherSignVector x.2)
              opNorm2 (fun j k => idMatrix d j k - rowGram (preconditionRows Pi U) j k) ≤ ε ∧
              ∀ v : Fin m → ℝ, (∃ z : Fin d → ℝ, v = rectMatMulVec U z) →
                (1 - ε) * vecNorm2Sq v ≤ vecNorm2Sq (rectMatMulVec Pi v) ∧
                vecNorm2Sq (rectMatMulVec Pi v) ≤ (1 + ε) * vecNorm2Sq v}

    Proof published. It depends on 91 theorems of the library.

  • preprocessingGeometry

    Combined parent contract for the two selected preprocessing families: exact signed-Walsh geometry, its mass spreading, and sparse signed-hash subspace geometry with its own law and dimension threshold.

    In the survey: Algorithm 3, the preprocessing with either transform.

    Uses: signedWalshExactGeometry, signedWalshMassSpreading, sparseSignedHashSubspaceGeometry

    Lean statement
    def preprocessingGeometry : Prop :=
      signedWalshExactGeometry ∧ signedWalshMassSpreading ∧ sparseSignedHashSubspaceGeometry

    Proof published. It depends on 216 theorems of the library.

  • zeroSubspacePreprocessingGeometry

    Every linear preprocessing map preserves the zero subspace exactly. This branch has no normalized leverage probability or division by its dimension.

    In the survey: Algorithm 3, the preprocessing, for a subspace of dimension zero.

    Uses: rectMatMulVec, vecNorm2Sq

    Lean statement
    def zeroSubspacePreprocessingGeometry : Prop :=
      ∀ (m t : ℕ) (Pi : Fin t → Fin m → ℝ) (v : Fin m → ℝ),
        v = 0 → rectMatMulVec Pi v = 0 ∧
          vecNorm2Sq (rectMatMulVec Pi v) = vecNorm2Sq v

    No proof published.

  • walshRotation

    The concrete normalized Sylvester/Walsh matrix in dimension 2^p.

    Lean statement
    noncomputable def walshRotation (p : ℕ) : Fin (2 ^ p) → Fin (2 ^ p) → ℝ :=
      fun i k => Real.sqrt (((2 ^ p : ℕ) : ℝ)⁻¹) * sylvesterHadamardSignPattern p i k

    A definition that statements of this file use.

Quantitative children of supplied-score leverage least squares

RelativeLeverageLeastSquaresRate.lean · 4 statements, 1 with a published proof

The score tolerance α is separate from residual tolerance ε. Its unavoidable factor β⁻¹ is explicit. Bounded score tolerance α≤1/2 gives β⁻¹≤3, hence the source scale with an absolute constant. No score-computation cost is asserted.

  • relativeLeverageLeastSquaresRelativeError

    In plain words: There is a constant C ≥ 1 such that, for an m × n matrix A, a vector b, row scores a with (1 − α) ℓᵢ ≤ aᵢ ≤ (1 + α) ℓᵢ for the leverage scores ℓᵢ of the column space of A and some 0 ≤ α < 1, 0 < ε < 1, and at least C n log(2m)/(((1 − α)/(1 + α)) ε) rows of A and b sampled independently with probabilities proportional to the scores, every exact solution of the sketched problem has a residual at most (1 + ε) times the least residual, with probability at least 1/2. The statement asserts that some constant exists, and the proof takes C = 4096.

    Original026-relative-error: every sufficient integer sample count for the actual normalized approximate scores, with reciprocal accuracy dependence.

    In the survey: Page 87, the least-squares sketch with approximate leverage scores, its relative-error bound.

    Uses: RelativeLeverageScores, RelativeLeverageLeastSquaresQuality, augmentedDataSpan, lsColumnSpaceBasisMatrix

    Lean statement
    def relativeLeverageLeastSquaresRelativeError : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
          (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1)
          (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α),
          0 < m → 0 < n → 0 < s → 0 ≤ α → 0 < ε → ε < 1 →
          C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε) ≤ (s : ℝ) →
          RelativeLeverageLeastSquaresQuality s A b a α hα ha ε

    Proof published. It depends on 451 theorems of the library.

  • relativeLeverageLeastSquaresSamples

    Original026-samples: the ceiling of a dimension/accuracy/score-tolerance budget gives successful actual outputs, and remains at most twice its scale.

    In the survey: Page 87, the least-squares sketch with approximate leverage scores, its sample count.

    Uses: RelativeLeverageScores, RelativeLeverageLeastSquaresQuality, augmentedDataSpan, lsColumnSpaceBasisMatrix

    Lean statement
    def relativeLeverageLeastSquaresSamples : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
          (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1)
          (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α),
          0 < m → 0 < n → 0 ≤ α → 0 < ε → ε < 1 →
          ∃ s : ℕ,
            s = ⌈C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε)⌉₊ ∧
            0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * (m : ℝ)) / (((1 - α) / (1 + α)) * ε) ∧
            RelativeLeverageLeastSquaresQuality s A b a α hα ha ε

    No proof published.

  • relativeLeverageLeastSquaresSourceRelativeError

    Source-scale relative-error child with a uniformly bounded internal score approximation tolerance. In particular α=min(ε,1/2) is permitted.

    In the survey: Page 87, the least-squares sketch with approximate leverage scores, its relative-error bound at the survey's sample scale.

    Uses: RelativeLeverageScores, RelativeLeverageLeastSquaresQuality, augmentedDataSpan, lsColumnSpaceBasisMatrix

    Lean statement
    def relativeLeverageLeastSquaresSourceRelativeError : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
          (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1)
          (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α),
          0 < m → 0 < n → 0 < s → 0 ≤ α → α ≤ 1 / 2 → 0 < ε → ε < 1 →
          C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε ≤ (s : ℝ) →
          RelativeLeverageLeastSquaresQuality s A b a α hα ha ε

    No proof published.

  • relativeLeverageLeastSquaresSourceSamples

    Source-scale samples child for bounded supplied-score tolerance. Its integer witness depends only on dimensions and residual accuracy.

    In the survey: Page 87, the least-squares sketch with approximate leverage scores, its sample count at the survey's sample scale.

    Uses: RelativeLeverageScores, RelativeLeverageLeastSquaresQuality, augmentedDataSpan, lsColumnSpaceBasisMatrix

    Lean statement
    def relativeLeverageLeastSquaresSourceSamples : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ)
          (a : Fin m → ℝ) (α ε : ℝ) (hα : α < 1)
          (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α),
          0 < m → 0 < n → 0 ≤ α → α ≤ 1 / 2 → 0 < ε → ε < 1 →
          ∃ s : ℕ,
            s = ⌈C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε⌉₊ ∧
            0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * (m : ℝ)) / ε ∧
            RelativeLeverageLeastSquaresQuality s A b a α hα ha ε

    No proof published.

  • IsRelativeLeverageLeastSquaresOutput

    Exact outputs of the literal shared A/b importance-sampling sketch.

    Lean statement
    def IsRelativeLeverageLeastSquaresOutput {m n s : ℕ}
        (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (P : FiniteProbability (Fin m))
        (xHat : RowTrace m s → Fin n → ℝ) : Prop :=
      ∀ samples, IsLeastSquaresMinimizer (rowSampleSketchWithProb s A P.prob samples)
        (rowSampleVectorWithProb P.prob b samples) (xHat samples)

    A definition that statements of this file use.

  • RelativeLeverageLeastSquaresQuality

    Rank-complete quality of the actual supplied-score law, including existence of actual outputs. Rank zero returns0 without dividing by a zero score sum.

    Lean statement
    def RelativeLeverageLeastSquaresQuality {m n : ℕ} (s : ℕ)
        (A : Fin m → Fin n → ℝ) (b : Fin m → ℝ) (a : Fin m → ℝ)
        (α : ℝ) (hα : α < 1) (ha : ∀ _hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
          RelativeLeverageScores (lsColumnSpaceBasisMatrix A) a α)
        (ε : ℝ) : Prop :=
      (Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)) = 0 →
        IsLeastSquaresMinimizer A b (fun _ => 0) ∧
        ∀ xOpt : Fin n → ℝ, IsLeastSquaresMinimizer A b xOpt →
          vecNorm2 (lsResidual A b (fun _ => 0)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)) ∧
      ∀ hd : 0 < Module.finrank ℝ (augmentedDataSpan A (fun _ => 0)),
        let P := relativeLeverageScoreProbability (lsColumnSpaceBasisMatrix A)
          (hasOrthonormalColumns_lsColumnSpaceBasisMatrix A) hd a hα (ha hd)
        (∃ xHat : RowTrace m s → Fin n → ℝ, IsRelativeLeverageLeastSquaresOutput A b P xHat) ∧
        ∀ (xHat : RowTrace m s → Fin n → ℝ) (xOpt : Fin n → ℝ),
          IsRelativeLeverageLeastSquaresOutput A b P xHat → IsLeastSquaresMinimizer A b xOpt →
          (1 / 2 : ℝ) ≤ (P.iid s).eventProb
            {samples | vecNorm2 (lsResidual A b (xHat samples)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}

    A definition that statements of this file use.

Proof-free contract for preservation of represented-subspace rank

RepresentedSubspaceRank.lean · 1 statement, with a published proof

The deterministic rank consequence of successful Eq. (7), CACM 59(6), p. 85. Only the actual represented subspace is claimed to be preserved.

  • representedSubspaceRank

    Successful Eq. (7) preserves the dimension of the represented subspace. The same linear sketch is injective throughout col(U); its application to U has rank d; and it preserves the rank of every matrix spanning exactly col(U). This includes the zero-dimensional case and rank-deficient input matrices.

    In the survey: Equation (7), page 85, its consequence for rank.

    Uses: HasOrthonormalColumns, idMatrix, opNorm2Le, rowSketchGram

    Lean statement
    def representedSubspaceRank : Prop :=
      ∀ (m d t : ℕ) (U : Matrix (Fin m) (Fin d) ℝ)
        (T : Matrix (Fin t) (Fin m) ℝ),
        HasOrthonormalColumns U →
        ∀ ε : ℝ, 0 < ε → ε < 1 →
        opNorm2Le (fun j k => idMatrix d j k - rowSketchGram (T * U) j k) ε →
          (T * U).rank = d ∧
          Set.InjOn T.mulVec (Set.range U.mulVec) ∧
          ∀ (n : ℕ) (A : Matrix (Fin m) (Fin n) ℝ),
            Set.range A.mulVec = Set.range U.mulVec → (T * A).rank = A.rank

    Proof published. It depends on 20 theorems of the library.

Source contracts for norm-squared and leverage sampling

RowSampling.lean · 3 statements, 2 with a published proof

Proof-free statements for equations (4)--(6) of Drineas--Mahoney (2016). The positive denominator in equation (4) excludes the undefined norm-squared distribution of the zero matrix. Equation (6) uses a positive-dimensional orthonormal basis and the paper's normalized leverage probabilities.

  • rowNormDistribution

    Equation (4): norm-squared row probabilities form the stated distribution.

    In the survey: Equation (4).

    Uses: rowSqNormProb, rowSqNormProbDen

    Lean statement
    def rowNormDistribution : Prop :=
      ∀ (m n : ℕ) (A : Fin m → Fin n → ℝ),
        0 < rowSqNormProbDen A →
          (∀ i, 0 ≤ rowSqNormProb A i) ∧
          (∑ i : Fin m, rowSqNormProb A i) = 1 ∧
          ∀ i, rowSqNormProb A i =
            (∑ j : Fin n, A i j ^ 2) /
              (∑ r : Fin m, ∑ j : Fin n, A r j ^ 2)

    Proof published. It depends on 3 theorems of the library.

  • leverageDistribution

    Equation (6): normalized leverage probabilities are squared row norms divided by the dimension, equivalently the diagonal of UUᵀ divided by it.

    In the survey: Equation (6).

    Uses: HasOrthonormalColumns, leverageScoreProb

    Lean statement
    def leverageDistribution : Prop :=
      ∀ (m n : ℕ) (U : Fin m → Fin n → ℝ),
        0 < n → HasOrthonormalColumns U →
          (∀ i, 0 ≤ leverageScoreProb U i) ∧
          (∑ i : Fin m, leverageScoreProb U i) = 1 ∧
          (∀ i, leverageScoreProb U i = (∑ j : Fin n, U i j ^ 2) / (n : ℝ)) ∧
          ∀ i, leverageScoreProb U i = (∑ j : Fin n, U i j * U i j) / (n : ℝ)

    Proof published. It depends on 5 theorems of the library.

  • expectedGramError

    Equation (5) is an expectation bound, as specified by its following prose. The norm on the Gram difference is Frobenius and sampling is with replacement.

    In the survey: Equation (5) and the text after it.

    Uses: FiniteProbability.expectationReal, RowSample, RowTrace, frobNorm, rowGram, rowSampleGram, rowSqNormProbDen, rowSqNormTraceProbability

    Lean statement
    def expectedGramError : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ)
        (hA : 0 < rowSqNormProbDen A),
        0 < s →
          (rowSqNormTraceProbability (steps := s) A hA).expectationReal
            (fun samples =>
              frobNorm (fun j k => rowSampleGram s A samples j k - rowGram A j k)) ≤
            rowSqNormProbDen A / Real.sqrt (s : ℝ)

    No proof published.

Algorithm contracts for Drineas--Mahoney (2016)

SamplingAlgorithms.lean · 5 statements, each with a published proof

Algorithms 1 and 2 use a supplied finite distribution and exactly s independent samples with replacement. Zero-probability outcomes are excluded almost surely. The unbiasedness claims require the distribution to cover every nonzero entry or row; without this support condition those claims are false. Algorithm 3 specifies products once its random preprocessing matrices have been drawn. As in the source meta-algorithm, these preprocessing matrices preserve dimensions.

Column sampling, output sparsity, and the explicit Eq. (5) Markov consequence

SamplingConsequences.lean · 3 statements, each with a published proof

These contracts retain separate selected child claims. The Gram tail has the visible confidence-dependent threshold dictated by Markov's inequality.

  • columnSamplingAlgorithm

    Algorithm 2 transposed back samples columns, retaining one column per trial.

    In the survey: Algorithm 2, applied to columns.

    Uses: FiniteProbability, FiniteProbability.eventProb, FiniteProbability.iid, FiniteProbability.prob, rowSampleSketchWithProb

    Lean statement
    def columnSamplingAlgorithm : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ)
        (P : FiniteProbability (Fin n)), 0 < s →
        (∀ ω, (P.iid s).prob ω = ∏ t, P.prob (ω t)) ∧
        (P.iid s).eventProb {ω | ∀ t, 0 < P.prob (ω t)} = 1 ∧
        ∀ (ω : Fin s → Fin n) i t,
          (Matrix.transpose (rowSampleSketchWithProb s (Matrix.transpose A) P.prob ω)) i t =
            (1 / Real.sqrt ((s : ℝ) * P.prob (ω t))) * A i (ω t)

    Proof published. It depends on 4 theorems of the library.

  • elementwiseSamplingSparsity

    At most s distinct entries of the zero-initialized Algorithm 1 output are nonzero. Repeated samples and sampled zero entries can make this strict.

    In the survey: Algorithm 1, the number of nonzero entries of its output.

    Uses: ElementwiseTrace, FiniteProbability, FiniteProbability.prob, elementwiseTraceSketchWithProb

    Lean statement
    def elementwiseSamplingSparsity : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ)
        (P : FiniteProbability (Fin m × Fin n)), 0 < s →
        ∀ (ω : ElementwiseTrace m n s), (∀ t, 0 < P.prob (ω t)) →
          (Finset.univ.filter (fun ij : Fin m × Fin n =>
            elementwiseTraceSketchWithProb s A (fun _ _ => 0)
              (fun i j => P.prob (i,j)) ω ij.1 ij.2 ≠ 0)).card ≤ s

    Proof published. It depends on no theorems of the library.

  • gramErrorHighProbability

    The direct high-probability consequence of the unsquared Eq. (5) expectation: the threshold is enlarged by 1/δ, with the literal nonzero-input norm law.

    In the survey: Equation (5), as a bound that holds with high probability.

    Uses: FiniteProbability.eventProb, RowSample, RowTrace, frobNorm, rowGram, rowSampleGram, rowSqNormProbDen, rowSqNormTraceProbability

    Lean statement
    def gramErrorHighProbability : Prop :=
      ∀ (m n s : ℕ) (A : Fin m → Fin n → ℝ)
        (hA : 0 < rowSqNormProbDen A), 0 < s →
        ∀ δ : ℝ, 0 < δ → δ < 1 →
          1 - δ ≤ (rowSqNormTraceProbability (steps := s) A hA).eventProb
            {ω | frobNorm (fun j k => rowSampleGram s A ω j k - rowGram A j k) ≤
              rowSqNormProbDen A / (δ * Real.sqrt (s : ℝ))}

    Proof published. It depends on 35 theorems of the library.

Total norm-squared row-sampling extension contracts

TotalRowSampling.lean · 3 statements, 1 with a published proof

The printed Eq4 distribution has no zero-input normalization rule. These contracts explicitly extend it by a deterministic none outcome with zero sketch and Gram output. On nonzero inputs they agree with the literal original iid sampler, and Eq5's expected error formula then extends to every finite matrix. This is an explicit mathematical convention, not a claim that the source printed a zero-input branch. Existing nonzero source contracts remain unchanged.

Quantitative children of the joint Walsh least-squares construction

WalshLeastSquaresRate.lean · 2 statements, each with a published proof

The source's rough sample scale is represented by existence of a universal constant. Success1/2 is a concrete sufficient interpretation of qualitative positive success probability. Neither contract asserts fast execution or an implicit extension to row dimensions other than powers of two.

  • walshUniformLeastSquaresRelativeError

    In plain words: There is a constant C ≥ 1 such that, for A with 2^q rows and n columns, 0 < ε < 1, and a sketch by random signs, a Walsh–Hadamard transform and at least C n log(2 · 2^q)/ε rows sampled uniformly, every exact solution of the sketched problem has a residual at most (1 + ε) times the least residual, with probability at least 1/2. The statement asserts that some constant exists, and the proof takes C = 4096.

    Original027-relative-error: every sufficient integer budget controls the original unsquared residual for every exact sketch minimizer. Actual outputs exist; no minimizer, embedding or final quality is postulated as source input.

    In the survey: Page 87, the least-squares sketch with a randomized Hadamard transform, its relative-error bound.

    Uses: FiniteProbability.eventProb, IsLeastSquaresMinimizer, RademacherTrace, RowSample, RowTrace, IsWalshLeastSquaresOutput, lsResidual, signedHadamardUniformRowTraceProbability, vecNorm2

    Lean statement
    def walshUniformLeastSquaresRelativeError : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (q n s : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ)
          (hm : 0 < 2 ^ q) (ε : ℝ),
          0 < n → 0 < s → 0 < ε → ε < 1 →
          C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε ≤ (s : ℝ) →
          (∃ xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ,
            IsWalshLeastSquaresOutput A b xHat) ∧
          ∀ (xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ)
            (xOpt : Fin n → ℝ),
            IsWalshLeastSquaresOutput A b xHat → IsLeastSquaresMinimizer A b xOpt →
            (1 / 2 : ℝ) ≤ (signedHadamardUniformRowTraceProbability (m := 2 ^ q) (s := s) hm).eventProb
              {z | vecNorm2 (lsResidual A b (xHat z)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}

    Proof published. It depends on 589 theorems of the library.

  • walshUniformLeastSquaresSamples

    Original027-samples: a dimension/accuracy-only integer budget at the source scale comes with actual joint sketch outputs and the fixed-probability original residual guarantee. This asserts algorithm success, not just an arithmetic count.

    In the survey: Page 87, the least-squares sketch with a randomized Hadamard transform, its sample count.

    Uses: FiniteProbability.eventProb, IsLeastSquaresMinimizer, RademacherTrace, RowSample, RowTrace, IsWalshLeastSquaresOutput, lsResidual, signedHadamardUniformRowTraceProbability, vecNorm2

    Lean statement
    def walshUniformLeastSquaresSamples : Prop :=
      ∃ C : ℝ, 1 ≤ C ∧
        ∀ (q n : ℕ) (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ)
          (hm : 0 < 2 ^ q) (ε : ℝ), 0 < n → 0 < ε → ε < 1 →
          ∃ s : ℕ, s = ⌈C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε⌉₊ ∧
            0 < s ∧ (s : ℝ) ≤ 2 * C * (n : ℝ) * Real.log (2 * ((2 ^ q : ℕ) : ℝ)) / ε ∧
          ∃ xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ,
            IsWalshLeastSquaresOutput A b xHat ∧
            ∀ xOpt : Fin n → ℝ, IsLeastSquaresMinimizer A b xOpt →
              (1 / 2 : ℝ) ≤ (signedHadamardUniformRowTraceProbability (m := 2 ^ q) (s := s) hm).eventProb
                {z | vecNorm2 (lsResidual A b (xHat z)) ≤ (1 + ε) * vecNorm2 (lsResidual A b xOpt)}

    Proof published. It depends on 589 theorems of the library.

  • IsWalshLeastSquaresOutput

    Actual exact minimizers of the common HD/uniform-row sketch of A and b.

    Lean statement
    def IsWalshLeastSquaresOutput {q n s : ℕ}
        (A : Fin (2 ^ q) → Fin n → ℝ) (b : Fin (2 ^ q) → ℝ)
        (xHat : RademacherTrace (2 ^ q) × RowTrace (2 ^ q) s → Fin n → ℝ) : Prop :=
      ∀ ω samples,
        let T := matMul (2 ^ q) (leastSquaresWalshMatrix q) (diagMatrix (rademacherSignVector ω))
        IsLeastSquaresMinimizer
          (rowSampleSketchWithProb s (preconditionRows T A) uniformRowProb samples)
          (rowSampleVectorWithProb uniformRowProb (matMulVec (2 ^ q) T b) samples)
          (xHat (ω, samples))

    A definition that statements of this file use.