Approximation Bounds for Semidefinite Relaxation of Max-Min-Fair Multicast Transmit Beamforming Problem

Consider a downlink multicast scenario where a base station equipped with multiple antennas wishes to simultaneously broadcast a number of signals to some given groups of users over a common bandwidth. The goal of the base station is to select appropriate beamforming vectors so as to maximize the mi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2008-08, Vol.56 (8), p.3932-3943
Main Authors: CHANG, Tsung-Hui, LUO, Zhi-Quan, CHI, Chong-Yung
Format: Article
Language:English
Subjects:
Algorithms
Antennas
Applied sciences
Approximation
Approximation algorithms
Approximation bound
Array signal processing
Bandwidth
Base stations
Beamforming
Broadcasting
Channels
Detection, estimation, filtering, equalization, prediction
Downlink
Exact sciences and technology
Information, signal and communications theory
Mathematical analysis
Miscellaneous
Multicast
Polynomials
semidefinite relaxation (SDR)
Signal and communications theory
Signal processing
Signal to noise ratio
Signal, noise
Stations
Studies
Telecommunications and information theory
Time measurement
transmit beamforming
Transmitting antennas
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a downlink multicast scenario where a base station equipped with multiple antennas wishes to simultaneously broadcast a number of signals to some given groups of users over a common bandwidth. The goal of the base station is to select appropriate beamforming vectors so as to maximize the minimum signal-to-interference-plus-noise ratio (SINR) among all users under a power budget constraint. Since this max-min-fair transmit beamforming problem is NP-hard in general, a randomized polynomial time approximation approach based on semidefinite relaxation (SDR) has been proposed recently where excellent performance in both simulated and measured wireless channels has been reported. This paper shows that the SDR-based approach can provide at least an O(1/M) approximation to the optimum solution, where M is the total number of users. This estimate implies that the SDR solution achieves an SINR that is at most (logM+O(1)) dB away from the highest possible value. The existence of such a data independent bound certifies the worst-case approximation quality of the SDR algorithm for any problem instance and any number of transmit antennas. For real-valued problems, the corresponding approximation ratio is shown to be O(1/M2), while the SINR loss due to SDR approximation is at most (2logM+O(1)) dB.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2008.921762