Efficient computer implementations of the GW approximation must approximate a numerically challenging frequency integral; the integral can be performed analytically, but doing so leads to an expensive implementation whose computational cost scales as O(N6), where N is the size of the system. Here, we introduce a new formulation of the full-frequency GW approximation by exactly recasting it as an eigenvalue problem in an expanded space. This new formulation (1) avoids the use of time or frequency grids, (2) naturally obviates the need for the common “diagonal” approximation, (3) enables common iterative eigensolvers that reduce the canonical scaling to O(N5), and (4) enables a density-fitted implementation that reduces the scaling to O(N4). We numerically verify these scaling behaviors and test a variety of approximations that are motivated by this new formulation. The new formulation is found to be competitive with conventional O(N4) methods based on analytic continuation or contour deformation. In this new formulation, the relation of the GW approximation to configuration interaction, coupled-cluster theory, and the algebraic diagrammatic construction is made especially apparent, providing a new direction for improvements to the GW approximation.