A bound on the minimum rank of solutions to sparse linear matrix equations

Raphael Louca, Subhonmesh Bose, Eilyan Bitar

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

Abstract

We derive a new upper bound on the minimum rank of matrices belonging to an affine slice of the positive semidefinite cone, when the affine slice is defined according to a system of sparse linear matrix equations. It is shown that a feasible matrix whose rank is no greater than said bound can be computed in polynomial time. The bound depends on both the number of linear matrix equations and their underlying sparsity pattern. For certain problem families, this bound is shown to improve upon well known bounds in the literature. Several examples are provided to illustrate the efficacy of this bound.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6501-6506
Number of pages6
ISBN (Electronic)9781467386821
DOIs
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
Volume2016-July
ISSN (Print)0743-1619

Other

Other2016 American Control Conference, ACC 2016
CountryUnited States
CityBoston
Period7/6/167/8/16

Keywords

  • Chordal graphs
  • Rank minimization
  • Semidefinite programming
  • Sparse linear matrix equations

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A bound on the minimum rank of solutions to sparse linear matrix equations'. Together they form a unique fingerprint.

Cite this