Guessing Efficiently for Constrained Subspace Approximation

In this paper we study constrained subspace approximation problem. Given a set of n points a1,ldots,an in ℝd, the goal of the em subspace approximation problem is to find a k dimensional subspace that best approximates the input points. More precisely, for a given p≥ 1, we aim to minimize the pth power of the ℓp norm of the error vector (|a1-bmPa1|,ldots,|an-bmPan|), where bmP denotes the projection matrix onto the subspace and the norms are Euclidean. In constrained subspace approximation (CSA), we additionally have constraints on the projection matrix bmP. In its most general form, we require bmP to belong to a given subset S that is described explicitly or implicitly. We introduce a general framework for constrained subspace approximation. Our approach, that we term coreset-guess-solve, yields either (1+varepsilon)-multiplicative or varepsilon-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to it fair subspace approximation, k-means clustering, and projected non-negative matrix factorization, among others. Specifically, while we reconstruct the best known bounds for k-means clustering in Euclidean spaces, we improve the known results for the remainder of the problems.