Finite-candidate information design

Assume AC for the library KL/EIG convention. Input a prior covariance $C\in {\mathbb{R}}^{n\times n}$ with $n\ge 1$ symmetric positive semidefinite, a finite ordered list of raw candidate records $(A_d,{\mathrm{\Gamma }}_d,c_d{)}_{d=1}^N$, and a real budget $B$. Each stored $A_d$ and ${\mathrm{\Gamma }}_d$ is a finite real matrix, with its dimensions part of the input, and each declared cost $c_d$ is finite and real. A candidate is dimension-valid when $A_d$ has at least one row and exactly $n$ columns and ${\mathrm{\Gamma }}_d$ is a symmetric square matrix whose dimension equals the row count of $A_d$; for a dimension-valid candidate write that common positive dimension as $m_d$. The prior mean is immaterial to the score.

Interpret each admissible candidate $d$ (dimension-valid with ${\mathrm{\Gamma }}_d$ positive definite) as a separate singleton-design dominated inverse experiment with prior $\theta \sim N_n(m_0,C)$ for any $m_0\in {\mathbb{R}}^n$, observation space ${\mathbb{R}}^{m_d}$ with Lebesgue measure, and observation $Y_d=A_d\theta +{\eta }_d$, where ${\eta }_d\sim N_{m_d}(0,{\mathrm{\Gamma }}_d)$ is independent of $\theta$. Here $\mathrm{EIG}(d)$ is the expected information gain from the preceding definition for that singleton experiment. Different candidates may have different $m_d$ because each is evaluated on its own observation space. The score is independent of $m_0$.

In exact-real arithmetic, process the list in order. Mark a candidate inadmissible if it is not dimension-valid or if its noise covariance ${\mathrm{\Gamma }}_d$ is not positive definite. For each remaining candidate with $c_d\le B$, compute the Cholesky factor ${\mathrm{\Gamma }}_d=L_d{L}_d^T$ with positive diagonal, solve $L_d{V}_d=A_d$ by forward substitution, and form the symmetric positive-semidefinite matrix $Z_d=V_{d}C{V}_d^T$. Set $H_d=I_{m_d}+Z_d$ and compute its Cholesky factor $H_d=R_d{R}_d^T$. Assign the utility $U_d={\sum }_{j=1}^{m_d}\log (R_d{)}_{jj}-c_d=\frac{1}{2}\log \det (H_d)-c_d\mathrm{.}$ Initialize the stored best candidate as unset. For each admissible candidate meeting the budget, set it if unset; otherwise replace it exactly when the new utility is strictly greater than the stored utility. After the scan, return the stored candidate. This update rule preserves the first index in any tie. If every candidate is inadmissible, return all-inadmissible; if at least one candidate is admissible but none meets the budget, return budget-exhausted.

In floating-point mode, treat each finite stored floating-point matrix entry, cost, budget, and tolerance as the exact real number represented by that value; no uncertainty in these input data is included. Use failure-aware Cholesky and triangular-solve procedures, and take a certificate provider as part of the floating-point input. Each provider result is a finite, independently checkable certificate; if the provider cannot certify a required fact, it returns unresolved.

Process the candidates in list order. Test dimensions and symmetry exactly, marking a dimension-invalid candidate inadmissible. For each dimension-valid noise matrix ${\mathrm{\Gamma }}_d$, call CertifyPositiveDefiniteness(\Gamma_d). It returns positive-definite only with a checkable positive-definiteness certificate, not-positive-definite only with a checkable certificate, or unresolved. For example, an exact factorization ${\mathrm{\Gamma }}_d=L{L}^T$ with $L$ lower triangular and positive diagonal certifies positive definiteness, while a nonzero vector $v$ with $v^T{\mathrm{\Gamma }}_{d}v\le 0$ certifies that it is not positive definite. A failed rounded Cholesky factorization is not a certificate of non-positive-definiteness. If any required status is unresolved, return numerically-unresolved. After all statuses are certified, return all-inadmissible if none is admissible. Compare each admissible stored cost to the stored budget exactly; if none meets it, return budget-exhausted.

