We consider the following sparse signal recovery (or feature selection) problem: given a design matrix X\in \mathbb{R} {n\times m} (m\gg n) and a noisy observation vector y\in \mathbb{R} {n} satisfying y X\beta * \epsilon where \epsilon is the noise vector following a Gaussian distribution N(0,\sigma 2I), how to recover the signal (or parameter vector) \beta * when the signal is sparse? The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively refines the target signal \beta * . We show that if X obeys a certain condition, then with a large probability the difference between the solution \hat\beta estimated by the proposed method and the true solution \beta * measured in terms of the l_p norm ( p\geq 1) is bounded as \begin{equation*} \ \hat\beta-\beta *\ _p\leq \left(C(s-N) {1/p}\sqrt{\log m} \Delta\right)\sigma, \end{equation*} C is a constant, s is the number of nonzero entries in \beta *, \Delta is independent of m and is much smaller than the first term, and N is the number of entries of \beta * larger than a certain value in the order of \mathcal{O}(\sigma\sqrt{\log m}) . When N s, the proposed algorithm achieves the oracle solution with a high probability.

Compressive Sensing (CS) combines sampling and compression into a single sub-Nyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefficients are clustered. Our new model-based reconstruction algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms.

Compressive Sensing (CS) combines sampling and compression into a single sub-Nyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefficients are clustered. Our new model-based reconstruction algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms. Papers published at the Neural Information Processing Systems Conference.

We consider the following sparse signal recovery (or feature selection) problem: given a design matrix $X\in \mathbb{R} {n\times m}$ $(m\gg n)$ and a noisy observation vector $y\in \mathbb{R} {n}$ satisfying $y X\beta * \epsilon$ where $\epsilon$ is the noise vector following a Gaussian distribution $N(0,\sigma 2I)$, how to recover the signal (or parameter vector) $\beta *$ when the signal is sparse? The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively refines the target signal $\beta *$. We show that if $X$ obeys a certain condition, then with a large probability the difference between the solution $\hat\beta$ estimated by the proposed method and the true solution $\beta *$ measured in terms of the $l_p$ norm ($p\geq 1$) is bounded as \begin{equation*} \ \hat\beta-\beta *\ _p\leq \left(C(s-N) {1/p}\sqrt{\log m} \Delta\right)\sigma, \end{equation*} $C$ is a constant, $s$ is the number of nonzero entries in $\beta *$, $\Delta$ is independent of $m$ and is much smaller than the first term, and $N$ is the number of entries of $\beta *$ larger than a certain value in the order of $\mathcal{O}(\sigma\sqrt{\log m})$. The proposed method improves the estimation bound of the standard Dantzig selector approximately from $Cs {1/p}\sqrt{\log m}\sigma$ to $C(s-N) {1/p}\sqrt{\log m}\sigma$ where the value $N$ depends on the number of large entries in $\beta *$.

Given an overcomplete dictionary $A$ and a signal $b = Ac^*$ for some sparse vector $c^*$ whose nonzero entries correspond to linearly independent columns of $A$, classical sparse signal recovery theory considers the problem of whether $c^*$ can be recovered as the unique sparsest solution to $b = A c$. It is now well-understood that such recovery is possible by practical algorithms when the dictionary $A$ is incoherent or restricted isometric. In this paper, we consider the more general case where $b$ lies in a subspace $\mathcal{S}_0$ spanned by a subset of linearly dependent columns of $A$, and the remaining columns are outside of the subspace. In this case, the sparsest representation may not be unique, and the dictionary may not be incoherent or restricted isometric. The goal is to have the representation $c$ correctly identify the subspace, i.e. the nonzero entries of $c$ should correspond to columns of $A$ that are in the subspace $\mathcal{S}_0$. Such a representation $c$ is called subspace-preserving, a key concept that has found important applications for learning low-dimensional structures in high-dimensional data. We present various geometric conditions that guarantee subspace-preserving recovery. Among them, the major results are characterized by the covering radius and the angular distance, which capture the distribution of points in the subspace and the similarity between points in the subspace and points outside the subspace, respectively. Importantly, these conditions do not require the dictionary to be incoherent or restricted isometric. By establishing that the subspace-preserving recovery problem and the classical sparse signal recovery problem are equivalent under common assumptions on the latter, we show that several of our proposed conditions are generalizations of some well-known conditions in the sparse signal recovery literature.

