  We consider the \textit{phase retrieval} problem of recovering a sparse
signal $\mathbf{x}$ in $\mathbb{R}^d$ from intensity-only measurements in
dimension $d \geq 2$. Phase retrieval can be equivalently formulated as the
problem of recovering a signal from its autocorrelation, which is in turn
directly related to the combinatorial problem of recovering a set from its
pairwise differences. In one spatial dimension, this problem is well studied
and known as the \textit{turnpike problem}. In this work, we present MISTR
(Multidimensional Intersection Sparse supporT Recovery), an algorithm which
exploits this formulation to recover the support of a multidimensional signal
from magnitude-only measurements. MISTR takes advantage of the structure of
multiple dimensions to provably achieve the same accuracy as the best
one-dimensional algorithms in dramatically less time. We prove theoretically
that MISTR correctly recovers the support of signals distributed as a Gaussian
point process with high probability as long as sparsity is at most
$\mathcal{O}\left(n^{d\theta}\right)$ for any $\theta < 1/2$, where $n^d$
represents pixel size in a fixed image window. In the case that magnitude
measurements are corrupted by noise, we provide a thresholding scheme with
theoretical guarantees for sparsity at most
$\mathcal{O}\left(n^{d\theta}\right)$ for $\theta < 1/4$ that obviates the need
for MISTR to explicitly handle noisy autocorrelation data. Detailed and
reproducible numerical experiments demonstrate the effectiveness of our
algorithm, showing that in practice MISTR enjoys time complexity which is
nearly linear in the size of the input.
