  We study the support recovery problem for compressed sensing, where the goal
is to reconstruct the a high-dimensional $K$-sparse signal
$\mathbf{x}\in\mathbb{R}^N$, from low-dimensional linear measurements with and
without noise. Our key contribution is a new compressed sensing framework
through a new family of carefully designed sparse measurement matrices
associated with minimal measurement costs and a low-complexity recovery
algorithm. The measurement matrix in our framework is designed based on the
well-crafted sparsification through capacity-approaching sparse-graph codes,
where the sparse coefficients can be recovered efficiently in a few iterations
by performing simple error decoding over the observations. We formally connect
this general recovery problem with sparse-graph decoding in packet
communication systems, and analyze our framework in terms of the measurement
cost, time complexity and recovery performance. In the noiseless setting, our
framework can recover any arbitrary $K$-sparse signal in $O(K)$ time using $2K$
measurements asymptotically with high probability. In the noisy setting, when
the sparse coefficients take values in a finite and quantized alphabet, our
framework can achieve the same goal in time $O(K\log(N/K))$ using
$O(K\log(N/K))$ measurements obtained from measurement matrix with elements
$\{-1,0,1\}$. When the sparsity $K$ is sub-linear in the signal dimension
$K=O(N^\delta)$ for some $0<\delta<1$, our results are order-optimal in terms
of measurement costs and run-time, both of which are sub-linear in the signal
dimension $N$. The sub-linear measurement cost and run-time can also be
achieved with continuous-valued sparse coefficients, with a slight increment in
the logarithmic factors. This offers the desired scalability of our framework
that can potentially enable real-time or near-real-time processing for massive
datasets featuring sparsity.
