Tootfinder

Basis pursuit by inconsistent alternating projections
Roger Behling, Yunier Bello-Cruz, Luiz-Rafael Santos, Paulo J. S. Silva
https://arxiv.org/abs/2508.15026 https://

Basis pursuit by inconsistent alternating projections
Basis pursuit is the problem of finding a vector with smallest $\ell_1$-norm among the solutions of a given linear system of equations. It is a famous convex relaxation of what the literature refers to as sparse affine feasibility problem, in which sparse solutions to underdetermined systems are sought. In addition to enjoying convexity, the basis pursuit can be trivially rewritten as a linear program, and thus standard tools in linear programming apply for solving it. In turn, we tackle the …

Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
Junqing Lin, Jingwei Sun, Mingge Lu, Guangzhong Sun
https://arxiv.org/abs/2507.12205

Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
Sparse Matrix-Vector Multiplication (SpMV) has become a critical performance bottleneck in the local deployment of sparse Large Language Models (LLMs), where inference predominantly operates on workloads during the decoder phase with a batch size of one. Existing SpMV kernels and sparse matrix formats, originally designed for scientific computing, fail to exploit the unique structure patterns inherent in sparse LLMs, resulting in suboptimal performance and excessive storage overhead. This paper…

Quantum Algorithms for Projection-Free Sparse Convex Optimization
Jianhao He, John C. S. Lui
https://arxiv.org/abs/2507.08543 https://

Quantum Algorithms for Projection-Free Sparse Convex Optimization
This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain $\mathcal{D} \subset \mathbb{R}^d$, we propose two quantum algorithms for sparse constraints that finds a $\varepsilon$-optimal solution with the query complexity of $O(\sqrt{d}/\varepsilon)$ and $O(1/\varepsilon)$ by using the function value oracle, reducing a fa…

Is Sparse Matrix Reordering Effective for Sparse Matrix-Vector Multiplication?
Omid Asudeh, Sina Mahdipour Saravani, Gerald Sabin, Fabrice Rastello, P Sadayappan
https://arxiv.org/abs/2506.10356

Is Sparse Matrix Reordering Effective for Sparse Matrix-Vector Multiplication?
This work evaluates the impact of sparse matrix reordering on the performance of sparse matrix-vector multiplication across different multicore CPU platforms. Reordering can significantly enhance performance by optimizing the non-zero element patterns to reduce total data movement and improve the load-balancing. We examine how these gains vary over different CPUs for different reordering strategies, focusing on both sequential and parallel execution. We address multiple aspects, including appro…

High-dimensional regression with outcomes of mixed-type using the multivariate spike-and-slab LASSO
Soham Ghosh, Sameer K. Deshpande
https://arxiv.org/abs/2506.13007

High-dimensional regression with outcomes of mixed-type using the multivariate spike-and-slab LASSO
We consider a high-dimensional multi-outcome regression in which $q,$ possibly dependent, binary and continuous outcomes are regressed onto $p$ covariates. We model the observed outcome vector as a partially observed latent realization from a multivariate linear regression model. Our goal is to estimate simultaneously a sparse matrix ($B$) of latent regression coefficients (i.e., partial covariate effects) and a sparse latent residual precision matrix ($Ω$), which induces partial correlations …

Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers
Josep Plana-Riu, F. Xavier Trias, \`Adel Alsalti-Baldellou, Xavier \'Alvarez-Farr\'e, Guillem Colomer, Assensi Oliva
https://arxiv.org/abs/2508.06710

Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers
Computational Fluid Dynamics (CFD) simulations are often constrained by the memory-bound nature of sparse matrix-vector operations, which eventually limits performance on modern high-performance computing (HPC) systems. This work introduces a novel approach to increase arithmetic intensity in CFD by leveraging repeated matrix block structures. The method transforms the conventional sparse matrix-vector product (SpMV) into a sparse matrix-matrix product (SpMM), enabling simultaneous processing o…

Matrix Weighted $L^p$ Estimates in the Nonhomogeneous Setting
Fernando Benito-de la Cigo\~na, Tainara Borges, Francesco D'Emilio, Marcus Pasquariello, Nathan A. Wagner
https://arxiv.org/abs/2506.15570

Matrix Weighted $L^p$ Estimates in the Nonhomogeneous Setting
We establish a modified pointwise convex body domination for vector-valued Haar shifts in the nonhomogeneous setting, strengthening and extending the scalar case developed in arXiv:2309.13943. Moreover, we identify a subclass of shifts, called $L^1$-normalized, for which the standard convex body domination holds without requiring any regularity assumption on the measure. Finally, we extend the best-known matrix weighted $L^p$ estimates for sparse forms to the nonhomogeneous setting. The key dif…

Polynomial Lattices for the BIKE Cryptosystem
Michael Schaller
https://arxiv.org/abs/2507.23641 https://arxiv.org/pdf/2507.23641

Polynomial Lattices for the BIKE Cryptosystem
In this paper we introduce a rank $2$ lattice over a polynomial ring arising from the public key of the BIKE cryptosystem \cite{aragon2022bike}. The secret key is a sparse vector in this lattice. We study properties of this lattice and generalize the recovery of weak keys from \cite{BardetDLO16}. In particular, we show that they implicitly solved a shortest vector problem in the lattice we constructed. Rather than finding only a shortest vector, we obtain a reduced basis of the lattice which ma…

Latent confounding in high-dimensional nonlinear models
Yuhao Wang, Rajen Shah
https://arxiv.org/abs/2508.06274 https://arxiv.org/pdf/2508.06274

Latent confounding in high-dimensional nonlinear models
We consider the the problem of identifying causal effects given a high-dimensional treatment vector in the presence of low-dimensional latent confounders. We assume a parametric structural causal model in which the outcome is permitted to depend on a sparse linear combination of the treatment vector and confounders nonlinearly. We consider a generalisation of the LAVA estimator of Chernozhukov et al. [2017] for estimating the treatment effects and show that under the so-called `dense confoundin…

