Index coding and network coding via rank minimization

Xiao Huang, Salim El Rouayheb

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations


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. We investigate the performance of different heuristics based on rank minimization and matrix completion methods for constructing linear index codes over the reals. As a summary of our results, the alternating projections method gives the best results in terms of minimizing the number of broadcast bits and convergence rate and leads to up to 13% savings in communication cost compared to graph coloring algorithms studied in the literature. Moreover, we describe how the proposed methods can be used to construct linear network codes for non-multicast networks.

Original languageEnglish (US)
Title of host publicationITW 2015 - 2015 IEEE Information Theory Workshop
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781467378529
StatePublished - Dec 17 2015
Externally publishedYes
EventIEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of
Duration: Oct 11 2015Oct 15 2015

Publication series

NameITW 2015 - 2015 IEEE Information Theory Workshop


OtherIEEE Information Theory Workshop, ITW 2015
Country/TerritoryKorea, Republic of
CityJeju Island

All Science Journal Classification (ASJC) codes

  • Information Systems


Dive into the research topics of 'Index coding and network coding via rank minimization'. Together they form a unique fingerprint.

Cite this