It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: 1) a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the nonsparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive-over 20% in the example we consider.

We propose a new algorithm to recover a sparse signal from a system of linear measurements. By projecting the measured signal onto a properly chosen subspace, we can use the projection to zero in on a low-sparsity portion of our original signal, which we can recover using ℓ1-minimization. We can then recover the remaining portion of our signal from an overdetermined system of linear equations. We prove that our scheme improves the threshold of ℓ1-minimization, and we derive an upper bound for this new threshold. We support our theoretical results with numerical simulations which demonstrate that certain classes of signals come close to achieving this upper bound.

Advances in compressed-sensing (CS) have sparked interest in designing information acquisition systems that process data at close to the information rate. Initial proposals for CS signal acquisition systems utilized random matrix ensembles in conjunction with convex relaxation based signal reconstruction algorithms. While providing universal performance bounds, random matrix based formulations present several practical problems due to: the difficulty in physically implementing key mathematical operations, and their dense representation. In this paper, we present a CS architecture which is based on a sub-linear time recovery algorithm (with minimum memory requirement) that exploits a novel structured matrix. This formulation allows the use of a reconstruction algorithm based on relatively simple computational primitives making it more amenable to implementation in a fully-integrated form. Theoretical recovery guarantees are discussed and a hypothetical physical CS decoder is described.

We consider the problem of recovering a sparse signal from underdetermined measurements when we have prior information about the sparsity structure of the signal. In particular, we assume that the entries of the signal can be partitioned into two known sets S1, S2 where the relative sparsities over the two sets are different. In this situation it is advantageous to replace classical ℓ1minimization with weighted ℓ1minimization, where the sparser set is given a larger weight. In this paper we give a simple closed form expression for the minimum number of measurements required for successful recovery when the optimal weights are chosen. The formula shows that the number of measurements is upper bounded by the sum of the minimum number of measurements needed had we measured the S1and S2components of the signal separately. In fact, our results indicate that this upper bound is tight and we actually have equality. Our proof technique uses the “escape through a mesh” framework and connects to the Minimax MSE of a certain basis pursuit denisoing problem.

We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.

The capacity region of multi-pair bidirectional relay networks, in which a relay node facilitates the communication between multiple pairs of users, is studied. This problem is first examined in the context of the linear shift deterministic channel model. The capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode for arbitrary number of pairs is characterized. It is shown that the cut-set upper-bound is tight and the capacity region is achieved by a so called divide-and-conquer relaying strategy. The insights gained from the deterministic network are then used for the Gaussian bidirectional relay network. The strategy in the deterministic channel translates to a specific superposition of lattice codes and random Gaussian codes at the source nodes and successive interference cancelation at the receiving nodes for the Gaussian network. The achievable rate of this scheme with two pairs is analyzed and it is shown that for all channel gains it achieves to within 3 bits/sec/Hz per user of the cut-set upper-bound. Hence, the capacity region of the two-pair bidirectional Gaussian relay network to within 3 bits/sec/Hz per user is characterized.

We consider the problem of network tomography in probabilistic tree mixture models. We invoke the theory of compressed sensing and prove that the distribution of a random communication network model with n nodes represented by a probabilistic mixture of k trees can be identified using low order routing summaries pertinent to groups of small sizes dlog k), then certain classes of inference algorithms can successfully determine the unknown model, i.e. the topologies of mixing trees and their corresponding probabilities. We show that a variation of ℓ1minimization over the space of all possible trees of n nodes can be used for this purpose. In addition, we propose a novel inference algorithm with a complexity polynomial in nlog k, with the same provable guarantee. The proposed model is applicable to practical situations such as ad-hoc and Peer-to-Peer(P2P) networks, and the presented inference method can lead to distributed protocols for network monitoring and tomography. In particular, we provide preliminary insight and numerical results on how the ideas are amenable to wireless sensor networks.

We present an alternative analysis of weighted ℓ1minimization for sparse signals with a nonuniform sparsity model, and extend our results to nuclear norm minimization for matrices with nonuniform singular vector distribution. In the case of vectors, we find explicit upper bounds for the successful recovery thresholds, and give a simple suboptimal weighting rule. For matrices, the thresholds we find are only implicit, and the optimal weight selection requires an exhaustive search. For the special case of very wide matrices, the relationship is made explicit and the optimal weight assignment is the same as the vector case. We demonstrate through simulations that for vectors, the suggested weighting scheme improves the recovery performance over that of regular ℓ1minimization.

Nuclear norm minimization (NNM) has recently gained attention for its use in rank minimization problems. In this paper, we define weak, sectional and strong recovery for NNM to succeed at finding the low rank solution. We find tight conditions for these and analyze them for the case where the linear measurement operator consists of i.i.d. Gaussian entries. Finally we calculate the so called weak, sectional and strong thresholds for the success of nuclear norm minimization. To obtain our results, we generalize the notion of sign and support from sparse vectors to low rank matrices, and achieve a weak threshold which is much closer to the empirical phase transition curve of nuclear norm minimization than the existing bounds available in the literature.

We show that girth can be used to certify that sparse compressed sensing matrices have good sparse approximation guarantees. This allows us to present the first deterministic measurement matrix constructions that have an optimal number of measurements for ℓ1/ℓ1approximation. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding.

We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including l1minimization and two combinatorial methods. In particular, one of the algorithms recovers k-sparse vectors of length N in sublinear time poly(k log N), and requires at most O(k log N log log N) measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for 103≤ N ≤ 1012and k = 100, the oversampling factor is between 5 to 25. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.

