2026-08-17T16:56:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23406 2025-10-02T12:54:17Z ddc:004 open_access

Guessing Efficiently for Constrained Subspace Approximation Bhaskara, Aditya Mahabadi, Sepideh Pittu, Madhusudhan Reddy Vakilian, Ali Woodruff, David P. parameterized complexity low rank approximation fairness non-negative matrix factorization clustering In this paper we study constrained subspace approximation problem. Given a set of n points {a₁,…,a_n} in ℝ^d, the goal of the 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 (‖a₁-Pa₁‖,…,‖a_n-Pa_n‖), where P 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 P. In its most general form, we require P to belong to a given subset 𝒮 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+ε)-multiplicative or ε-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Bhaskara and Sepideh Mahabadi and Madhusudhan Reddy Pittu and Ali Vakilian and David P. Woodruff 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.29 urn:nbn:de:0030-drops-234068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode