Abstract

Many applications in cellular systems and sensor networks involve a random subset of a large number of users asynchronously reporting activity to a base station. This paper examines the problem of multiuser detection (MUD) in random access channels for such applications. Traditional orthogonal signaling ignores the random nature of user activity in this problem and limits the total number of users to be on the order of the number of signal space dimensions. Contention-based schemes, on the other hand, suffer from delays caused by colliding transmissions and the hidden node problem. In contrast, this paper presents a novel pairing of an asynchronous non-orthogonal code-division random access scheme with a convex optimization-based MUD algorithm that overcomes the issues associated with orthogonal signaling and contention-based methods. Two key distinguishing features of the proposed MUD algorithm are that it does not require knowledge of the delay or channel state information of every user and it has polynomial-time computational complexity. The main analytical contribution of this paper is the relationship between the performance of the proposed MUD algorithm in the presence of arbitrary or random delays and two simple metrics of the set of user codewords. The study of these metrics is then focused on two specific sets of codewords, random binary codewords and specially constructed algebraic codewords, for asynchronous random access. The ensuing analysis confirms that the proposed scheme together with either of these two codeword sets significantly outperforms the orthogonal signaling-based random access in terms of the total number of users in the system.

@article{Applebaum_PHYCOMM11,
title = "Asynchronous code-division random access using convex optimization",
author = "Lorne Applebaum and Waheed U. Bajwa and Marco F. Duarte and Robert Calderbank",
journal = "Physical Communication",
volume = "",
number = "0",
pages = " - ",
year = "2011",
note = "",
issn = "1874-4907",
doi = "10.1016/j.phycom.2011.09.006",
url = "http://www.sciencedirect.com/science/article/pii/S187449071100053X"
}
			  

Abstract

Compressed sensing is a novel technique to acquire sparse signals with few measurements. Normally, compressed sensing uses random projections as measurements. Here we design deterministic measurements and an algorithm to accomplish signal recovery with computational efficiency. A measurement matrix is designed with chirp sequences forming the columns. Chirps are used since an efficient method using FFTs can recover the parameters of a small superposition. We show that this type of matrix is valid as compressed sensing measurements. This is done by bounding the eigenvalues of sub-matrices, as well as an empirical comparison with random projections. Further, by implementing our algorithm, simulations show successful recovery of signals with sparsity levels similar to those possible by matching pursuit with random measurements. For sufficiently sparse signals, our algorithm recovers the signal with computational complexity O(KlogK) for K measurements. This is a significant improvement over existing algorithms.

@article{Applebaum_ACHA09,
title = "Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery",
author = "Lorne Applebaum and Stephen D. Howard and Stephen Searle and Robert Calderbank",
journal = "Applied and Computational Harmonic Analysis",
volume = "26",
number = "2",
pages = "283 - 290",
year = "2009",
note = "",
issn = "1063-5203",
doi = "10.1016/j.acha.2008.08.002",
url = "http://www.sciencedirect.com/science/article/pii/S1063520308000869"
}
			  

Abstract

Communication networks conventionally operate with half-duplex methods and interference avoiding schemes to manage multiple transceivers. Here we consider a method in which nodes transmit and receive in concert to achieve full duplex communication without transmitter coordination. We build on a recent framework for full-duplex communication in ad-hoc wireless networks recently proposed by Zhang, Luo and Guo. An individual node in the wireless network either transmits or it listens to transmissions from other nodes but it cannot do both at the same time. There might be as many nodes as there are MAC addresses but we assume that only a small subset of nodes contribute to the superposition received at any given node in the network. We develop deterministic algebraic coding methods that allow simultaneous communication across the entire network. We call such codes choir codes. Users are assigned subspaces of F_{2^m} to define their transmit and listen times. Codewords on these subspaces are designed and proven to adhere to bounds on worst-case coherence and the associated matrix spectral norm. This in turn provides guarantees for multi-user detection using convex optimization. Further, we show that matrices for each receiver's listening times can be related by permutations, thus guaranteeing fairness between receivers. Compared with earlier work using random codes, our methods have significant improvements including reduced decoding/detection error and non-asymptotic results. Simulation results verify that, as a method to manage interference, our scheme has significant advantages over seeking to eliminate or align interference through extensive exchange of fine-grained channel state information.

@inproceedings{Applebaum_ChoirCodesAllerton,
title = "Choir Codes: Coding for Full Duplex Interference Management",
author = "Lorne Applebaum and Waheed U. Bajwa and Robert Calderbank and Stephen Howard",
booktitle = "49th Annual Allerton Conference on Communication, Control and Computing",
address = "Monticello, IL",
month = sep,
year = "2011"
}
			  

Abstract