For each feasible candidate $d$ in inherited order, call CertifyScore(d). It first runs failure-aware rounded Cholesky on ${\mathrm{\Gamma }}_d$ and, on success, failure-aware forward substitution on each column of $A_d$ in order; any operation failure or unmet range hypothesis returns unresolved. After forming a certified positive-semidefinite ${\widehat{Z}}_d$, it forms a stored matrix ${\widehat{H}}_d$ and certifies both that ${\widehat{H}}_d$ is symmetric positive definite and that $\mathrm{\parallel }{\widehat{H}}_d-(I_{m_d}+{\widehat{Z}}_d){\mathrm{\parallel }}_2\le {\sigma }_d$ for a rational bound ${\sigma }_d\ge 0$. It then runs failure-aware rounded Cholesky on ${\widehat{H}}_d$; a failed definiteness check, factorization, or formation bound returns unresolved. The call then returns either certified with finite stored values ${\widehat{U}}_d$, ${\widehat{Z}}_d$, and ${\widehat{R}}_d$, nonnegative rational upper bounds ${\delta }_d,{\rho }_d,{\lambda }_d$, and certificates for all of the following, or unresolved:

• ${\widehat{Z}}_d$ is symmetric positive semidefinite and $\mathrm{\parallel }{\widehat{Z}}_d-Z_d{\mathrm{\parallel }}_2\le {\delta }_d$, where $Z_d$ uses the exact Cholesky factor of the represented ${\mathrm{\Gamma }}_d$. This bound includes rounding in forming the Cholesky factor and triangular solve for ${\mathrm{\Gamma }}_d$, the covariance square root, and the matrix products.
• ${\widehat{R}}_d$ is a successful lower-triangular Cholesky factor with positive diagonal. If ${\tilde{\rho }}_d$ is a certified upper bound for $\mathrm{\parallel }{\widehat{R}}_d{\widehat{R}}_d^T-{\widehat{H}}_d{\mathrm{\parallel }}_2$, choose a rational ${\rho }_d\ge {\tilde{\rho }}_d+{\sigma }_d$ with ${\rho }_d<1$; then $\mathrm{\parallel }{\widehat{R}}_d{\widehat{R}}_d^T-(I_{m_d}+{\widehat{Z}}_d){\mathrm{\parallel }}_2\le {\rho }_d$.
• $\mid {\widehat{U}}_d-(\frac{1}{2}\log \det ({\widehat{R}}_d{\widehat{R}}_d^T)-c_d)\mid \le {\lambda }_d$. Evaluate the exact expression as ${\sum }_j\log (({\widehat{R}}_d{)}_{jj})-c_d$ using the triangular determinant identity; ${\lambda }_d$ covers rounded logarithms, their summation, and cost evaluation.

If any CertifyScore call returns unresolved, return numerically-unresolved immediately, without a candidate or optimum claim. Continue to interval comparisons only when every feasible candidate has a certified result.

