We study the support recovery problem for compressed sensing, where the goal is to reconstruct the sparsity pattern of a high-dimensional K-sparse signal x ∈ ℝN, as well as the corresponding sparse coefficients, 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. Specifically, 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 sparsegraph decoding in packet communication systems and analyze our framework in terms of the measurement cost, computational complexity, and recovery performance. Specifically, we show that in the noiseless setting, our framework can recover any arbitrary K-sparse signal in O(K) time using 2K measurements asymptotically with a vanishing error 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δ) for some 0δ) and the magnitudes of all thesparse coefficients are bounded below by a positive constant, our algorithm can recover an arbitrarily large (1- p)-fraction of the support of the sparse signal using O(K log(N/K) log log(N/K)) measurements, and O(K log3(N/K)) run-time, where r is an arbitrarily small constant. For each recovered sparse coefficient, we can achieve O(∈) error for an arbitrarily small constant E. In addition, if the magnitudes of all the sparse coefficients are upper bounded by O(Kc) for some constant c1recovery guarantee for the estimated signal x̂: ∥x̂ - x∥1≤ κ∥x∥1, where the constant κ can be arbitrarily small. This offers the desired scalability of our framework that can potentially enable real-time or near-realtime processing for massive datasets featuring sparsity, which are relevant to a multitude of practical applications.

We study the design of measurement matrices for compressed sensing, where the goal is to stably acquire and reconstruct arbitrary K-sparse N-length signals in the presence of noise. We propose a new design framework that simultaneously leads to low measurement cost and low computational cost. In particular, the proposed framework guarantees successful recovery with high probability using O(K log N) measurements with a computational complexity of O(K log N). Both the measurement cost and algorithm runtime are order-optimal for support recovery when K = O (Nδ ) for some 0 <; δ <; 1. To the best of our knowledge, this is the first result that achieves this optimal scaling. The remarkable gains are brought by the proposed measurement structure based on sparse-graph codes, which allows for reconstructions of sparse signals using a simple peeling decoder. More generally, we formally connect general sparse recovery problems with sparse-graph decoding, and demonstrate our design in terms of the measurement cost, computational complexity and performance.

Sampling of bandlimited signals whose frequency support is unknown is called spectrum-blind sampling. It has attracted considerable attention due to its potential for sampling much lower than the Nyquist rate. The minimum rate for spectrum-blind sampling has been established as twice the measure of the frequency support. We study this sampling problem and propose a novel sampling framework by leveraging tools from modern coding theory. Our approach is based on subsampling the outputs of a carefully designed sparse-graph-codedfilter bank. The key idea is to exploit, rather than avoid, the aliasing artifacts induced by subsampling, which introduces linear mixing of spectral components in the form of parity constraints for sparse-graph codes. Under the proposed sampling scheme, signal reconstruction becomes equivalent to the peeling decoding of sparse-graph codes in erasure channels. As a result, we can simultaneously approach the minimum sampling rate, while also having a computational cost that is linear in the number of samples. We support our theoretical findings through numerical experiments.

We consider the problem of recovering the support of an arbitrary K-sparse N-length vector in the presence of noise, where the sparsity K = O(Nδ) is sub-linear in N for some 01.3̇N) and sub-linear computational complexity O(K log1.3̇N). Our measurement system is designed to capture observations of the signal through the parity constraints of sparse-graph codes, and to recover the signal by using a simple peeling decoder. We formally connect general sparse recovery problems with sparse-graph decoding, and showcase our design in terms of the measurement cost, computational complexity and recovery performance.

Let $f: \{-1,1\}^n \rightarrow \mathbb{R}$ be an $n$-variate polynomial consisting of $2^n$ monomials, in which only $s\ll 2^n$ coefficients are non-zero. The goal is to learn the polynomial by querying the values of $f$. We introduce an active learning framework that is associated with a low query cost and computational runtime. The significant savings are enabled by leveraging sampling strategies based on modern coding theory, specifically, the design and analysis of {\it sparse-graph codes}, such as Low-Density-Parity-Check (LDPC) codes, which represent the state-of-the-art of modern packet communications. More significantly, we show how this design perspective leads to exciting, and to the best of our knowledge, largely unexplored intellectual connections between learning and coding. The key is to relax the worst-case assumption with an ensemble-average setting, where the polynomial is assumed to be drawn uniformly at random from the ensemble of all polynomials (of a given size $n$ and sparsity $s$). Our framework succeeds with high probability with respect to the polynomial ensemble with sparsity up to $s={O}(2^{\delta n})$ for any $\delta\in(0,1)$, where $f$ is exactly learned using ${O}(ns)$ queries in time ${O}(n s \log s)$, even if the queries are perturbed by Gaussian noise. We further apply the proposed framework to graph sketching, which is the problem of inferring sparse graphs by querying graph cuts. By writing the cut function as a polynomial and exploiting the graph structure, we propose a sketching algorithm to learn the an arbitrary $n$-node unknown graph using only few cut queries, which scales {\it almost linearly} in the number of edges and {\it sub-linearly} in the graph size $n$. Experiments on real datasets show significant reductions in the runtime and query complexity compared with competitive schemes.

In this paper, we consider the problem of computing a K-sparse N-point Hadamard Transforms (HT) from noisy time domain samples, where K = O(Nα) scales sub-linearly in N for some α ∈ (0; 1). The SParse Robust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm is proposed to recover the sparse HT coefficients in a stable manner that is robust to additive Gaussian noise. In particular, it is shown that the K-sparse HT of the signal can be reconstructed from noisy time domain samples with a vanishing error probability using the same sample complexity O(K logN) as in the noiseless case of [1] and computational complexity1O(N logN). Last but not least, given the complexity orders of the SPRIGHT algorithm, our numerical experiments further validate that the big-Oh constants in the complexity are small.