Matrix rank minimization (RM) problems recently gained extensive attention due to numerous applications in machine learning, system identification and graphical models. In RM problem, one aims to find the matrix with the lowest rank that satisfies a set of linear constraints. The existing algorithms include nuclear norm minimization (NNM) and singular value thresholding. Thus far, most of the attention has been on i.i.d. Gaussian or Bernoulli measurement operators. In this work, we introduce a new class of measurement operators, and a novel recovery algorithm, which is notably faster than NNM. The proposed operators are based on what we refer to as subspace expanders, which are inspired by the well known expander graphs based measurement matrices in compressed sensing. We show that given an n×n PSD matrix of rank r, it can be uniquely recovered from a minimal sampling of O(nr) measurements using the proposed structures, and the recovery algorithm can be cast as matrix inversion after a few initial processing steps.

The proliferation of mobile applications and services involving group communications has increased the need for efficient wireless multicasting solutions in next generation broadband access networks. The availability of antenna arrays at the base stations makes adaptive beamforming especially attractive for multicasting; with beamforming, the received signal strength at the clients can be significantly improved. However, the problem of designing optimal transmit beamformers for multicast applications is challenging, mainly due to its non-convex nature. In this work, we design efficient transmit beamformers for wireless link layer multicasting where instantaneous channel state information is available at the transmitter. In addressing the non-convexity of the problem, we design non-iterative, near-optimal beamforming algorithms based on the optimality conditions derived from its Lagrangian formulation. We show that for real channels, e.g, where Pulse Amplitude Modulation (PAM) is used, the optimal solution can be obtained. To address the effectiveness of the proposed solution for the complex channel, we also derive an upper bound on the multicast rate based on the dual formulation of the problem. Evaluations reveal that our algorithms deliver a performance that is close to the upper bound, while significantly improving the multicast rate over state of the art solutions.

We consider the problem of maximizing the weighted sum rate (WSR) in MIMO broadcast channel where the number of transmitted streams (ranks) is constrained. The problem is treated both with or without interference pre-compensation also known as dirty paper coding (DPC). The rank constrained problem is highly motivated by the practical consideration on the receiver complexity in current wireless systems such as LTE. We propose a unified algorithm based on fixed point iteration. The proposed approach has very fast convergence rate that usually converges to the minimal number of streams for each user and finds the corresponding optimal precoding matrix. Rank minimization is particularly desirable in practice. The order in which the users' streams are encoded is crucial when dirty paper coding is allowed. We prove that the optimal user ordering does not depend on the transmission rank constraints and is given only by the weight vector. Using simulations, we compare the performance of our proposed scheme with the best known algorithms in the literature and demonstrate the effect of rank constraints.

It is now well understood that the ℓ1minimization algorithm is able to recover sparse signals from incomplete measurements and sharp recoverable sparsity thresholds have also been obtained for the ℓ1minimization algorithm. However, even though iterative reweighted ℓ1minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted ℓ1algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted ℓ1minimization can indeed deliver recoverable sparsity thresholds larger than that given in. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for ℓ1minimization and weighted ℓ1minimization algorithms.

It is well known that ℓ1minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as “weak thresholds”. In this paper, we introduce a reweighted ℓ1recovery algorithm composed of two steps: a standard ℓ1minimization step to identify a set of entries where the signal is likely to reside, and a weighted ℓ1minimization step where entries outside this set are penalized. For signals where the non-sparse component has iid Gaussian entries, we prove a “strict” improvement in the weak recovery threshold. Simulations suggest that the improvement can be quite impressive-over 20% in the example we consider.

This paper studies compressed sensing for the recovery of non-negative sparse vectors from a smaller number of measurements than the ambient dimension of the unknown vector. We focus on measurement matrices that are sparse, i.e., have only a constant number of nonzero (and non-negative) entries in each column. For such measurement matrices we give a simple necessary and sufficient condition for l1optimization to successfully recover the unknown vector. Using a simple ldquoperturbationrdquo to the adjacency matrix of an unbalanced expander, we obtain simple closed form expressions for the threshold relating the ambient dimension n, number of measurements m and sparsity level k, for which l1optimization is successful with overwhelming probability. Simulation results suggest that the theoretical thresholds are fairly tight and demonstrate that the ldquoperturbationsrdquo significantly improve the performance over a direct use of the adjacency matrix of an expander graph.

We study the capacity of the Gaussian two-pair fullduplex directional (or two-way) relay network with a single-relay supporting the communication of the pairs. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We propose a novel transmission technique which is based on a specific superposition of lattice codes and random Gaussian codes at the source nodes. The relay attempts to decode the Gaussian codewords and the superposition of the lattice codewords of each pair. Then it forwards this information to all users. We analyze the achievable rate of this scheme and show that for all channel gains it achieves to within 2 bits/sec/Hz per user of the cut-set upper bound on the capacity region of the two-pair bidirectional relay network.

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted ¿1minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted ¿1minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional ¿1optimization.

In this paper we study the capacity region of the multi-pair bidirectional (or two-way) wireless relay network, in which a relay node facilitates the communication between multiple pairs of users. This network is a generalization of the well known bidirectional relay channel, where we have only one pair of users. We examine this problem in the context of the deterministic channel interaction model, which eliminates the channel noise and allows us to focus on the interaction between signals. We characterize the capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode (with non adaptive listen-transmit scheduling). In both cases we show that the cut-set upper bound is tight and, quite interestingly, the capacity region is achieved by a simple equation-forwarding strategy.