Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection

• URL: http://arxiv.org/abs/2106.06983v1
• Date: Sun, 13 Jun 2021 13:16:15 GMT
• Title: Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection
• Authors: Ashkan Esmaeili, Mohsen Joneidi, Mehrdad Salimitari, Umar Khalid, and Nazanin Rahnavard
• Abstract summary: 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.
• Score: 9.649210683629127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of simultaneous column and row subset selection is addressed in this paper. The column space and row space of a matrix are spanned by its left and right singular vectors, respectively. However, the singular vectors are not within actual columns/rows of the matrix. 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. This algorithm is referred to as two-way spectrum pursuit (TWSP) which provides us with an accurate solution for the CUR matrix decomposition. TWSP is applicable in a wide range of applications since it enjoys a linear complexity w.r.t. number of original columns/rows. We demonstrated the application of TWSP for joint channel and sensor selection in cognitive radio networks, informative users and contents detection, and efficient supervised data reduction.

Related papers

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Wave-informed dictionary learning for high-resolution imaging in complex media [0.0]
  We propose an approach for imaging in scattering media when large and diverse data sets are available. We show that the proposed approach is able to provide images in complex media whose resolution is that of a homogeneous medium.
  arXiv  Detail & Related papers  (2023-09-22T01:28:15Z)
• Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model [13.082805815235975]
  We introduce a novel framework called Mode-wise Principal Subspace Pursuit (MOP-UP) to extract hidden variations in both the row and column dimensions for matrix data. The effectiveness and practical merits of the proposed framework are demonstrated through experiments on both simulated and real datasets.
  arXiv  Detail & Related papers  (2023-07-02T13:59:47Z)
• Fair Column Subset Selection [6.004035936737586]
  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.
  arXiv  Detail & Related papers  (2023-06-07T15:00:38Z)
• A network community detection method with integration of data from multiple layers and node attributes [0.0]
  We suggest a simple way of representing network data in a data matrix where rows correspond to the nodes, and columns correspond to the data items. For compressing a data matrix, we suggest to extend so called regular decomposition method for non-square matrices. We illustrate our method with synthetic power-law graphs and two real networks: an Internet autonomous systems graph and a world airline graph.
  arXiv  Detail & Related papers  (2023-05-22T13:15:36Z)
• Generalized Leverage Scores: Geometric Interpretation and Applications [15.86621510551207]
  We extend the definition of leverage scores to relate the columns of a matrix to arbitrary subsets of singular vectors. We employ this result to design approximation algorithms with provable guarantees for two well-known problems.
  arXiv  Detail & Related papers  (2022-06-16T10:14:08Z)
• Dual-Flattening Transformers through Decomposed Row and Column Queries for Semantic Segmentation [50.321277476317974]
  We propose a Dual-Flattening Transformer (DFlatFormer) to enable high-resolution output. Experiments on ADE20K and Cityscapes datasets demonstrate the superiority of the proposed dual-flattening transformer architecture.
  arXiv  Detail & Related papers  (2022-01-22T22:38:15Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)
• 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)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• 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)

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.