Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any $n \times n$ zero-one matrix in expected time $\text{exp} \left[ -\Omega\left( \frac{n^{1/3}}{2\ln n}\right) \right]2^n$. Building on their work, we show that for any constant $C>0$ there is a constant $\eps > 0$ such that the permanent of any $n \times n$ (real or complex) matrix with at most $Cn$ nonzero entries can be computed in deterministic time $(2 - \eps)^n$ and space $O(n).$ This improves on the $\Omega(2^n)$ runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.