The matrix radius may be certified by the published information-matrix perturbation bound in its single-design, unit-weight $W=I_n$ case. Factor $C$ as $C^{1\mathrm{/}2}{C}^{1\mathrm{/}2}$ and set $J_d=C^{1\mathrm{/}2}{V}_d^T$; for a computed solve ${\widehat{V}}_d$, set ${\widehat{J}}_d=C^{1\mathrm{/}2}{\widehat{V}}_d^T$. Then $Z_d=J_d^T{J}_d$ and ${\widehat{Z}}_d={\widehat{J}}_d^T{\widehat{J}}_d$. The lemma's finite-design hypotheses hold for the one-point sensitivity maps $z\mapsto J_{d}z$ and $z\mapsto {\widehat{J}}_{d}z$ from ${\mathbb{R}}^{m_d}$ to ${\mathbb{R}}^n$, with weight $W=I_n$ and design weight $1$. If $\mathrm{\parallel }{J}_d{\mathrm{\parallel }}_2\le K_d$ and $\mathrm{\parallel }{\widehat{J}}_d-J_d{\mathrm{\parallel }}_2\le {\eta }_d$, then ${\delta }_d$ may be any verified bound at least $2K_d{\eta }_d+{\eta }_d^2$, enlarged by any separate matrix-formation residual. A rounded triangular-substitution bound may be used only after checking its $(m_d+3)u<1$ and normal-range, finite-operation hypotheses for every right-hand side. Convert its backward-error bound to the required forward matrix bound using verified conditioning; a solve backward-error bound alone does not certify ${\eta }_d$. For the published rounded-Cholesky normwise bound, verify success and its operationwise model, put $q=20m_d+20$ and $g=qu\mathrm{/}(1-qu)$, and check $qu<1\mathrm{/}5$ before using $100g\mathrm{\parallel }{\widehat{R}}_d{\mathrm{\parallel }}_F^2$ as a residual bound; if using its relative bound, also check $100\sqrt{m_d}g\le 1\mathrm{/}2$. The log-determinant perturbation bound is applied on the two symmetric matrix segments with eigenvalue floors $1$ and $1-{\rho }_d$. A missing or failed certificate returns numerically-unresolved and no optimum claim.

Set ${\epsilon }_d=\frac{m_d}{2}({\delta }_d+\frac{{\rho }_d}{1-{\rho }_d})+{\lambda }_d$ and form the exact rational interval $[{\widehat{U}}_d-{\epsilon }_d,{\widehat{U}}_d+{\epsilon }_d]$. Given a finite nonnegative stored tolerance $\tau$, compute $M={\max }_{d\text{ feasible}}{\widehat{U}}_d$ and return the first feasible candidate with ${\widehat{U}}_d\ge M-\tau$. Certify the comparisons exactly on the represented floating-point values and rational bounds; if any comparison needed for this branch or for its interval certificate is undecided, return numerically-unresolved. The returned candidate's true utility gap is at most $\tau +2{\max }_d{\epsilon }_d$. If its lower interval endpoint exceeds every earlier candidate's upper endpoint and is at least every later candidate's upper endpoint, certify it as the first exact maximizer. The algorithm makes no bit-complexity claim for exact-real comparisons.

The exact linear-Gaussian EIG is a log determinant, including singular state covariance.

Each candidate's Gaussian model is a singleton design in the dominated-experiment convention.

EIG is the extended prior-predictive posterior-to-prior KL integral.

A positive-semidefinite prior covariance has a positive-semidefinite square root for the Gram representation.

Cholesky factors are lower triangular with positive diagonal.

Every symmetric positive-definite matrix has a unique positive-diagonal Cholesky factor.

Cholesky triangular solves evaluate positive-definite systems without forming an inverse.

The determinant of a triangular matrix is the product of its diagonal entries.

The log-determinant score uses the usual determinant of a finite square matrix.

The logarithm in the score is the natural logarithm.

The floating-point factorization reports success or its first pivot/operation failure.

Successful rounded triangular solves have the stated componentwise backward error.

Successful rounded Cholesky gives the stated factorization residual bounds.

Uniform factor and solve errors imply the stated information-matrix perturbation bound.

A one-point approximate design with a linear sensitivity map and weight matrix $W=I$ satisfies the finite-design setting.

A positive eigenvalue floor controls log-determinant perturbation.

Rasmussen and Williams, Chapter 2, Algorithm 2.1 and equation (2.30)

Chaloner and Verdinelli, §2.2

This procedure is for the specified finite linear-Gaussian candidates. A Monte Carlo estimate of nonlinear EIG is a different procedure and inherits no exact finite optimum guarantee from this algorithm.

Any solve-error certificate must convert triangular-solve backward error to the required matrix error using a verified conditioning bound. Backward error alone is not a forward-error bound.

The exact log-determinant formula applies to the linear-Gaussian model stated there.

A rounded triangular-solve certificate is a backward-error statement and requires conditioning to produce a forward bound.

MacKay, §6.1, model-correctness caveat