CTG Publications http://www.nari.ee.ethz.ch/commth/pubs/viewpubs.php?group=y CTG Publications Wed, 16 May 2012 23:43:08 +0200 http://www.nari.ee.ethz.ch en A short course on frame theory http://www.nari.ee.ethz.ch/commth/pubs/p/frameschapter 2012-01-01 http://www.nari.ee.ethz.ch/commth/pubs/p/frameschapter Authors Veniamin I. Morgenshtern and Helmut Bölcskei

Reference

Chapter in Mathematical Foundations for Signal Processing, Communications, and Networking, E. Serpedin, T. Chen, and D. Rajan, Eds., CRC Press, pp. 737-789, 2012.


Download this document:

 

Copyright Notice: © 2012 V. I. Morgenshtern and H. Bölcskei.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Diversity-multiplexing tradeoff in two-user fading interference channels http://www.nari.ee.ethz.ch/commth/pubs/p/it2009_int 2012-01-01 http://www.nari.ee.ethz.ch/commth/pubs/p/it2009_int Authors Cemal Akçaba and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, 2012, to appear.

Abstract

We analyze the two-user single-antenna fading interference channel with perfect receive channel state information (CSI) and no transmit CSI. The diversity-multiplexing tradeoff (DMT) region of a fixed-power-split Han and Kobayashi (HK)-type superposition coding scheme is considered and design criteria for the corresponding superposition codes are derived. We demonstrate that this scheme is DMT-optimal under strong and very strong interference by showing that it achieves a DMT region outer bound that we derive. In addition, we show that, under very strong interference, decoding interference while treating the intended signal as noise, subtracting the result out, and then decoding the desired signal, a process known as “stripping”, achieves the optimal DMT region. Our proofs reveal code design criteria for achieving DMT optimality (in the cases where we can demonstrate it).

Keywords

Interference channel, diversity-multiplexing tradeoff, Han-Kobayashi scheme


Download this document:

 

Copyright Notice: © 2012 C. Akçaba and H. Bölcskei.

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Recovery of sparsely corrupted signals http://www.nari.ee.ethz.ch/commth/pubs/p/sparserec 2012-05-01 http://www.nari.ee.ethz.ch/commth/pubs/p/sparserec Authors Christoph Studer, Patrick Kuppinger, Graeme Pope, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, pp. 3115-3130, May 2012

DOI: 10.1109/TIT.2011.2179701

Abstract

We investigate the recovery of signals exhibiting a sparse representation in a general (i.e., possibly redundant or incomplete) dictionary that are corrupted by additive noise admitting a sparse representation in another general dictionary. This setup covers a wide range of applications, such as image inpainting, super-resolution, signal separation, and recovery of signals that are impaired by, e.g., clipping, impulse noise, or narrowband interference. We present deterministic recovery guarantees based on a novel uncertainty relation for pairs of general dictionaries and we provide corresponding practicable recovery algorithms. The recovery guarantees we find depend on the signal and noise sparsity levels, on the coherence parameters of the involved dictionaries, and on the amount of prior knowledge about the signal and noise support sets.

Keywords

Uncertainty relations, signal restoration, signal separation, coherence-based recovery guarantees, l1-norm minimization, greedy algorithms


Download this document:

 

Copyright Notice: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Capacity pre-log of noncoherent SIMO channels via Hironaka's Theorem http://www.nari.ee.ethz.ch/commth/pubs/p/mrydlsb12 2012-04-01 http://www.nari.ee.ethz.ch/commth/pubs/p/mrydlsb12 Authors Veniamin I. Morgenshtern, Erwin Riegler, Wei Yang, Giuseppe Durisi, Shaowei Lin, Bernd Sturmfels, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Apr. 2012, submitted.

Abstract

