On the complexity of leakage interference minimization for interference alignment

Ya Feng Liu; Yu Hong Dai; Zhi-Quan Luo

doi:10.1109/SPAWC.2011.5990455

On the complexity of leakage interference minimization for interference alignment

Ya Feng Liu, Yu Hong Dai, Zhi-Quan Luo

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

Abstract

For a general MIMO interference channel, we can determine the feasibility of linear interference alignment via minimizing the leakage interference. This paper gives a complete complexity characterization of the leakage interference minimization problem. It is shown that, when each transmitter (receiver) is equipped with at least three antennas and each receiver (transmitter) is equipped with at least two antennas, the problem of checking whether the interference in the network can be perfectly aligned is strongly NP-hard. Moreover, when each transmit/receive node is equipped with two or more antennas, leakage interference minimization can not be solved (even approximately) in polynomial time, unless P = NP.

Original language	English (US)
Title of host publication	2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011
Pages	471-475
Number of pages	5
DOIs	https://doi.org/10.1109/SPAWC.2011.5990455
State	Published - Sep 16 2011
Event	2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011 - San Francisco, CA, United States Duration: Jun 26 2011 → Jun 29 2011

Publication series

Name	IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC

Other

Other	2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011
Country/Territory	United States
City	San Francisco, CA
Period	6/26/11 → 6/29/11

Keywords

Complexity analysis
interference alignment
leakage interference minimization

Publisher link

10.1109/SPAWC.2011.5990455

Find It

Find It at U of M Libraries

Cite this

Liu, Y. F., Dai, Y. H., & Luo, Z-Q. (2011). On the complexity of leakage interference minimization for interference alignment. In 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011 (pp. 471-475). Article 5990455 (IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC). https://doi.org/10.1109/SPAWC.2011.5990455

On the complexity of leakage interference minimization for interference alignment. / Liu, Ya Feng; Dai, Yu Hong; Luo, Zhi-Quan.
2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011. 2011. p. 471-475 5990455 (IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Liu, YF, Dai, YH & Luo, Z-Q 2011, On the complexity of leakage interference minimization for interference alignment. in 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011., 5990455, IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC, pp. 471-475, 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011, San Francisco, CA, United States, 6/26/11. https://doi.org/10.1109/SPAWC.2011.5990455

@inproceedings{a839ba45fe1a44ac86506c29ae76589c,

title = "On the complexity of leakage interference minimization for interference alignment",

abstract = "For a general MIMO interference channel, we can determine the feasibility of linear interference alignment via minimizing the leakage interference. This paper gives a complete complexity characterization of the leakage interference minimization problem. It is shown that, when each transmitter (receiver) is equipped with at least three antennas and each receiver (transmitter) is equipped with at least two antennas, the problem of checking whether the interference in the network can be perfectly aligned is strongly NP-hard. Moreover, when each transmit/receive node is equipped with two or more antennas, leakage interference minimization can not be solved (even approximately) in polynomial time, unless P = NP.",

keywords = "Complexity analysis, interference alignment, leakage interference minimization",

author = "Liu, {Ya Feng} and Dai, {Yu Hong} and Zhi-Quan Luo",

year = "2011",

month = sep,

day = "16",

doi = "10.1109/SPAWC.2011.5990455",

language = "English (US)",

isbn = "9781424493326",

series = "IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC",

pages = "471--475",

booktitle = "2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011",

note = "2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011 ; Conference date: 26-06-2011 Through 29-06-2011",

}

TY - GEN

T1 - On the complexity of leakage interference minimization for interference alignment

AU - Liu, Ya Feng

AU - Dai, Yu Hong

AU - Luo, Zhi-Quan

PY - 2011/9/16

Y1 - 2011/9/16

N2 - For a general MIMO interference channel, we can determine the feasibility of linear interference alignment via minimizing the leakage interference. This paper gives a complete complexity characterization of the leakage interference minimization problem. It is shown that, when each transmitter (receiver) is equipped with at least three antennas and each receiver (transmitter) is equipped with at least two antennas, the problem of checking whether the interference in the network can be perfectly aligned is strongly NP-hard. Moreover, when each transmit/receive node is equipped with two or more antennas, leakage interference minimization can not be solved (even approximately) in polynomial time, unless P = NP.

AB - For a general MIMO interference channel, we can determine the feasibility of linear interference alignment via minimizing the leakage interference. This paper gives a complete complexity characterization of the leakage interference minimization problem. It is shown that, when each transmitter (receiver) is equipped with at least three antennas and each receiver (transmitter) is equipped with at least two antennas, the problem of checking whether the interference in the network can be perfectly aligned is strongly NP-hard. Moreover, when each transmit/receive node is equipped with two or more antennas, leakage interference minimization can not be solved (even approximately) in polynomial time, unless P = NP.

KW - Complexity analysis

KW - interference alignment

KW - leakage interference minimization

UR - http://www.scopus.com/inward/record.url?scp=80052655079&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052655079&partnerID=8YFLogxK

U2 - 10.1109/SPAWC.2011.5990455

DO - 10.1109/SPAWC.2011.5990455

M3 - Conference contribution

AN - SCOPUS:80052655079

SN - 9781424493326

T3 - IEEE Workshop on Signal Processing Advances in Wireless Communications, SPAWC

SP - 471

EP - 475

BT - 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011

T2 - 2011 IEEE 12th International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2011

Y2 - 26 June 2011 through 29 June 2011

ER -

On the complexity of leakage interference minimization for interference alignment

Abstract

Publication series

Other

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this