In this work we prove a high dimensional analogue of the beloved Goldreich-Levin theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function $f:\mathbb{Z}_q^m\rightarrow\mathbb{Z}_q^n$ such that ${\rm Prob}_{{\bf x}\sim\mathbb{Z}_q^m}\bigl[f({\bf x})={\bf Ax}\bigr]\geq\varepsilon$ for some ${\bf A}\in\mathbb{Z}_q^{n\times m}$ and $\varepsilon>0$, recover ${\bf A}$ (or a list of all such matrices). We focus on the case $\varepsilon\leq1/q$ since when $\varepsilon\geq1/q+\delta$, the problem is solved by the original Goldreich-Levin theorem. As stated, this problem cannot be efficiently solved, since when $\varepsilon\leq1/q$ the list of ${\bf A}$ with good agreement with $f$ might be exponentially large. Our main theorem gives an algorithm which efficiently recovers a list of linear maps of size $\mathcal{O}\bigl(1/\varepsilon\bigr)$ which have good agreement with $f$, and such that every linear map which has good agreement with $f$, also has good agreement with some map in our list. Our proof makes novel use of Fourier analysis.