We find the capacity pre-log of a temporally correlated Rayleigh block-fading SIMO channel in the noncoherent setting. It is well known that for block-length L and rank of the channel covariance matrix equal to Q, the capacity pre-log in the SISO case is given by 1-Q/L. Here, Q/L can be interpreted as the pre-log penalty incurred by channel uncertainty. Our main result reveals that, by adding only one receive antenna, this penalty can be reduced to 1/L and can, hence, be made to vanish in the large-L limit, even if Q/L remains constant as L goes to infinity. Intuitively, even though the SISO channels between the transmit antenna and the two receive antennas are statistically independent, the transmit signal induces enough statistical dependence between the corresponding receive signals for the second receive antenna to be able to resolve the uncertainty associated with the first receive antenna's channel and thereby make the overall system appear coherent. The proof of our main theorem is based on a deep result from algebraic geometry known as Hironaka's Theorem on the Resolution of Singularities.


Download this document:

 

Copyright Notice: © 2012 V. I. Morgenshtern, E. Riegler, W. Yang, G. Durisi, S. Lin, B. Sturmfels, and H. Bölcskei.

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Uncertainty relations and sparse signal recovery for pairs of general signal sets http://www.nari.ee.ethz.ch/commth/pubs/p/UncRel2011 2012-01-01 http://www.nari.ee.ethz.ch/commth/pubs/p/UncRel2011 Authors Patrick Kuppinger, Giuseppe Durisi, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 58, No. 1, pp. 263-277, Jan. 2012

DOI: 10.1109/TIT.2011.2167215

Abstract

We present an uncertainty relation for the representation of signals in two different general (possibly redundant or incomplete) signal sets. This uncertainty relation is relevant for the analysis of signals containing two distinct features each of which can be described sparsely in a suitable general signal set. Furthermore, the new uncertainty relation is shown to lead to improved sparsity thresholds for recovery of signals that are sparse in general dictionaries. Specifically, our results improve on the well-known (1+1/d)/2-threshold for dictionaries with coherence d by up to a factor of two. Furthermore, we provide probabilistic recovery guarantees for pairs of general dictionaries that also allow us to understand which parts of a general dictionary one needs to randomize over to “weed out” the sparsity patterns that prohibit breaking the square-root bottleneck.

Keywords

Basis pursuit, frame theory, orthogonal matching pursuit, signal recovery, sparsity, uncertainty relations


Download this document:

 

Copyright Notice: © 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Information theory of underspread WSSUS channels http://www.nari.ee.ethz.ch/commth/pubs/p/dmbss_book10 2011-01-01 http://www.nari.ee.ethz.ch/commth/pubs/p/dmbss_book10 Authors Giuseppe Durisi, Veniamin I. Morgenshtern, Helmut Bölcskei, Ulrich G. Schuster, and Shlomo Shamai (Shitz)

Reference

Chapter in Wireless Communications over Rapidly Time-Varying Channels, F. Hlawatsch and G. Matz, Eds., Academic Press, pp. 65-116, 2011.


Download this document:

 

Copyright Notice: © 2011 G. Durisi, V. I. Morgenshtern, H. Bölcskei, U. G. Schuster, and S. Shamai (Shitz).

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Information-theoretic analysis of MIMO channel sounding http://www.nari.ee.ethz.ch/commth/pubs/p/phase07 2011-11-01 http://www.nari.ee.ethz.ch/commth/pubs/p/phase07 Authors Daniel S. Baum and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 57, No. 11, pp. 7555-7577, Nov. 2011

DOI: 10.1109/TIT.2011.2165129

Abstract

The large majority of commercially available multiple-input multiple-output (MIMO) radio channel measurement devices (sounders) is based on time-division multiplexed switching (TDMS) of a single transmit/receive radio frequency chain into the elements of a transmit/receive antenna array. While being cost-effective, such a solution can cause significant measurement errors due to phase noise and frequency offset in the local oscillators. In this paper, we systematically analyze the resulting errors and show that, in practice, overestimation of channel capacity by several hundred percent can occur. Overestimation is caused by phase noise (and to a lesser extent by frequency offset) leading to an increase of the MIMO channel rank. Our analysis furthermore reveals that the impact of phase errors is, in general, most pronounced if the physical channel has low rank (typical for line-of-sight or poor scattering scenarios). The extreme case of a rank-1 physical channel is analyzed in detail. The capacity bounds derived in this paper show excellent agreement with measurement results. In light of the findings of this paper, the results obtained through MIMO channel measurement campaigns using TDMS-based channel sounders should be interpreted with great care.

