Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass
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.

The D-equivalence violation bounds the finite-budget design's log-determinant gap

Statement

Let X be a finite nonempty candidate set, let p≥1, and let ξ be any returned nonsingular approximate design from Finite-budget multiplicative update for approximate D-optimal design. Put M=M(ξ) and sx=fxTM−1fx,v=max⁡x∈Xsx−p. Then v≥0, every nonsingular approximate competitor η satisfies log⁡det⁡M(η)−log⁡det⁡M(ξ)≤v, and v=0 if and only if ξ is D-optimal among nonsingular approximate designs.

Facts & Assumptions

Given: A finite candidate set X, feature vectors fx∈Rp, p≥1, and a nonsingular approximate design ξ returned by the stated algorithm.

[F1]

Finite-budget multiplicative update for approximate D-optimal design: M(ξ)=∑xξxfxfxT, the finite sensitivity is sx=fxTM(ξ)−1fx, and the returned violation is v=max⁡xsx−p.

[F2]

Approximate designs and linear-model optimality criteria: approximate design weights are nonnegative and sum to one; nonsingular means M(ξ) is positive definite; D-optimality maximizes log⁡det⁡M(ξ) over nonsingular designs.

[F3]

The log determinant is concave on positive-definite matrices: log⁡det⁡ is concave along every segment of positive-definite matrices.

[F5]
[F6]

Equivalence criterion for D-optimal approximate designs: a nonsingular approximate design is D-optimal exactly when fxTM(ξ)−1fx≤p for every candidate x.

Proof

technique · direct
1.1F1F2F5givenalgebra

By [F1] and [F5], ∑xξxsx=∑xξxtr⁡(M−1fxfxT)=tr⁡ ⁣(M−1∑xξxfxfxT)=tr⁡(M−1M)=tr⁡(Ip)=p. The first rank-one trace identity follows by expanding the diagonal sum: tr⁡(M−1fxfxT)=∑i,j(M−1)ij(fx)j(fx)i=fxTM−1fx. Since the ξx are nonnegative and sum to one, their weighted average of the sx is at most their maximum. The displayed equality therefore gives max⁡xsx≥p and v≥0.

1.2F2F3F4givenalgebra

Let η be any nonsingular approximate competitor and put N=M(η) and Mt=(1−t)M+tN. The segment is positive definite because for each nonzero u, uTMtu=(1−t)uTMu+tuTNu>0. Define g(t)=log⁡det⁡Mt. By [F3], g is concave, and [F4] gives g′(0)=tr⁡(M−1(N−M)). For 0<s<1, concavity gives g(s)≥(1−s)g(0)+sg(1), hence g(1)−g(0)≤(g(s)−g(0))/s. Letting s↓0 and using the right derivative g′(0) proves log⁡det⁡N−log⁡det⁡M≤tr⁡(M−1(N−M)).

2.1step 1.1step 1.2F2F5algebra

Expand N=∑xηxfxfxT and M=∑xξxfxfxT. By the rank-one trace identity proved in step 1.1, tr⁡(M−1N)=∑xηxsx and tr⁡(M−1M)=p. Since η is an approximate design, ∑xηxsx≤max⁡xsx=p+v. Thus step 1.2 yields log⁡det⁡M(η)−log⁡det⁡M(ξ)≤v.

3.1step 1.1F6algebra∎

If v=0, then sx≤p for every x, so [F6] makes ξ D-optimal. Conversely, if ξ is D-optimal, [F6] gives sx≤p for every x; step 1.1 says their ξ-weighted average equals p, so their maximum is exactly p and v=0. This proves both directions.

Depends on

Used by

Dependency tree · two levels

47 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