Index coding and network coding via rank minimization

Xiao Huang, Salim El Rouayheb

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

20 Citations (Scopus)


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
Title of host publicationITW 2015 - 2015 IEEE Information Theory Workshop
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781467378529
Publication statusPublished - 17 Dec 2015
Externally publishedYes
EventIEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of
Duration: 11 Oct 201515 Oct 2015

Publication series

NameITW 2015 - 2015 IEEE Information Theory Workshop


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

ASJC Scopus subject areas

  • Information Systems


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

Cite this