Keywords

Channel measurement, multiple-input multiple-output (MIMO), phase noise, sounding


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> On the complexity distribution of sphere decoding http://www.nari.ee.ethz.ch/commth/pubs/p/SDdist09 2011-09-01 http://www.nari.ee.ethz.ch/commth/pubs/p/SDdist09 Authors Dominik Seethaler, Joakim Jaldén, Christoph Studer, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 57, No. 9, pp. 5754-5768, Sept. 2011

DOI: 10.1109/TIT.2011.2162177

Abstract

We analyze the (computational) complexity distribution of sphere decoding (SD) for random infinite lattices. In particular, we show that under fairly general assumptions on the statistics of the lattice basis matrix, the tail behavior of the SD complexity distribution is fully determined by the inverse volume of the fundamental regions of the underlying lattice. Particularizing this result to NxM, N>=M, i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we find that the corresponding complexity distribution is of Pareto-type with tail exponent given by N-M+1. A more refined analysis reveals that the corresponding average complexity of SD is infinite for N = M and finite for N > M. Finally, for i.i.d. circularly symmetric complex Gaussian lattice basis matrices, we analyze SD preprocessing techniques based on lattice-reduction (such as the LLL algorithm or layer-sorting according to the V-BLAST algorithm) and regularization. In particular, we show that lattice reduction does not improve the tail exponent of the complexity distribution while regularization results in a SD complexity distribution with tails that decrease faster than polynomial.

Keywords

Closest lattice point problem, complexity distribution, MIMO wireless, random lattices, sphere decoding


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Compressive identification of linear operators http://www.nari.ee.ethz.ch/commth/pubs/p/isit2011CILO 2011-08-01 http://www.nari.ee.ethz.ch/commth/pubs/p/isit2011CILO Authors Reinhard Heckel and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, pp. 1412-1416, Aug. 2011

DOI: 10.1109/ISIT.2011.6033772

Abstract

We consider the problem of identifying a linear deterministic operator from an input-output measurement. For the large class of continuous (and hence bounded) operators, under additional mild restrictions, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies D <= 1/2. This result holds for arbitrary (possibly fragmented) support regions of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region of the spreading function to be known prior to identification. Furthermore, we prove that asking for identifiability of only almost all operators, stable identifiability is possible if D <= 1. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification.


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> High-SNR capacity of wireless communication channels in the noncoherent setting: A primer http://www.nari.ee.ethz.ch/commth/pubs/p/AEU2011 2011-08-01 http://www.nari.ee.ethz.ch/commth/pubs/p/AEU2011 Authors Giuseppe Durisi and Helmut Bölcskei

Reference

International Journal of Electronics and Communications (AEÜ), Vol. 65, Issue 8, pp. 707-712, Aug. 2011

DOI: 10.1016/j.aeue.2011.02.003

Abstract

This paper, mostly tutorial in nature, deals with the problem of characterizing the capacity of fading channels in the high signal-to-noise ratio (SNR) regime. We focus on the practically relevant noncoherent setting, where neither transmitter nor receiver know the channel realizations, but both are aware of the channel law. We present, in an intuitive and accessible form, two tools, first proposed by Lapidoth and Moser (2003), of fundamental importance to high-SNR capacity analysis: the duality approach and the escape-to-in finity property of capacity-achieving distributions. Furthermore, we apply these tools to refi ne some of the results that appeared previously in the literature and to simplify the corresponding proofs.

Keywords

Shannon capacity, high SNR, non coherent communication


Download this document:

 

Copyright Notice: © 2011 G. Durisi and H. Bölcskei.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Noncoherent SIMO pre-log via resolution of singularities http://www.nari.ee.ethz.ch/commth/pubs/p/rmdlsb11 2011-08-01 http://www.nari.ee.ethz.ch/commth/pubs/p/rmdlsb11 Authors Erwin Riegler, Veniamin I. Morgenshtern, Giuseppe Durisi, Shaowei Lin, Bernd Sturmfels, and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, pp. 2020-2024, Aug. 2011

DOI: 10.1109/ISIT.2011.6033909

