Spectral Analysis for Sparse Matrix Computation: Insights and Potential

• URL: http://arxiv.org/abs/2608.29362v1
• Date: Sat, 29 Aug 2026 16:50:03 GMT
• Title: Spectral Analysis for Sparse Matrix Computation: Insights and Potential
• Abstract summary: We show that spectral signatures uncover global structural characteristics that are not captured by conventional spatial statistics.<n>Experiments on incorporating spectral features into machine-learning-based SpMV format selection demonstrate the usefulness of such spectral analysis over a state-of-the-art spatial-only model.
• Score: 8.047900710704837
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Sparse computations are fundamental to scientific computing, graph analytics, and machine learning, yet their performance is highly sensitive to the diverse sparsity and patterns. This is because cache reuse, memory coalescing, and load balancing depend critically on the sparsity patterns. This work gives the first known exploration of the connections between sparse matrix computation and spectral analysis by treating sparse matrices as two-dimensional signals and analyzing their frequency-domain representations through Fast Fourier Transform. We show that spectral signatures uncover global structural characteristics that are not sufficiently captured by conventional spatial statistics and provide complementary information for understanding sparse computation performance. Experiments on incorporating spectral features into machine-learning-based SpMV format selection demonstrate the usefulness of such spectral analysis over a state-of-the-art spatial-only model. By uncovering the principled connections between spectral characteristics and sparse matrix computations, this work introduces a novel analytical perspective into sparse computation, and provides a new approach to enhancing the current sparse structure characterization and optimization. On pruned LLM decoding, adding spectral features improves kernel selection and yields 1.035--1.245$\times$ kernel speedups.

Related papers

• Improved large-scale graph learning through ridge spectral sparsification [65.84577791298442]
  We consider the problem of learning over the Laplacian L in a distributed streaming setting.<n>In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L.<n>We present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances.
  arXiv  Detail & Related papers  (2026-04-22T00:49:31Z)
• Learning to Discover Iterative Spectral Algorithms [46.39331984989963]
  AutoSpec is a neural network framework for discovering iterative spectral algorithms for large-scale numerical linear algebra.<n>We apply AutoSpec to discovering algorithms for representative numerical linear algebra tasks.<n>On real-world solvers, the learned procedures deliver orders-of-magnitude improvements in accuracy and/or reductions in count.
  arXiv  Detail & Related papers  (2026-02-10T08:39:59Z)
• Amortized Spectral Kernel Discovery via Prior-Data Fitted Network [0.0]
  We introduce an interpretability-driven framework for amortized spectral discovery from pre-trained PFNs with decoupled attention.<n>We propose decoder architectures that map PFN latents to explicit spectral density estimates and corresponding stationary kernels.<n>This yields orders-of-magnitude reductions in inference time compared to optimization-based baselines.
  arXiv  Detail & Related papers  (2026-01-29T13:51:26Z)
• Spectral Geometry for Deep Learning: Compression and Hallucination Detection via Random Matrix Theory [0.0]
  This thesis proposes a unified framework based on spectral geometry and random matrix theory to address both problems.<n>The first contribution, EigenTrack, is a real-time method for detecting hallucinations and out-of-distribution behavior in language and vision-language models.<n>The second contribution, RMT-KD, is a principled compression method that identifies informative spectral components.
  arXiv  Detail & Related papers  (2026-01-24T08:07:22Z)
• Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery [21.414505380263016]
  We focus on recovering the subspace spanned by the signals via spectral estimators.<n>Our main technical contribution is a precise characterization of the performance of spectral methods.<n>Our analysis unveils a phase transition phenomenon in which, as the sample complexity grows, eigenvalues escape from the bulk of the spectrum.
  arXiv  Detail & Related papers  (2025-02-03T18:08:30Z)
• Holistic Physics Solver: Learning PDEs in a Unified Spectral-Physical Space [54.13671100638092]
  Holistic Physics Mixer (HPM) is a framework for integrating spectral and physical information in a unified space.<n>We show that HPM consistently outperforms state-of-the-art methods in both accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2024-10-15T08:19:39Z)
• Datacube segmentation via Deep Spectral Clustering [76.48544221010424]
  Extended Vision techniques often pose a challenge in their interpretation. The huge dimensionality of data cube spectra poses a complex task in its statistical interpretation. In this paper, we explore the possibility of applying unsupervised clustering methods in encoded space. A statistical dimensional reduction is performed by an ad hoc trained (Variational) AutoEncoder, while the clustering process is performed by a (learnable) iterative K-Means clustering algorithm.
  arXiv  Detail & Related papers  (2024-01-31T09:31:28Z)
• Hodge-Aware Contrastive Learning [101.56637264703058]
  Simplicial complexes prove effective in modeling data with multiway dependencies. We develop a contrastive self-supervised learning approach for processing simplicial data.
  arXiv  Detail & Related papers  (2023-09-14T00:40:07Z)
• ESSAformer: Efficient Transformer for Hyperspectral Image Super-resolution [76.7408734079706]
  Single hyperspectral image super-resolution (single-HSI-SR) aims to restore a high-resolution hyperspectral image from a low-resolution observation. We propose ESSAformer, an ESSA attention-embedded Transformer network for single-HSI-SR with an iterative refining structure.
  arXiv  Detail & Related papers  (2023-07-26T07:45:14Z)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• SF-GRASS: Solver-Free Graph Spectral Sparsification [16.313489255657203]
  This work introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing techniques. We show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks.
  arXiv  Detail & Related papers  (2020-08-17T21:37:19Z)
• Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects [1.6752182911522515]
  This work presents a principled spectral clustering algorithm that exploits spectral properties of the similarity matrix associated with sampled points to regulate accuracy-efficiency trade-offs. The overarching goal of this work is to provide an improved baseline for future research directions to accelerate spectral clustering.
  arXiv  Detail & Related papers  (2020-06-25T15:10:56Z)

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.