Matrix Theory and Algorithms

Derniers papiers

• Riemannian Structure and Optimization for a Class of Low-Parametric Orthogonal Matrices

  Ali Aliev, Maxim Rakhuba · 24 septembre 2026

  In this paper, we are concerned with matrices formed by block-diagonal factors interleaved with fixed permutations -- a flexible family of structured matrices. This class has recently drawn interest in deep learning architectures for its balanced expressivity-efficiency trade-off, yet efficient comp…

• Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

  A. Afham · 4 septembre 2026

  The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly…

• Orthogonal Polynomial Approximation for Matrix Log Normalization in Global Covariance Pooling

  Md Rifat Ur Rahman, Md Raihan Khan, Md Sakib Hossain Shovon, Pietro Liò, Mohammad Ali Moni · 20 août 2026

  Global Covariance Pooling (GCP) improves deep networks by capturing second-order feature statistics, and is especially effective for fine-grained recognition. Because covariance matrices live on the Symmetric Positive Definite (SPD) manifold, a normalization step is required before the Euclidean cla…

• Matrix-free Neural Preconditioner for the Dirac Operator in Lattice Gauge Theory

  Yixuan Sun, Srinivas Eswar, Yin Lin, William Detmold, Phiala Shanahan, Xiaoye Li, Yang Liu, Prasanna Balaprakash · 11 août 2026

  Linear systems arise in generating samples and in calculating observables in lattice quantum chromodynamics~(QCD). Solving the Hermitian positive definite systems, which are sparse but ill-conditioned, involves using iterative methods, such as Conjugate Gradient (CG), which are time-consuming and co…

• Singular value soft-thresholding via the polar decomposition

  Stephen Becker · 27 juillet 2026

  Singular value soft-thresholding can be computed via a reduction to the matrix polar decomposition, which allows one to exploit GPU-friendly algorithms for computing the polar decomposition. Empirically, there is a significant speed-up on GPUs compared to the standard approach using the SVD. We leav…

• Totally Positive Matrices and the Highest-Order Coefficients of the Characteristic Polynomial

  Tiago Closs, Leandro Farina · 21 juillet 2026

  We investigate the extent to which totally positive matrices can be distinguished through the highest-order coefficients of their characteristic polynomials. To identify the most informative coefficients, we also employed neural-network classifiers together with feature-attribution methods. Using da…

• A Unified Framework for Diffusion Model Unlearning with f-Divergence

  Nicola Novello, Federico Fontana, Luigi Cinque, Deniz Gunduz, Andrea M. Tonello · 27 mai 2026

  Most existing methods for concept unlearning in text-to-image diffusion models minimize a mean squared error (MSE) loss between the denoiser outputs conditioned on a target and an anchor concept, which is implicitly the KL divergence between two Gaussians. We generalize this objective to any $f$-div…

• Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem

  Xiaozhi Liu, Mengmeng Song, Yong Xia · 26 mai 2026

  The computation of the dominant eigenpair for symmetric positive semidefinite matrices is fundamental in numerical optimization. This work shifts the paradigm from the classical Rayleigh quotient to an unconstrained difference formulation, whose global optimum recovers the dominant eigenpair. Within…

• Analysis of Nystrom method with sequential ridge leverage scores

  Daniele Calandriello, Alessandro Lazaric, Michal Valko · 23 avril 2026

  Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed matrix. The chosen su…

• Towards Universal Convergence of Backward Error in Linear System Solvers

  Micha{\l} Derezi\'nski, Yuji Nakatsukasa, Elizaveta Rebrova · 20 avril 2026

  The quest for an algorithm that solves an $n\times n$ linear system in $O(n^2)$ time complexity, or $O(n^2 \text{poly}(1/\epsilon))$ when solving up to $\epsilon$ relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science. There are two predominant p…