Abstract

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Our result holds for arbitrary rank Q of the channel correlation matrix, arbitrary block-length L > Q, and arbitrary number of receive antennas R, and includes the result in Morgenshtern et al. (2010) as a special case. It is well known that the capacity pre-log for this channel in the single-input single-output (SISO) case is given by 1−Q/L, where Q/L is the penalty incurred by channel uncertainty. Our result reveals that this penalty can be reduced to 1/L by adding only one receive antenna, provided that L ≥ 2Q − 1 and the channel correlation matrix satisfies mild technical conditions. The main technical tool used to prove our result is Hironaka’s celebrated theorem on resolution of singularities in algebraic geometry.


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Sparse signal recovery from sparsely corrupted measurements http://www.nari.ee.ethz.ch/commth/pubs/p/ISIT11-sparse 2011-08-01 http://www.nari.ee.ethz.ch/commth/pubs/p/ISIT11-sparse Authors Christoph Studer, Patrick Kuppinger, Graeme Pope, and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, pp. 1422-1426, Aug. 2011

DOI: 10.1109/ISIT.2011.6033774

Abstract

We investigate the recovery of signals exhibiting a sparse representation in a general (i.e., possibly redundant or incomplete) dictionary that are corrupted by additive noise admitting a sparse representation in another general dictionary. This setup covers a wide range of applications, such as image inpainting, super-resolution, signal separation, and the recovery of signals that are corrupted by, e.g., clipping, impulse noise, or narrowband interference. We present deterministic recovery guarantees based on a recently developed uncertainty relation and provide corresponding recovery algorithms. The recovery guarantees we find depend on the signal and noise sparsity levels, on the coherence parameters of the involved dictionaries, and on the amount of prior knowledge on the support sets of signal and noise.

Keywords

Sparse signal recovery, compressed sensing, uncertainty relations


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Sensitivity of noncoherent WSSUS fading channel capacity http://www.nari.ee.ethz.ch/commth/pubs/p/sensitivity2011 2011-07-01 http://www.nari.ee.ethz.ch/commth/pubs/p/sensitivity2011 Authors Giuseppe Durisi, Veniamin I. Morgenshtern, and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, July 2011, submitted.

Abstract

The noncoherent capacity of stationary discrete-time fading channels is known to be very sensitive to the fine details of the channel model. More specifically, the measure of the support of the fading-process power spectral density (PSD) determines if noncoherent capacity grows logarithmically in SNR or slower than logarithmically. Such a result is unsatisfactory from an engineering point of view, as the support of the PSD cannot be determined through measurements. The aim of this paper is to assess whether, for general continuous-time fading channels, this sensitivity has a noticeable impact on capacity at SNR values of practical interest. To this end, we consider the general class of band-limited continuous-time Rayleigh-fading channels that satisfy the wide-sense stationary uncorrelated-scattering (WSSUS) assumption and are, in addition, underspread. We show that, for all SNR values of practical interest, the noncoherent capacity of every channel in this class is close to the capacity of an AWGN channel with the same SNR and bandwidth, independently of the measure of the support of the scattering function (the two-dimensional channel PSD). Our result is based on a lower bound on noncoherent capacity, which is built on a discretization of the channel input-output relation induced by projecting onto Weyl-Heisenberg (WH) sets. This approach is interesting in its own right as it yields a mathematically tractable way of dealing with the mutual information between certain continuous-time random signals.

Keywords

Fading channel, capacity, noncoherent, sensitivity, underspread


Download this document:

 

Copyright Notice: © 2011 G. Durisi, V. I. Morgenshtern, and H. Bölcskei.

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Algorithms for interpolation-based QR decomposition in MIMO-OFDM systems http://www.nari.ee.ethz.ch/commth/pubs/p/qrdectsp11 2011-04-01 http://www.nari.ee.ethz.ch/commth/pubs/p/qrdectsp11 Authors Davide Cescato and Helmut Bölcskei

Reference

IEEE Transactions on Signal Processing, Vol. 59, No. 4, pp. 1719-1733, Apr. 2011

DOI: 10.1109/TSP.2010.2104149

Abstract

