Maximizing the Minimum Eigenvalue in Constant Dimension

In an instance of the minimum eigenvalue problem, we are given a collection of n vectors v1,ldots, vn subset ℝd, and the goal is to pick a subset Bsubseteq [n] of given vectors to maximize the minimum eigenvalue of the matrix sumi∈ B vi vitop . Often, additional combinatorial constraints such as cardinality constraint left(|B|≤ kright) or matroid constraint (B is a basis of a matroid defined on [n]) must be satisfied by the chosen set of vectors. The minimum eigenvalue problem with matroid constraints models a wide variety of problems including the Santa Clause problem, the E-design problem, and the constructive Kadison-Singer problem. In this paper, we give a randomized algorithm that finds a set Bsubseteq [n] subject to any matroid constraint whose minimum eigenvalue is at least (1-ε) times the optimum, with high probability. The running time of the algorithm is Oleft( nO(dlog(d)/ε2)right). In particular, our results give a polynomial time asymptotic scheme when the dimension of the vectors is constant. Our algorithm uses a convex programming relaxation of the problem after guessing a rescaling which allows us to apply pipage rounding and matrix Chernoff inequalities to round to a good solution. The key new component is a structural lemma which enables us to "guess'' the appropriate rescaling, which could be of independent interest. Our approach generalizes the approximation guarantee to monotone, homogeneous functions and as such we can maximize det(sumi∈ B vi vi^top)1/d, or minimize any norm of the eigenvalues of the matrix left(sumi∈ B vi vi^topright)-1 , with the same running time under some mild assumptions. As a byproduct, we also get a simple algorithm for an algorithmic version of Kadison-Singer problem.