Essentially, the self-improvement lemma says the
following: suppose that (a) the provers pass the test with probability
\(1 - \varepsilon \) , and (b) there is a complete measurement \(G_{g}\)  whose
outcomes are codewords \(g \in \mathcal {C}^{\otimes m}\)  that has
consistency error \(\nu \) : that is, \(G\)  always returns an outcome, but
has probability \(\nu \)  of producing an outcome \(g\)  that disagrees with the points measurement \(A^u_a\)  at a
random point \(u\) . Then there exists an
“improved” submeasurement \(H_{h}\)  with consistency error \(\zeta \) 
depending only on \(\varepsilon \) , and with completeness error
(i.e. probability of not producing an outcome at all) of \(\nu +\zeta \) . Essentially, this lemma says we can always “reset” the
consistency error of any measurement we construct at intermediate
points in the analysis to a universal
function \(\zeta \)  depending only on the provers' success in the test,
at the cost of introducing some amount completeness error. Intuitively, one may
think of the action of the lemma as correcting \(G\)  on the portions of
Hilbert space where it is only mildly corrupted, while “cutting out” the
portions of Hilbert space where \(G\)  is too corrupted to be
correctable. In some sense, this lemma is the quantum analogue of the
idea of identifying “good” and “bad” random seeds in the classical
randomized case. The proof of the lemma uses a version of semidefinite programming duality
together with the combinatorial facts used in [1]}.
