A Distance-preserving Matrix Sketch

• URL: http://arxiv.org/abs/2009.03979v3
• Date: Fri, 19 Nov 2021 06:39:11 GMT
• Title: A Distance-preserving Matrix Sketch
• Authors: Leland Wilkinson, Hengrui Luo
• Abstract summary: We introduce two new algorithms that respectively select a subset of rows and columns of a rectangular matrix. This selection is designed to preserve relative distances as closely as possible. We compare our matrix sketch to more traditional alternatives on a variety of artificial and real datasets.
• Score: 0.7734726150561086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Visualizing very large matrices involves many formidable problems. Various popular solutions to these problems involve sampling, clustering, projection, or feature selection to reduce the size and complexity of the original task. An important aspect of these methods is how to preserve relative distances between points in the higher-dimensional space after reducing rows and columns to fit in a lower dimensional space. This aspect is important because conclusions based on faulty visual reasoning can be harmful. Judging dissimilar points as similar or similar points as dissimilar on the basis of a visualization can lead to false conclusions. To ameliorate this bias and to make visualizations of very large datasets feasible, we introduce two new algorithms that respectively select a subset of rows and columns of a rectangular matrix. This selection is designed to preserve relative distances as closely as possible. We compare our matrix sketch to more traditional alternatives on a variety of artificial and real datasets.

Related papers

• Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein [56.62376364594194]
  Unsupervised learning aims to capture the underlying structure of potentially large and high-dimensional datasets. In this work, we revisit these approaches under the lens of optimal transport and exhibit relationships with the Gromov-Wasserstein problem. This unveils a new general framework, called distributional reduction, that recovers DR and clustering as special cases and allows addressing them jointly within a single optimization problem.
  arXiv  Detail & Related papers  (2024-02-03T19:00:19Z)
• Fair Recommendation by Geometric Interpretation and Analysis of Matrix Factorization [4.658166900129066]
  Matrix factorization-based recommender system is in effect an angle preserving dimensionality reduction technique. We reformulate the original angle preserving dimensionality reduction problem into a distance preserving dimensionality reduction problem. We show that the geometric shape of input data of recommender system in its original higher dimension are distributed on co-centric circles with interesting properties.
  arXiv  Detail & Related papers  (2023-01-10T05:30:46Z)
• 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)
• Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
  We propose a novel unsupervised multi-view feature selection model based on graph learning. The contributions are threefold: (1) during the feature selection procedure, the consensus similarity graph shared by different views is learned. Experiments on various datasets demonstrate the superiority of the proposed method compared with the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-04-11T03:25:25Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  We show how to design learned sketches for the Hessian in the context of second order methods. We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems.
  arXiv  Detail & Related papers  (2021-02-24T14:50:59Z)
• Multi-point dimensionality reduction to improve projection layout reliability [77.34726150561087]
  In ordinary Dimensionality Reduction (DR), each data instance in an m-dimensional space (original space) is mapped to one point in a d-dimensional space (visual space) Our solution, named Red Gray Plus, is built upon and extends a combination of ordinary DR and graph drawing techniques.
  arXiv  Detail & Related papers  (2021-01-15T17:17:02Z)
• 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)
• Adaptive Graph-based Generalized Regression Model for Unsupervised Feature Selection [11.214334712819396]
  How to select the uncorrelated and discriminative features is the key problem of unsupervised feature selection. We present a novel generalized regression model imposed by an uncorrelated constraint and the $ell_2,1$-norm regularization. It can simultaneously select the uncorrelated and discriminative features as well as reduce the variance of these data points belonging to the same neighborhood.
  arXiv  Detail & Related papers  (2020-12-27T09:07:26Z)
• Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares [22.679160149512377]
  Nonnegative least squares problems with multiple right-hand sides (MNNLS) arise in models that rely on additive linear combinations. We introduce a novel formulation for sparse MNNLS, with a matrix-wise sparsity constraint. We show that our proposed two-step approach provides more accurate results than state-of-the-art sparse codings applied both column-wise and globally.
  arXiv  Detail & Related papers  (2020-11-22T17:21:16Z)
• Projection techniques to update the truncated SVD of evolving matrices [17.22107982549168]
  This paper considers the problem of updating the rank-k truncated Singular Value Decomposition (SVD) of matrices subject to the addition of new rows and/or columns over time. The proposed framework is purely algebraic and targets general updating problems. Results on matrices from real applications suggest that the proposed algorithm can lead to higher accuracy.
  arXiv  Detail & Related papers  (2020-10-13T13:46:08Z)

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.