• Inductive Global and Local Manifold Approximation and Projection

  Jungeum Kim, Xiao Wang · 2 avril 2026

  Nonlinear dimensional reduction with the manifold assumption, often called manifold learning, has proven its usefulness in a wide range of high-dimensional data analysis. The significant impact of t-SNE and UMAP has catalyzed intense research interest, seeking further innovations toward visualizing …

• Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates

  Flavia Esposito, Andersen Ang · 24 mars 2026

  Low-rank optimization problems with sparse simplex constraints involve variables that must satisfy nonnegativity, sparsity, and sum-to-1 conditions, making their optimization particularly challenging due to the interplay between low-rank structures and constraints. These problems arise in various ap…

• Generalized Continuous-Time Models for Nesterov's Accelerated Gradient Methods

  Chanwoong Park, Youngchae Cho, Insoon Yang · 23 mars 2026

  Recent research has indicated a substantial rise in interest in understanding Nesterov's accelerated gradient methods via their continuous-time models. However, most existing studies focus on specific classes of Nesterov's methods, which hinders the attainment of an in-depth understanding and a unif…

• Using GPUs And LLMs Can Be Satisfying for Nonlinear Real Arithmetic Problems

  Christopher Brix, Julia Walczak, Nils Lommen, Thomas Noll · 10 mars 2026

  Solving quantifier-free non-linear real arithmetic (NRA) problems is a computationally hard task. To tackle this problem, prior work proposed a promising approach based on gradient descent. In this work, we extend their ideas and combine LLMs and GPU acceleration to obtain an efficient technique. We…

• Towards a Fairer Non-negative Matrix Factorization

  Lara Kassab, Erin George, Deanna Needell, Haowen Geng, Nika Jafar Nia, Aoxi Li · 26 février 2026

  There has been a recent critical need to study fairness and bias in machine learning (ML) algorithms. Since there is clearly no one-size-fits-all solution to fairness, ML methods should be developed alongside bias mitigation strategies that are practical and approachable to the practitioner. Motivat…

• New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results

  Francesco Orabona, Ryan D'Orazio · 22 janvier 2026

  The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions. The universality of the Polyak stepsize has also inspired many stochastic variants, with theoretical guarantees and strong empirical…

• torch-sla: Differentiable Sparse Linear Algebra with Adjoint Solvers and Sparse Tensor Parallelism for PyTorch

  Mingyuan Chi · 21 janvier 2026

  Industrial scientific computing predominantly uses sparse matrices to represent unstructured data -- finite element meshes, graphs, point clouds. We present \torchsla{}, an open-source PyTorch library that enables GPU-accelerated, scalable, and differentiable sparse linear algebra. The library addre…

• Nonlinear reconciliation: Error reduction theorems

  Lorenzo Nespoli, Anubhab Biswas, Roberto Rocchetta, Vasco Medici · 15 janvier 2026

  Forecast reconciliation, an ex-post technique applied to forecasts that must satisfy constraints, has been a prominent topic in the forecasting literature over the past two decades. Recently, several efforts have sought to extend reconciliation methods to the probabilistic settings. Nevertheless, fo…

• A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning

  Zechen Wu, Amy Greenwald, Ronald Parr · 27 novembre 2025

  In off-policy policy evaluation (OPE) tasks within reinforcement learning, Temporal Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Parti…

• Finite-dimensional approximations of push-forwards on locally analytic functionals

  Isao Ishikawa · 25 novembre 2025

  This paper develops a functional-analytic framework for approximating the push-forward induced by an analytic map from finitely many samples. Instead of working directly with the map, we study the push-forward on the space of locally analytic functionals and identify it, via the Fourier--Borel trans…

• Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs

  Zherui Yang, Zhehao Li, Kangbo Lyu, Yixuan Li, Tao Du, Ligang Liu · 3 novembre 2025

  The conjugate gradient solver (CG) is a prevalent method for solving symmetric and positive definite linear systems Ax=b, where effective preconditioners are crucial for fast convergence. Traditional preconditioners rely on prescribed algorithms to offer rigorous theoretical guarantees, while limiti…