Fair Column Subset Selection

• URL: http://arxiv.org/abs/2306.04489v4
• Date: Mon, 12 Aug 2024 16:54:55 GMT
• Title: Fair Column Subset Selection
• Authors: Antonis Matakos, Bruno Ordozgoiti, Suhas Thejaswi,
• Abstract summary: We consider a setting where the matrix rows are partitioned into two groups, and the goal is to choose a subset of columns that minimizes the maximum error reconstruction of both groups. In certain scenarios it is unavoidable to choose columns separately for each group, resulting in double the expected column count. We propose a deterministic leverage-score sampling strategy for the fair setting and show that sampling a column subset of minimum size becomes NP-hard in the presence of two groups.
• Score: 6.004035936737586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of column subset selection asks for a subset of columns from an input matrix such that the matrix can be reconstructed as accurately as possible within the span of the selected columns. A natural extension is to consider a setting where the matrix rows are partitioned into two groups, and the goal is to choose a subset of columns that minimizes the maximum reconstruction error of both groups, relative to their respective best rank-k approximation. Extending the known results of column subset selection to this fair setting is not straightforward: in certain scenarios it is unavoidable to choose columns separately for each group, resulting in double the expected column count. We propose a deterministic leverage-score sampling strategy for the fair setting and show that sampling a column subset of minimum size becomes NP-hard in the presence of two groups. Despite these negative results, we give an approximation algorithm that guarantees a solution within 1.5 times the optimal solution size. We also present practical heuristic algorithms based on rank-revealing QR factorization. Finally, we validate our methods through an extensive set of experiments using real-world data.

Related papers

• Column and row subset selection using nuclear scores: algorithms and theory for Nyström approximation, CUR decomposition, and graph Laplacian reduction [0.0]
  We develop unified methodologies for fast, efficient, and theoretically guaranteed column selection. First, we derive and implement a sparsity-exploiting deterministic algorithm applicable to tasks including kernel approximation and CUR decomposition. Next, we develop a matrix-free formalism relying on a randomization scheme satisfying guaranteed concentration bounds.
  arXiv  Detail & Related papers  (2024-07-01T18:10:19Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Achieving Long-term Fairness in Submodular Maximization through Randomization [16.33001220320682]
  It is important to implement fairness-aware algorithms when dealing with data items that may contain sensitive attributes like race or gender. We investigate the problem of maximizing a monotone submodular function while meeting group fairness constraints.
  arXiv  Detail & Related papers  (2023-04-10T16:39:19Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection [9.649210683629127]
  The problem of simultaneous column and row subset selection is addressed in this paper. An iterative approach is proposed to capture the most structural information of columns/rows via selecting a subset of actual columns/rows. We demonstrate the application of TWSP for joint channel and sensor selection in cognitive radio networks.
  arXiv  Detail & Related papers  (2021-06-13T13:16:15Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Self-Representation Based Unsupervised Exemplar Selection in a Union of Subspaces [27.22427926657327]
  We present a new exemplar selection model that searches for a subset that best reconstructs all data points as measured by the $ell_1$ norm of the representation coefficients. When the dataset is drawn from a union of independent subspaces, our method is able to select sufficiently many representatives from each subspace. We also develop an exemplar based subspace clustering method that is robust to imbalanced data and efficient for large scale data.
  arXiv  Detail & Related papers  (2020-06-07T19:43:33Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
  arXiv  Detail & Related papers  (2020-01-06T23:33:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.