Linear transceiver design for interference alignment: Complexity and computation

Meisam Razaviyayn, Maziar Sanjabi, Zhi-Quan Luo

Research output: Contribution to journalArticlepeer-review

100 Scopus citations


Consider a multiple input-multiple output (MIMO) interference channel where each transmitter and receiver are equipped with multiple antennas. An effective approach to practically achieving high system throughput is to deploy linear transceivers (or beamformers) that can optimally exploit the spatial characteristics of the channel. The recent work of Cadambe and Jafar (IEEE Trans. Inf. Theory, vol. 54, no. 8) suggests that optimal beamformers should maximize the total degrees of freedom and achieve interference alignment in the high signal-to-noise ratio (SNR) regime. In this paper we first consider the interference alignment problem without channel extension and prove that the problem of maximizing the total achieved degrees of freedom for a given MIMO interference channel is NP-hard. Furthermore, we show that even checking the achievability of a given tuple of degrees of freedom for all receivers is NP-hard when each receiver is equipped with at least three antennas. Interestingly, the same problem becomes polynomial time solvable when each transmit/receive node is equipped with no more than two antennas. We also propose a distributed algorithm for transmit covariance matrix design that does not require the DoF tuple preassignment, under the assumption that each receiver uses a linear minimum mean square error (MMSE) beamformer. The simulation results show that the proposed algorithm outperforms the existing interference alignment algorithms in terms of system throughput.

Original languageEnglish (US)
Article number6142087
Pages (from-to)2896-2910
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 2012

Bibliographical note

Funding Information:
Manuscript received August 07, 2010; revised August 26, 2011; accepted September 17, 2011. Date of publication January 31, 2012; date of current version April 17, 2012. This work was supported in part by the Army Research Office under Grant W911NF-09-1-0279, the National Science Foundation under Grant CMMI-0726336, and by a research gift from Huawei Technologies, Inc. The authors are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: meisam@ece.;; Communicated by S. Jafar, Associate Editor for Communications. Color versions of one or more of the figures in this paper are available online at Digital Object Identifier 10.1109/TIT.2012.2184909


  • Beamformer design
  • MIMO interference channel
  • complexity
  • interference alignment


Dive into the research topics of 'Linear transceiver design for interference alignment: Complexity and computation'. Together they form a unique fingerprint.

Cite this