Detection algorithms for multiple-input multiple-output (MIMO) wireless systems based on orthogonal frequency-division multiplexing (OFDM) typically require the computation of a QR decomposition for each of the data-carrying OFDM tones. The resulting computational complexity will, in general, be significant. Motivated by the fact that the channel matrices arising in MIMO-OFDM systems result from oversampling of a polynomial matrix, we formulate interpolation-based QR decomposition algorithms. An in-depth complexity analysis, based on a metric relevant for very large scale integration (VLSI) implementations, shows that the proposed algorithms, for a sufficiently large number of data-carrying tones and sufficiently small channel order, provably exhibit significantly smaller complexity than brute-force per-tone QR decomposition.

Keywords

Interpolation, polynomial matrices, multiple-input multiple-output (MIMO) systems, orthogonal frequency-division multiplexing (OFDM), QR decomposition, sphere decoding, successive cancelation, very large scale integration (VLSI)


Download this document:

 

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Soft-input soft-output single tree-search sphere decoding http://www.nari.ee.ethz.ch/commth/pubs/p/sisosts09 2010-10-01 http://www.nari.ee.ethz.ch/commth/pubs/p/sisosts09 Authors Christoph Studer and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 56, No. 10, pp. 4827-4842, Oct. 2010

DOI: 10.1109/TIT.2010.2059730

Abstract

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The computational complexity of SISO detection often poses significant challenges for practical receiver implementations, in particular in the context of multiple-input multiple-output (MIMO) wireless communication systems. In this paper, we present a low-complexity SISO sphere-decoding algorithm, based on the single tree-search paradigm proposed originally for soft-output MIMO detection in Studer, et al., IEEE J-SAC, 2008. The new algorithm incorporates clipping of the extrinsic log-likelihood ratios (LLRs) into the tree-search, which results in significant complexity savings and allows to cover a large performance/complexity tradeoff region by adjusting a single parameter. Furthermore, we propose a new method for correcting approximate LLRs---resulting from sub-optimal detectors---which (often significantly) improves detection performance at low additional computational complexity.

Keywords

Multiple-input multiple-output (MIMO) communication, soft-input soft-output detection, sphere decoding, iterative MIMO decoding


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> QR decomposition of Laurent polynomial matrices sampled on the unit circle http://www.nari.ee.ethz.ch/commth/pubs/p/qrdecit10 2010-09-01 http://www.nari.ee.ethz.ch/commth/pubs/p/qrdecit10 Authors Davide Cescato and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 56, No. 9, pp. 4754-4761, Sept. 2010

DOI: 10.1109/TIT.2010.2054454

Abstract

We consider Laurent polynomial (LP) matrices defined on the unit circle of the complex plane. QR decomposition of an LP matrix A(s) yields QR factors Q(s) and R(s) that, in general, are neither LP nor rational matrices. In this paper, we present an invertible mapping that transforms Q(s) and R(s) into LP matrices. Furthermore, we show that, given QR factors of sufficiently many samples of A(s), it is possible to obtain QR factors of additional samples of A(s) through application of this mapping followed by interpolation and inversion of the mapping. The results of this paper find applications in the context of signal processing for multiple-input multiple-output (MIMO) wireless communication systems that employ orthogonal frequency-division multiplexing (OFDM).

Keywords

Interpolation, Laurent polynomial (LP) matrices, QR decomposition, sampling


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Block-sparse signals: Uncertainty relations and efficient recovery http://www.nari.ee.ethz.ch/commth/pubs/p/Block2009 2010-06-01 http://www.nari.ee.ethz.ch/commth/pubs/p/Block2009 Authors Yonina Eldar, Patrick Kuppinger, and Helmut Bölcskei

Reference

IEEE Transactions on Signal Processing, Vol. 58, No. 6, pp. 3042-3054, June 2010

DOI: 10.1109/TSP.2010.2044837

Abstract

