  We present a new first-principles linear-response theory of changes due to
perturbations in the quasiparticle self-energy operator within the $GW$ method.
This approach, named $GW$ perturbation theory ($GW$PT), is applied to calculate
the electron-phonon ($e$-ph) interactions with the full inclusion of the $GW$
non-local, energy-dependent self-energy effects, going beyond
density-functional perturbation theory. Avoiding limitations of the
frozen-phonon technique, $GW$PT gives access to $e$-ph matrix elements at the
$GW$ level for all phonons and scattering processes, and the computational cost
scales linearly with the number of phonon modes (wavevectors and branches)
investigated. We demonstrate the capabilities of $GW$PT by studying the $e$-ph
coupling and superconductivity in Ba$_{0.6}$K$_{0.4}$BiO$_3$. We show that
many-electron correlations significantly enhance the $e$-ph interactions for
states near the Fermi surface, and explain the observed high superconductivity
transition temperature of Ba$_{0.6}$K$_{0.4}$BiO$_3$ as well as its doping
dependence.
