INDEX CODING VIA RANK MINIMIZATION

Index codes reduce the number of bits broadcast by a wireless transmitter to a number of receivers with different demands and with side information. It is known that the problem of finding optimal linear index codes is NP-hard (a worst-case result). Many heuristic solutions based on graph coloring have been proposed. However, graph coloring is also a NP-hard problem, and it only gives an upper bound of the index coding. Motivated by a connection between index coding and rank minimization, this thesis investigates the performance of different heuristics based on rank minimization and matrix completion methods, such as alternating projections and alternating minimization, for constructing linear index codes over the reals. The underlying matrices representing an index coding problem have a special structure that makes celebrated methods, such as nuclear norm minimization, perform badly. The performance of different methods, such as alternating projections, directional alternating projections and alternating minimization are presented, through extensive simulation results on random instances of the index coding problem. This thesis makes the following contributions: 1) The proposed alternating projections method gives the best performance compared to other graph based algorithms in the literature. 2) This proposed method leads to up to 13% savings on average communication cost compared to the well know greedy graph coloring algorithm. 3) The thesis describes how the proposed methods can be used to construct linear network codes for non-multicast networks. Our computer code is available online.M.S. in Electrical Engineering, July 201