We present low complexity, quickly converging robust adaptive beamformers that combine robust Capon beamformer (RCB) methods and data-adaptive Krylov subspace dimensionality reduction techniques. We extend a recently proposed reduced-dimension RCB framework, which ensures proper combination of RCBs with any form of dimensionality reduction that can be expressed using a full-rank dimension reducing transform, providing new results for data-adaptive dimensionality reduction. We consider Krylov subspace methods computed with the Powers-of-R (PoR) and Conjugate Gradient (CG) techniques, illustrating how a fast CG-based algorithm can be formed by beneficially exploiting that the CG-algorithm diagonalizes the reduced-dimension covariance. Our simulations show the benefits of the proposed approaches.