|Title||A bound on the minimum rank of solutions to sparse linear matrix equations|
|Publication Type||Conference Paper|
|Year of Publication||2016|
|Authors||Raphael Louca, Subhonmesh Bose, Eilyan Bitar|
|Conference Name||2016 American Control Conference (ACC)|
|Conference Location||Boston, MA, USA|
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.