We consider efficient methods for the recovery of block-sparse signals - i.e., sparse signals that have nonzero entries occurring in clusters - from an underdetermined system of linear equations. An uncertainty relation for block-sparse signals is derived, based on a block-coherence measure, which we introduce. We then show that a block-version of the orthogonal matching pursuit algorithm recovers block k-sparse signals in no more than k steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed l2/l1-optimization approach. This complements previous recovery results for the block-sparse case which relied on small block-restricted isometry constants. The significance of the results presented in this paper lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

Keywords

Basis pursuit, block-sparsity, compressed sensing, matching pursuit


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> The SIMO pre-log can be larger than the SISO pre-log http://www.nari.ee.ethz.ch/commth/pubs/p/mdb_isit2010 2010-06-01 http://www.nari.ee.ethz.ch/commth/pubs/p/mdb_isit2010 Authors Veniamin I. Morgenshtern, Giuseppe Durisi, and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), Austin, TX, pp. 320-324, June 2010

DOI: 10.1109/ISIT.2009.5205806

Abstract

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Surprisingly, when the covariance matrix of the channel satisfies a certain technical condition related to the cardinality of its smallest set of linearly dependent rows, this lower bound reveals that the capacity pre-log in the SIMO case is larger than that in the single-input single-output (SISO) case.

Keywords

Fading channels, single-input multiple-output (SIMO), capacity pre-log


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Where is randomness needed to break the square-root bottleneck? http://www.nari.ee.ethz.ch/commth/pubs/p/isit2010KDB 2010-06-01 http://www.nari.ee.ethz.ch/commth/pubs/p/isit2010KDB Authors Patrick Kuppinger, Giuseppe Durisi, and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), Austin, TX, pp. 1578-1582, June 2010

DOI: 10.1109/ISIT.2010.5513456

Abstract

As shown by Tropp, 2008, for the concatenation of two orthonormal bases (ONBs), breaking the square-root bottleneck in compressed sensing does not require randomization over all the positions of the nonzero entries of the sparse coefficient vector. Rather the positions corresponding to one of the two ONBs can be chosen arbitrarily. The two-ONB structure is, however, restrictive and does not reveal the property that is responsible for allowing to break the bottleneck with reduced randomness. For general dictionaries we show that if a sub-dictionary with small enough coherence and large enough cardinality can be isolated, the bottleneck can be broken under the same probabilistic model on the sparse coefficient vector as in the two-ONB case.

Keywords

Compressed sensing, square-root bottleneck, probabilistic sampling


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]> Performance and complexity analysis of infinity-norm sphere-decoding http://www.nari.ee.ethz.ch/commth/pubs/p/LinfSD_sub 2010-03-01 http://www.nari.ee.ethz.ch/commth/pubs/p/LinfSD_sub Authors Dominik Seethaler and Helmut Bölcskei

Reference

IEEE Transactions on Information Theory, Vol. 56, No. 3, pp. 1085-1105, Mar. 2010

DOI: 10.1109/TIT.2009.2039034

Abstract

Promising approaches for efficient detection in multiple-input multiple-output (MIMO) wireless systems are based on sphere-decoding (SD). The conventional (and optimum) norm that is used to conduct the tree traversal step in SD is the l2-norm. It was, however, recently observed that using the l-infinity-norm instead reduces the hardware complexity of SD considerably at only a marginal performance loss. These savings result from a reduction in the length of the critical path in the circuit and the silicon area required for metric computation, but are also, as observed previously through simulation results, a consequence of a reduction in the computational (i.e., algorithmic) complexity. The aim of this paper is an analytical performance and computational complexity analysis of l-infinity-norm SD. For independent and identically distributed (i.i.d.) Rayleigh fading MIMO channels, we show that l-infinity-norm SD achieves full diversity order with an asymptotic SNR gap, compared to l2-norm SD, that increases at most linearly in the number of receive antennas. Moreover, we provide a closed-form expression for the computational complexity of l-infinity-norm SD based on which we establish that its complexity scales exponentially in the system size. Finally, we characterize the tree pruning behavior of l-infinity-norm SD and show that it behaves fundamentally different from that of l2-norm SD.

Keywords

Algorithmic complexity, data detection, hardware complexity, infinity norm, maximum-likelihood, multiple-input multiple-output (MIMO) wireless


Download this document:

 

Copyright Notice: © 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

]]>