This paper examines the problem of multipath channel estimation in single-antenna orthogonal frequency division multiplexing (OFDM) systems. In particular, we study the problem of pilot assisted channel estimation in wideband OFDM systems, where the time-domain (discrete) channel is approximately sparse. Existing works on this topic established that techniques from the compressed sensing literature can yield accurate channel estimates using a relatively small number of pilot tones, provided the pilots are selected randomly. Here, we describe a general purpose procedure for deterministic selection of pilot tones to be used for channel estimation, and establish guarantees for channel estimation accuracy using these sequences along with recovery techniques from the compressed sensing literature. Simulation results are presented to demonstrate the effectiveness of the proposed procedure in practice.

@inproceedings{Applebaum_DSP11,
title = "Deterministic Pilot Sequences for Sparse Channel Estimation in OFDM Systems",
author = "Lorne Applebaum and Waheed U. Bajwa and Robert Calderbank and 
          Jarvis Haupt and Robert Nowak",
booktitle = "17th International Conference on Digital Signal Processing",
address = "Corfu, Greece",
month = jul,
year = "2011"
}
			  

Abstract

This paper considers on-off random access channels where users transmit either a one or a zero to a base station. Such channels represent an abstraction of control channels used for scheduling requests in third-generation cellular systems and uplinks in wireless sensor networks deployed for target detection. This paper introduces a novel convex-optimization-based scheme for multiuser detection (MUD) in asynchronous on-off random access channels that does not require knowledge of the delays or the instantaneous received signal-to-noise ratios of the individual users at the base station. For any fixed number of temporal signal space dimensions N and maximum delay τ in the system, the proposed scheme can accommodate M ≲ exp(O(N1/3)) total users and k ≲ N/ log M active users in the system-a significant improvement over the k ≤ M ≲ N scaling suggested by the use of classical matched-filtering-based approaches to MUD employing orthogonal signaling. Furthermore, the computational complexity of the proposed scheme differs from that of a similar oracle-based scheme with perfect knowledge of the user delays by at most a factor of log(N+τ). Finally, the results presented in here are non-asymptotic, in contrast to related previous work for synchronous channels that only guarantees that the probability of MUD error at the base station goes to zero asymptotically in M.

@inproceedings{Applebaum_Allerton10, 
author={Lorne Applebaum and Waheed U. Bajwa and Marco F. Duarte and Robert Calderbank}, 
title={Multiuser Detection in Asynchronous On--Off Random Access Channels Using Lasso},
booktitle={48th Annual Allerton Conference on Communication, Control, and Computing},
year={2010}, 
month= oct, 
address= {Monticello, IL},
doi={10.1109/ALLERTON.2010.5706898}, 
}
			  

Abstract

Matrices satisfying the Restricted Isometry Property (RIP) are central to the emerging theory of compressive sensing (CS). Initial results in CS established that the recovery of sparse vectors x from a relatively small number of linear observations of the form y = Ax can be achieved, using a tractable convex optimization, whenever A is a matrix that satisfies the RIP; similar results also hold when x is nearly sparse or the observations are corrupted by noise. In contrast to random constructions prevalent in many prior works in CS, this paper establishes a collection of deterministic matrices, formed by deterministic selection of rows of Fourier matrices, which satisfy the RIP. Implications of this result for the recovery of signals having sparse spectral content over a large bandwidth are discussed.

@inproceedings{Haupt_CISS10, 
author={Jarvis Haupt and Lorne Applebaum and Robert Nowak}, 
title={On the Restricted Isometry of deterministically subsampled Fourier matrices}, 
booktitle={44th Annual Conference on Information Sciences and Systems (CISS)}, 
year={2010}, 
month={march}, 
address={Princeton, NJ}
doi={10.1109/CISS.2010.5464880}, 
}
			  

Abstract

We propose a simple method for downlink communications based on second order Reed-Muller sequences which generalize the Walsh sequences that are used in orthogonal CDMA. In our approach, coding occurs at the chip level (i.e. we use a spreading factor of 1) and different users are not orthogonalized. Our decoding algorithm is borrowed from work on fast reconstruction of signals for compressed-sensing. This algorithm allows for low-complexity multiuser detection.

@inproceedings{Aggarwal_Allerton09, 
author={Vaneet Aggarwal and Lorne Applebaum and Amir Bennatan and Robert Calderbank and Stephen Howard and Stephen Searle}, 
booktitle={47th Annual Allerton Conference on Communication, Control, and Computing}, 
title={Enhanced CDMA Communications Using Compressed-sensing Reconstruction Methods}, 
year={2009}, 
month=oct, 
address={Monticello, IL},
doi={10.1109/ALLERTON.2009.5394537}, 
}