Fast Swap-Based Element Selection for Multiplication-Free Dimension Reduction

• URL: http://arxiv.org/abs/2602.13532v1
• Date: Sat, 14 Feb 2026 00:11:43 GMT
• Title: Fast Swap-Based Element Selection for Multiplication-Free Dimension Reduction
• Authors: Nobutaka Ono,
• Abstract summary: We propose a fast algorithm for element selection that produces a dimension-reduced vector by simply selecting a subset of elements from the input.<n>Experiments on MNIST handwritten-digit images demonstrate the effectiveness of the proposed method.
• Score: 8.81314696375596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a fast algorithm for element selection, a multiplication-free form of dimension reduction that produces a dimension-reduced vector by simply selecting a subset of elements from the input. Dimension reduction is a fundamental technique for reducing unnecessary model parameters, mitigating overfitting, and accelerating training and inference. A standard approach is principal component analysis (PCA), but PCA relies on matrix multiplications; on resource-constrained systems, the multiplication count itself can become a bottleneck. Element selection eliminates this cost because the reduction consists only of selecting elements, and thus the key challenge is to determine which elements should be retained. We evaluate a candidate subset through the minimum mean-squared error of linear regression that predicts a target vector from the selected elements, where the target may be, for example, a one-hot label vector in classification. When an explicit target is unavailable, the input itself can be used as the target, yielding a reconstruction-based criterion. The resulting optimization is combinatorial, and exhaustive search is impractical. To address this, we derive an efficient formula for the objective change caused by swapping a selected and an unselected element, using the matrix inversion lemma, and we perform a swap-based local search that repeatedly applies objective-decreasing swaps until no further improvement is possible. Experiments on MNIST handwritten-digit images demonstrate the effectiveness of the proposed method.

Related papers

• Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering [9.46982964997944]
  We learn a reordering network by minimizing triangular factors of the reordered matrix to approximate the exact number of fill-ins.<n>For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective.<n> Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-11-12T08:06:33Z)
• Novel Pivoted Cholesky Decompositions for Efficient Gaussian Process Inference [2.8391355909797644]
  Cholesky decomposition is a fundamental tool for solving linear systems with symmetric and positive definite matrices.<n>We introduce a pivoting strategy that iteratively permutes the rows and columns of the matrix.<n>Our results show that the proposed selection strategies are either on par or, in most cases, outperform traditional baselines.
  arXiv  Detail & Related papers  (2025-07-28T10:01:43Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  We introduce a novel global optimization method for align partially overlapping point sets.<n>Our method exhibits superior robustness to non-rigid deformations, positional noise and outliers.<n> Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to outliers.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Causal Unit Selection using Tractable Arithmetic Circuits [12.223629720083148]
  We introduce a new approach for unit selection that is not necessarily limited by the constrained treewidth. This is done through compiling the meta-model into a special class of tractable arithmetic circuits.
  arXiv  Detail & Related papers  (2024-04-10T02:02:34Z)
• Feature Selection as Deep Sequential Generative Learning [50.00973409680637]
  We develop a deep variational transformer model over a joint of sequential reconstruction, variational, and performance evaluator losses. Our model can distill feature selection knowledge and learn a continuous embedding space to map feature selection decision sequences into embedding vectors associated with utility scores.
  arXiv  Detail & Related papers  (2024-03-06T16:31:56Z)
• Numerical Optimizations for Weighted Low-rank Estimation on Language Model [73.12941276331316]
  Singular value decomposition (SVD) is one of the most popular compression methods that approximates a target matrix with smaller matrices. Standard SVD treats the parameters within the matrix with equal importance, which is a simple but unrealistic assumption. We show that our method can perform better than current SOTA methods in neural-based language models.
  arXiv  Detail & Related papers  (2022-11-02T00:58:02Z)
• Subspace Learning for Feature Selection via Rank Revealing QR Factorization: Unsupervised and Hybrid Approaches with Non-negative Matrix Factorization and Evolutionary Algorithm [0.0]
  rank revealing QR (RRQR) factorization is leveraged in obtaining the most informative features as a novel unsupervised feature selection technique. A hybrid feature selection algorithm is proposed by coupling RRQR, as a filter-based technique, and a Genetic algorithm as a wrapper-based technique. The proposed algorithm shows to be dependable and robust when compared against state-of-the-art feature selection algorithms in supervised, unsupervised, and semi-supervised settings.
  arXiv  Detail & Related papers  (2022-10-02T04:04:47Z)
• 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)
• Metalearning: Sparse Variable-Structure Automata [0.0]
  We propose a metalearning approach to increase the number of basis vectors used in dynamic sparse coding vectors on the fly. An actor-critic algorithm is deployed to automatically choose an appropriate dimension for feature regarding the required level of accuracy.
  arXiv  Detail & Related papers  (2021-01-30T21:32:23Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.