Parameterized mathematical models play a central role in understanding and design of complex information systems. However, they often cannot take into account the intricate interactions innate to such systems. On the contrary, purely data-driven approaches do not need explicit mathematical models for data generation and have a wider applicability at the cost of interpretability. In this paper, we consider the design of a one-bit compressive autoencoder, and propose a novel hybrid model-based and data-driven methodology that allows us to not only design the sensing matrix for one-bit data acquisition, but also allows for learning the latent-parameters of an iterative optimization algorithm specifically designed for the problem of one-bit sparse signal recovery. Our results demonstrate a significant improvement compared to state-of-the-art model-based algorithms.

We present DeepFPC, a novel deep neural network designed by unfolding the iterations of the fixed-point continuation algorithm with one-sided l1-norm (FPC-l1), which has been proposed for solving the 1-bit compressed sensing problem. The network architecture resembles that of deep residual learning and incorporates prior knowledge about the signal structure (i.e., sparsity), thereby offering interpretability by design. Once DeepFPC is properly trained, a sparse signal can be recovered fast and accurately from quantized measurements. The proposed model is evaluated in the task of direction-of-arrival (DOA) estimation and is shown to outperform state-of-the-art algorithms, namely, the iterative FPC-l1 algorithm and the 1-bit MUSIC method.

Dantzig Selector (DS) is widely used in compressed sensing and sparse learning for feature selection and sparse signal recovery. Since the DS formulation is essentially a linear programming optimization, many existing linear programming solvers can be simply applied for scaling up. The DS formulation can be explained as a basis pursuit denoising problem, wherein the data matrix (or measurement matrix) is employed as the denoising matrix to eliminate the observation noise. However, we notice that the data matrix may not be the optimal denoising matrix, as shown by a simple counter-example. This motivates us to pursue a better denoising matrix for defining a general DS formulation. We first define the optimal denoising matrix through a minimax optimization, which turns out to be an NPhard problem. To make the problem computationally tractable, we propose a novel algorithm, termed as Optimal Denoising Dantzig Selector (ODDS), to approximately estimate the optimal denoising matrix. Empirical experiments validate the proposed method. Finally, a novel sparse reinforcement learning algorithm is formulated by extending the proposed ODDS algorithm to temporal difference learning, and empirical experimental results demonstrate to outperform the conventional vanilla DS-TD algorithm.

In this paper, we introduce a new sparsity-promoting prior, namely, the "normal product" prior, and develop an efficient algorithm for sparse signal recovery under the Bayesian framework. The normal product distribution is the distribution of a product of two normally distributed variables with zero means and possibly different variances. Like other sparsity-encouraging distributions such as the Student's $t$-distribution, the normal product distribution has a sharp peak at origin, which makes it a suitable prior to encourage sparse solutions. A two-stage normal product-based hierarchical model is proposed. We resort to the variational Bayesian (VB) method to perform the inference. Simulations are conducted to illustrate the effectiveness of our proposed algorithm as compared with other state-of-the-art compressed sensing algorithms.

In this paper, we propose majority voting neural networks for sparse signal recovery in binary compressed sensing. The majority voting neural network is composed of several independently trained feedforward neural networks employing the sigmoid function as an activation function. Our empirical study shows that a choice of a loss function used in training processes for the network is of prime importance. We found a loss function suitable for sparse signal recovery, which includes a cross entropy-like term and an $L_1$ regularized term. From the experimental results, we observed that the majority voting neural network achieves excellent recovery performance, which is approaching the optimal performance as the number of component nets grows. The simple architecture of the majority voting neural networks would be beneficial for both software and hardware implementations.