The Greedy Algorithm for Determinant Maximization

Given a set of n vectors in R^d, the goal of the determinant maximization problem is to pick k vectors with the maximum volume. The most natural algorithm is to pick the k vectors by performing the Gram-Schmidt process greedily: keep choosing the vector with the largest perpendicular component to our current solution. This is known to have a k! approximation factor. Our main result is a local optimality property for the greedy algorithm using elementary linear algebra: swapping a single point from the greedy solution with a vector that was not picked can increase the volume by a factor of at most 1+sqrt(k). This is tight up to the additive constant 1. This leads to two interesting consequences: we obtain near optimal guarantees in the composable coreset setting and recover the original k! result in the offline setting.