LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Bottom-up factor-sum recompression has the reported rank and Frobenius error bound

Statement

Use Bottom-up low-rank recompression of block contributions on a finite factor-sum tree for one admissible block over $F \in {R, C}$ , with exact arithmetic, rank cap $k \geq 1$ , node tolerances $θ_{v} \geq 0$ , and $\sum_{v} θ_{v} \leq δ_{b}$ . Let $T_{v}$ be the subtree rooted at $v$ , and let $M_{v}$ be the sum of its exact leaf contributions. Whenever all calls in $T_{v}$ succeed, the returned factors represent a matrix ${\hat{M}}_{v}$ of rank at most $k$ , and the reported bound satisfies $∥ M_{v} - {\hat{M}}_{v} ∥_{F} \leq e_{v} = \sum_{w \in T_{v}} ρ_{w} \leq \sum_{w \in T_{v}} θ_{w} .$ In particular, if the routine succeeds at the root, $rank ({\hat{M}}_{r o o t}) \leq k, ∥ M_{r o o t} - {\hat{M}}_{r o o t} ∥_{F} \leq e_{r o o t} = \sum_{w} ρ_{w} \leq \sum_{w} θ_{w} \leq δ_{b} .$ Here $ρ_{w}$ is the exact discarded-tail norm returned at node $w$ . A tolerance-not-met status at a node only means this chosen tree and these assigned local budgets did not produce the requested certificate; it does not assert that no rank- $k$ approximation of the exact full sum meets $δ_{b}$ .

Facts & Assumptions

Given: A finite factor-sum tree for one admissible block, a cap $k$ , nonnegative local tolerances, and exact arithmetic.

[F1]

Core-SVD recompression with rank and error tolerances: on success, recompresses the supplied factor product and returns the exact discarded singular-value tail $ρ_{v}$ with $ρ_{v} \leq θ_{v}$ .

[F2]

Core-SVD recompression is best at the declared Frobenius tolerance: the returned core-SVD factors represent the truncated singular expansion, and their Frobenius residual is exactly the reported tail $ρ_{v}$ .

[F3]

Finite tensor arrays and the Frobenius inner product: the Frobenius norm is the Euclidean norm of the finite list of matrix entries, with inner product $⟨ X, Y ⟩_{F} = \sum_{i, j} \overline{X_{i j}} Y_{i j}$ .

[F4]

Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ in a real or complex inner-product space; together with [F3] this gives the Frobenius triangle inequality.

Proof

Every successful node call uses $k_{b} = \min (k, ∣ τ ∣, ∣ σ ∣)$ and returns a truncated singular expansion of rank at most $k_{b} \leq k$ , by [F1] and [F2]. Clipping the cap changes no feasible matrix rank: every matrix of the block dimensions already has rank at most $\min (∣ τ ∣, ∣ σ ∣)$ . The following two steps give the unchanged error induction.

1.1givenF1F2

At a leaf $v$ , the routine compresses its exact contribution $M_{v}$ ; by [F1] and [F2], $∥ M_{v} - {\hat{M}}_{v} ∥_{F} = ρ_{v} = e_{v} \leq θ_{v}$ .

2.1givenF1F2F3F4step 1.1inductionalgebra∎

Suppose $v$ is internal with children $v_{1}, v_{2}$ . Their exact targets add to $M_{v}$ , and their returned approximations add to the matrix $Z_{v}$ supplied to the core-SVD call. The Frobenius triangle inequality from [F3,F4] gives $∥ M_{v} - Z_{v} ∥_{F} \leq e_{v_{1}} + e_{v_{2}}$ . By [F1,F2], $∥ Z_{v} - {\hat{M}}_{v} ∥_{F} = ρ_{v}$ , hence $∥ M_{v} - {\hat{M}}_{v} ∥_{F} \leq e_{v_{1}} + e_{v_{2}} + ρ_{v} = e_{v}$ . Step 1.1 is the leaf base case; induction over the finite tree proves the root error bound. The recurrence for $e_{v}$ gives $e_{r o o t} = \sum_{v \in T} ρ_{v} \leq \sum_{v \in T} θ_{v} \leq δ_{b}$ .

Depends on

Used by

Blockwise Frobenius errors propagate by disjoint block sums Theorem

Cited to discharge well-definedness by Bottom-up low-rank recompression of block contributions.

Dependency tree · two levels

16 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch, Hierarchical Matrices, MiS Lecture Note 21 (2003; revised June 2006), §§6.2, 7.1–7.2 (standard reference, not scraped)
Ralf Hiptmair, AdvNumCSE Lecture Document, Chapter 2, “Local Low-Rank Compression of Non-Local Operators” (ETH Zürich, AT’23), §§2.4.2–2.4.3 (standard reference, not scraped)