  We study infinite matrices $A$ indexed by a discrete group $G$ that are
dominated by a convolution operator in the sense that $|(Ac)(x)| \leq (a \ast
|c|)(x)$ for $x\in G$ and some $a\in \ell ^1(G)$. This class of
"convolution-dominated" matrices forms a Banach-*-algebra contained in the
algebra of bounded operators on $\ell ^2(G)$. Our main result shows that the
inverse of a convolution-dominated matrix is again convolution-dominated,
provided that $G$ is amenable and rigidly symmetric. For abelian groups this
result goes back to Gohberg, Baskakov, and others, for non-abelian groups
completely different techniques are required, such as generalized
  $L^1$-algebras and the symmetry of group algebras.
