A Caltech Library Service

Optimization Algorithms in Wireless and Quantum Communications


Stojnic, Mihailo (2008) Optimization Algorithms in Wireless and Quantum Communications. Dissertation (Ph.D.), California Institute of Technology.


Since the first communication systems were developed, the scientific community has been witnessing attempts to increase the amount of information that can be transmitted. In the last 10--15 years there has been a tremendous amount of research towards developing multi-antenna systems which would hopefully provide high-data-rate transmissions. However, increasing the overall amount of transmitted information increases the complexity of the necessary signal processing. A large portion of this thesis deals with several important issues in signal processing of multi-antenna systems. In almost every particular case the goal is to develop a technique/algorithm so that the overall complexity of the signal processing is significantly decreased.

In the first part of the thesis a very important problem of signal detection in MIMO (multiple-input multiple-output) systems is considered. The problem is analyzed in two different scenarios: when the transmission medium (channel) 1) is known and 2) is unknown at the receiver. The former case is often called coherent and the later non-coherent MIMO detection. Both cases usually amount to solving highly complex NP-hard combinatorial optimization problems. For the coherent case we develop a significant improvement of the traditional sphere decoder algorithm commonly used for this type of detection. An interesting connection between the new improved algorithm and the H-infinity estimation theory is established, and the performance improvement over the standard sphere decoder is demonstrated. For the non-coherent case we develop a counterpart to the standard sphere decoder, the so-called out-sphere decoder. The complexity of the algorithm is viewed as a random variable; its expected value is analyzed and shown to be significantly smaller than the one of the overall exhaustive search. In the non-coherent case, in addition to the complexity analysis of the exact out-sphere decoder, we analyze the performance loss of a suboptimal technique. We show that only a moderate loss of a few dbs in power required at the transmitter will occur if a polynomial algorithm based on the semi-definite relaxation is used in place of any exact technique (which of course is not known to be polynomial).

In the second part of the thesis we consider a few problems that arise in wireless broadcast channels. Namely, we consider the problem of the information symbol vector design at the transmitter. A polynomial linear precoding technique is constructed. It enables achieving data rates very close to the ones achieved with DPC (dirty paper coding) technique. Additionally, for another suboptimal polynomial scheme (the so-called nulling and cancelling), we show that it asymptotically achieves the same data rate as the optimal, exponentially complex, DPC.

In the last part of the thesis we consider a quantum counterpart of the signal detection from classical communication. In quantum systems the signals are quantum states and the quantum detection problem amounts to designing measurement operators which have to satisfy certain quantum mechanics laws. A specific type of quantum detection called unambiguous detection, which has numerous applications including quantum filtering, has recently attracted a lot of attention in the research community. We develop a general framework for numerically solving this problem using the tools from the convex optimization theory. Furthermore, in the special case where the two quantum states are of rank 2, we construct an explicit analytical solution for the measurement operators.

At the end we would like to emphasize that the contribution of this thesis goes beyond the specific problems mentioned here. Most algorithmic optimization techniques developed in this paper are generally applicable. While it is a fact that our results were originally motivated by wireless and quantum communications applications, we believe that the developed techniques will find applications in many different areas where similar optimization problems appear.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:broadcast; optimization; quantum; wireless communications
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hassibi, Babak
Thesis Committee:
  • Hassibi, Babak (chair)
  • Bruck, Jehoshua
  • Vaidyanathan, P. P.
  • McEliece, Robert J.
  • Ho, Tracey C.
Defense Date:28 November 2007
Record Number:CaltechETD:etd-12032007-113628
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4747
Deposited By: Imported from ETD-db
Deposited On:05 Dec 2007
Last Modified:23 Jan 2019 22:24

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page