Joint user grouping and linear virtual beamforming: Complexity, algorithms and approximation bounds

Mingyi Hong, Zi Xu, Meisam Razaviyayn, Zhi-Quan Luo

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In a wireless system with a large number of distributed nodes, the quality of communication can be greatly improved by pooling the nodes to perform joint transmission/reception. In this paper, we consider the problem of optimally selecting a subset of nodes from potentially a large number of candidates to form a virtual multi-antenna system, while at the same time designing their joint linear transmission strategies. We focus on two specific application scenarios: 1) multiple single antenna transmitters cooperatively transmit to a receiver; 2) a single transmitter transmits to a receiver with the help of a number of cooperative relays. We formulate the joint node selection and beamforming problems as cardinality constrained optimization problems with both discrete variables (used for selecting cooperative nodes) and continuous variables (used for designing beamformers). For each application scenario, we first characterize the computational complexity of the joint optimization problem, and then propose novel semi-definite relaxation (SDR) techniques to obtain approximate solutions. We show that the new SDR algorithms have a guaranteed approximation performance in terms of the gap to global optimality, regardless of channel realizations. The effectiveness of the proposed algorithms is demonstrated via numerical experiments.

Original languageEnglish (US)
Article number6601768
Pages (from-to)2013-2027
Number of pages15
JournalIEEE Journal on Selected Areas in Communications
Issue number10
StatePublished - 2013


  • Approximation Bounds
  • Beamforming
  • Cardinality Constrained Quadratic Program
  • Computational Complexity
  • Semi-definite Relaxation
  • User Grouping
  • Virtual Multi-antenna Systems


Dive into the research topics of 'Joint user grouping and linear virtual beamforming: Complexity, algorithms and approximation bounds'. Together they form a unique fingerprint.

Cite this