SUBSET SELECTION AND THE CONE OF FACTOR-WIDTH-k MATRICES

We study the cone of factor-width-k matrices, where the factor width of a positive semidefinite matrix is defined as the smallest number k allowing it to be expressed as a sum of positive semidefinite matrices that are nonzero only on a single k\timesk principal submatrix. Two hierarchies of approximations are proposed for this cone. Some theoretical bounds to assess the quality of the new approximations are derived. We also use these approximations to build convex conic relaxations for the subset selection problem where one has to minimize \|b- Ax\|²₂ under the constraint that x has at most k nonzero components. Several numerical experiments are performed showing that some of these relaxations provide a good compromise between tightness and computational complexity and rank well compared to perspective-type relaxations.