Effective and Sparse Count-Sketch via k-means clustering

• URL: http://arxiv.org/abs/2011.12046v2
• Date: Thu, 26 Nov 2020 06:20:43 GMT
• Title: Effective and Sparse Count-Sketch via k-means clustering
• Authors: Yuhan Wang, Zijian Lei, Liang Lan
• Abstract summary: We propose to reduce the reconstruction error of count-sketch by using k-means clustering algorithm to obtain the low-dimensional sketched matrix. Our experimental results based on six real-life classification datasets have demonstrated that our proposed method achieves higher accuracy than the original count-sketch.
• Score: 17.26941311020711
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 than X while preserving most of its properties. Therefore, count-sketch is widely used for addressing high-dimensionality challenge in machine learning. However, there are two main limitations of count-sketch: (1) The sketching matrix used count-sketch is generated randomly which does not consider any intrinsic data properties of X. This data-oblivious matrix sketching method could produce a bad sketched matrix which will result in low accuracy for subsequent machine learning tasks (e.g.classification); (2) For highly sparse input data, count-sketch could produce a dense sketched data matrix. This dense sketch matrix could make the subsequent machine learning tasks more computationally expensive than on the original sparse data X. To address these two limitations, we first show an interesting connection between count-sketch and k-means clustering by analyzing the reconstruction error of the count-sketch method. Based on our analysis, we propose to reduce the reconstruction error of count-sketch by using k-means clustering algorithm to obtain the low-dimensional sketched matrix. In addition, we propose to solve k-mean clustering using gradient descent with -L1 ball projection to produce a sparse sketched matrix. Our experimental results based on six real-life classification datasets have demonstrated that our proposed method achieves higher accuracy than the original count-sketch and other popular matrix sketching algorithms. Our results also demonstrate that our method produces a sparser sketched data matrix than other methods and therefore the prediction cost of our method will be smaller than other matrix sketching methods.

Related papers

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning. We develop two randomized algorithms for its computation. We show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.
  arXiv  Detail & Related papers  (2024-02-13T00:02:05Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• 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)
• 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)
• Learning the Positions in CountSketch [51.15935547615698]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries. We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
  arXiv  Detail & Related papers  (2020-07-20T05:06:29Z)
• Localized sketching for matrix multiplication and ridge regression [29.61816941867831]
  We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching. We show that, under mild conditions, block diagonal sketching matrices require only O(stable rank / epsilon2) and $O( stat. dim. epsilon)$ total sample complexity for matrix multiplication and ridge regression.
  arXiv  Detail & Related papers  (2020-03-20T04:25:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

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.