4.1 The potential and the verifier

Definition 4.1 The lower potential and verifier

✓

Let \(\iota \) be a finite set, let \(A \in \mathbb {C}^{\iota \times \iota }\) be positive definite, and let \(\delta {\gt} 0\) with \(A - \delta \cdot 1\) positive definite. The lower potential of \(A\) is \(\Phi (A) = \operatorname {Tr}A^{-1}\). With \(Z = (A - \delta \cdot 1)^{-1}\), the lower verifier at \(v \in \mathbb {C}^{\iota }\) is

\[ L_A^{\delta }(v) = \frac{v^* Z^2 v}{\Phi (A - \delta \cdot 1) - \Phi (A)} - v^* Z v . \]

The lower potential is large when \(A\) has a small eigenvalue. Before each step \(A\) is shrunk by \(\delta \cdot 1\), which raises the potential by an amount that is computed exactly, and that amount is the budget one new sampling point is allowed to consume. The verifier decides pointwise, without recomputing any inverse, whether a candidate point stays within that budget. A bound on the potential is a bound on the matrix, \(\Phi (A)^{-1} \cdot 1 \preceq A\) (Lemma 2.7(a)). The upper potential \(\Psi _J(B) = \operatorname {Tr}(J B^{-1})\) and its verifier play the same role for the second family (Definition 5.1).

Lemma 4.2 How the lower potential changes

✓

Let \(\iota \) be a finite set.

(a) Let \(A \in \mathbb {C}^{\iota \times \iota }\) be positive definite and let \(\delta {\gt} 0\) with \(A - \delta \cdot 1\) positive definite. Then

\[ \Phi (A - \delta \cdot 1) - \Phi (A) = \delta \, \operatorname {Tr}\bigl( (A - \delta \cdot 1)^{-1} A^{-1} \bigr) {\gt} 0 . \]

(b) Let \(N \in \mathbb {C}^{\iota \times \iota }\) be positive definite, \(v \in \mathbb {C}^{\iota }\) and \(w \geq 0\). Then

\[ \Phi \bigl( N + w \, v v^* \bigr) = \Phi (N) - \frac{w}{1 + w \, v^* N^{-1} v} \, v^* N^{-2} v . \]

Proof ▼

(a) The identity is the resolvent identity \(X^{-1} - Y^{-1} = X^{-1} (Y - X) Y^{-1}\) for the matrices \(X = A - \delta \cdot 1\) and \(Y = A\), whose difference is \(\delta \cdot 1\). The sign is Lemma 2.3(a) applied to the product of two positive definite matrices.

(b) Insert the Sherman–Morrison formula of Lemma 2.8(a) and take traces.

Lemma 4.3 Barrier lemma for the lower potential

✓

Let \(\iota \) be a finite set, let \(A \in \mathbb {C}^{\iota \times \iota }\) be positive definite, let \(0 {\lt} \delta {\lt} \Phi (A)^{-1}\) and \(v \in \mathbb {C}^{\iota }\), and let \(w {\gt} 0\) satisfy \(1/w \leq L_A^{\delta }(v)\). Then \(A - \delta \cdot 1 + w \, v v^*\) is positive definite and

\[ \Phi \bigl( A - \delta \cdot 1 + w \, v v^* \bigr) \leq \Phi (A). \]

Proof ▼

The matrix \(A - \delta \cdot 1\) is positive definite by Lemma 2.7(b), and adding \(w \, v v^*\) keeps it so by Lemma 2.8(b). The closed form of Lemma 4.2(b) for \(N = A - \delta \cdot 1\), together with the positive gain of Lemma 4.2(a), reduces the inequality to one between real numbers, which is the hypothesis \(1/w \leq L_A^{\delta }(v)\) multiplied out.