  We study the compressed sensing reconstruction problem for a broad class of
random, band-diagonal sensing matrices. This construction is inspired by the
idea of spatial coupling in coding theory. As demonstrated heuristically and
numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms
can effectively solve the reconstruction problem for spatially coupled
measurements with undersampling rates close to the fraction of non-zero
coordinates.
  We use an approximate message passing (AMP) algorithm and analyze it through
the state evolution method. We give a rigorous proof that this approach is
successful as soon as the undersampling rate $\delta$ exceeds the (upper)
R\'enyi information dimension of the signal, $\uRenyi(p_X)$. More precisely,
for a sequence of signals of diverging dimension $n$ whose empirical
distribution converges to $p_X$, reconstruction is with high probability
successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band
diagonal matrix.
  For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero
entries, this implies reconstruction from $k(n)+o(n)$ measurements. For
`discrete' signals, i.e., signals whose coordinates take a fixed finite set of
values, this implies reconstruction from $o(n)$ measurements. The result is
robust with respect to noise, does not apply uniquely to random signals, but
requires the knowledge of the empirical distribution of the signal $p_X$.
