Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing,

pp. 974-981, September 2016.

We consider the problem of minimizing a particular singular value of a matrix variable, which is then subject to some convex constraints. Convex heuristics for this problem are discussed, including some counter-intuitive results regarding which is best, which then provide upper bounds on the value of the problem. The use of polynomial optimization formulations is considered, particularly for obtaining lower bounds on the value of the problem.

We show that the main problem can also be formulated as an optimization problem with a bilinear matrix inequality (BMI), and discuss the use of this formulation.

This problem of minimizing the k-th singular value of a matrix is closely related to the problem of minimizing the k-th largest element of a vector, and we discuss that problem as well where appropriate.