Antidot lattices fabricated from permalloy thin films have been investigated by all-electrical spin-wave spectroscopy and Brillouin light scattering. Periodic arrays of 120-nm-diameter nanoholes have been prepared using focused ion beam etching. The periodicity of the square lattices was varied from 300 to 4000 nm. By applying an in-plane field of 40 mT, we discover surprisingly large spin-wave velocities of up to 6 km/s for a periodicity <400 nm. Using micromagnetic modeling and the further-developed plane wave method, we show that edge excitations at neighboring holes couple and form an allowed miniband supporting fast spin waves. By varying the orientation of the magnetic field we control the miniband characteristics. The coupling of edge modes opens interesting perspectives for magnonic crystals. © 2011 American Physical Society.