## Abstract

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 (log M + 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/M^{2}), while the SINR loss due to SDR approximation is at most (2 log M + O(1)) dB.

Original language | English (US) |
---|---|

Pages (from-to) | 3932-3943 |

Number of pages | 12 |

Journal | IEEE Transactions on Signal Processing |

Volume | 56 |

Issue number | 8 II |

DOIs | |

State | Published - Aug 2008 |

### Bibliographical note

Funding Information:Manuscript received August 29, 2007; revised March 7, 2008. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Andreas Jakobsson. The work of T.-H. Chang and C.-Y. Chi is supported by the National Science Council, R.O.C., under Grant NSC 96-2219-E-007-004. The work of Z.-Q. Luo is supported by the U.S. National Science Foundation, Grant DMS-0610037. Part of this work was presented at the Second IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, St. Thomas, U.S. Virgin Islands, December 12–14, 2007.

## Keywords

- Approximation bound
- Multicast
- Semidefinite relaxation (SDR)
- Transmit beamforming