Simple Randomized Rounding for Max-Min Eigenvalue Augmentation

We consider the max-min eigenvalue augmentation problem: given n × n symmetric positive semidefinite matrices M, A 1 , . . . , A m and a positive integer k < m, the goal is to choose a subset I ⊂ 1, . . . , m of cardinality at most k that maximizes the minimum eigenvalue of the matrix M + i∈I A i . The problem captures both the Bayesian E-optimal design and maximum algebraic connectivity augmentation problems. In contrast to the existing work, we do not assume that the augmentation matrices are rankone matrices, and we focus on the setting in which k < n. We show that a simple randomized rounding method provides a constant-factor approximation if the optimal increase is sufficiently large, specifically, if OPT -λ min (M ) = Ω(R ln k), where OPT is the optimal value, and R is the maximum trace of an augmentation matrix. To establish the guarantee, we derive a matrix concentration inequality that is of independent interest. The inequality can be interpreted as an intrinsic dimension analog of the matrix Chernoff inequality for the minimum eigenvalue of a sum of independent random positive semidefinite matrices; such an inequality has already been established for the maximum eigenvalue, but not for the minimum eigenvalue.