Robust Distributed Phase Retrieval for Multi-View Compressive Networked Sensing With Outliers
Ming-Hsun Yang
https://arxiv.org/abs/2505.24651 https://

Robust Distributed Phase Retrieval for Multi-View Compressive Networked Sensing With Outliers
This work examines the multi-view compressive phase retrieval problem in a distributed sensor network, where each sensor device, limited by storage and sensing capabilities, can access only intensity measurements from an unknown part of the global sparse vector. The goal is to enable each sensor to recover its observable sparse signal when measurements are corrupted by outliers. To achieve reliable local signal recovery with limited data access, we propose a distributed reconstruction algorithm…

ViLLA-MMBench: A Unified Benchmark Suite for LLM-Augmented Multimodal Movie Recommendation
Fatemeh Nazary, Ali Tourani, Yashar Deldjoo, Tommaso Di Noia
https://arxiv.org/abs/2508.04206

ViLLA-MMBench: A Unified Benchmark Suite for LLM-Augmented Multimodal Movie Recommendation
Recommending long-form video content demands joint modeling of visual, audio, and textual modalities, yet most benchmarks address only raw features or narrow fusion. We present ViLLA-MMBench, a reproducible, extensible benchmark for LLM-augmented multimodal movie recommendation. Built on MovieLens and MMTF-14K, it aligns dense item embeddings from three modalities: audio (block-level, i-vector), visual (CNN, AVF), and text. Missing or sparse metadata is automatically enriched using state-of-the…

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu
https://arxiv.org/abs/2508.02182

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k$-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive applicat…

Communication-Efficient Publication of Sparse Vectors under Differential Privacy
Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya
https://arxiv.org/abs/2506.20234

Communication-Efficient Publication of Sparse Vectors under Differential Privacy
In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with $N$ users, $n$ columns, and $m$ nonzero …

Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation
Abdullah Al Raqibul Islam, Helen Xu, Dong Dai, Ayd{\i}n Bulu\c{c}
https://arxiv.org/abs/2507.21253

Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation
Sparse matrix-sparse matrix multiplication (SpGEMM) is a key kernel in many scientific applications and graph workloads. Unfortunately, SpGEMM is bottlenecked by data movement due to its irregular memory access patterns. Significant work has been devoted to developing row reordering schemes towards improving locality in sparse operations, but prior studies mostly focus on the case of sparse-matrix vector multiplication (SpMV). In this paper, we address these issues with hierarchical clusterin…

Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Cameron Musco, Christopher Musco, David Persson
https://arxiv.org/abs/2507.19290

Query Efficient Structured Matrix Learning
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix $A$ given access to matrix-vector product (matvec) queries of the form $x \rightarrow Ax$ and $x \rightarrow A^Tx$. This problem is of central importance to algorithms across scientific computing and machine learning, with applications to fast multiplication and inversion for structured matrices, building preconditioners for first-order optimization, and as a model for differential …