A Distance-preserving Matrix Sketch
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.
Code (1)
Tasks
Clusteringfeature selectionVisual ReasoningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
In this note we illustrate how common matrix approximation methods, such as random projection and random sampling, yield projection-cost-preserving sketches, as introduced in [FSS13, CEM+15]. A projection-cost-preserving…
Effective and Sparse Count-Sketch via k-means clustering
Count-sketch is a popular matrix sketching algorithm that can produce a sketch of an input data matrix X in O(nnz(X))time where nnz(X) denotes the number of non-zero entries in X. The sketched matrix will be much smaller…
BIG-bench Machine LearningClusteringFilter Sketch for Network Pruning
We propose a novel network pruning approach by information preserving of pre-trained network weights (filters). Network pruning with the information preserving is formulated as a matrix sketch problem, which is efficient…
Network PruningNodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching
Embeddings have become a key paradigm to learn graph represen-tations and facilitate downstream graph analysis tasks. Existinggraph embedding techniques either sample a large number of nodepairs from a graph to learn nod…
Streaming Binary Sketching based on Subspace Tracking and Diagonal Uniformization
In this paper, we address the problem of learning compact similarity-preserving embeddings for massive high-dimensional streams of data in order to perform efficient similarity search. We present a new online method for …