Sketching Low-Rank Plus Diagonal Matrices

Andres Fernandez, Felix Dangel, Philipp Hennig, Frank Schneider · 2025

Read Sketching Low-Rank Plus Diagonal Matrices by Andres Fernandez, Felix Dangel, Philipp Hennig, Frank Schneider (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-23587.txt.

Introduction

Big linear operators in science and machine learning are often reachable only through costly products with vectors. Andres Fernandez and 3 co-authors introduce SKETCHLORD, a sketching method that estimates two structures at once: a low-rank part and a diagonal part. Older sketching tools recover one or the other, and the forced choice leaves error behind. Their target class, low-rank plus diagonal operators, covers cases like the deep learning Hessian.

Joint estimation beat not only single-structure fits but also both orders of doing the two fits in sequence. The team recasts the method as a convex optimization problem, which makes it scalable. Tests on synthetic matrices confirm it recovers the true structure with high fidelity.

Catalog record

CREATORAndres Fernandez, Felix Dangel, Philipp Hennig, Frank Schneider
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-23587

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sketching Low-Rank Plus Diagonal Matrices Andres Fernandez, Felix Dangel, Philipp Hennig, Frank Schneider Abstract Many relevant machine learning and scientific computing tasks involve high-dimensional linear operators accessible only via costly matrix-vector products. In this context, recent advances in sketched methods have enabled the construction of either low-rank or diagonal approximations from few matrix-vector products. This provides great speedup and scalability, but approximation errors arise due to the assumed simpler structure. This work introduces Sketchlord , a method that simultaneously estimates both low-rank and diagonal components, targeting the broader class of Low-Rank plus Diagonal ( LoRD ) linear operators. We demonstrate theoretically and empirically that this joint estimation is superior also to any sequential variant (diagonal-then-low-rank or low-rank-then-diagonal). Then, we cast Sketchlord as a convex optimization problem, leading to a scalable algorithm. Comprehensive experiments on synthetic (approximate) LoRD ( LoRD ) matrices confirm Sketchlord ’s performance in accurately recovering these structures. This positions it as a valuable addition to the structured approximation toolkit, particularly when high-fidelity approximations are desired for large-scale operators, such as the deep learning Hessian. 1 Introduction High-dimensional linear operators are ubiquitous in modern data science, from the Hessian matrices of deep neural networks to large-scale scientific simulators. Due to their sheer size, these operators are often accessible only implicitly through their MVP . While MVP access suffices for many applications, we sometimes prefer an explicit , albeit possibly approximate, representation of the operator. Such an explicit approximate representation can be useful, e.g., for visualizations or compressing an operator that contains simpler sub-structures. To achieve this tractably, one typically resorts to structured approximations that are cheap to store and invert. Recent advances in sketched methods enable the efficient construction of either LoR ( LoR ) or D ( D ) approximations from a comparably small number of MVP . However, these approaches can falter when the underlying linear operator exhibits a joint LoRD structure, or can be well-approximated as such. Attempting to recover operators with such inherent or approximate LoRD structure using methods designed solely for either LoR or diagonal components leads to suboptimal results, even when applying them sequentially ( Figs. 1 and 3 ). To address this gap, we introduce Sketchlord , a novel sketched method designed for the joint recovery of both LoR ( LoR ) and D ( D ) components simultaneously from a few MVP of large-scale linear operators. Our contributions are: • We analytically show that for LoRD operators, approximations for either LoR ( LoR ) or D ( D ) components individually, or even sequentially ( LoR -then- D or D -then- LoR ), are inherently suboptimal ( Section 3 ). We empirically verify this for sketched variants. • As a solution, we propose Sketchlord , a joint approximation method that phrases the LoRD recovery as a convex optimization task, solvable efficiently via ADMM ( Section 4 ). We provide practical accelerations, such as a new compact recovery strategy for any sketched methods. • On synthetic matrices, we empirically show that Sketchlord achieves high-quality approximations across a broad class of (approximately) LoRD operators ( Section 5 ). We also observe that Sketchlord is stable for a wide range of its hyperparameters ( Section 4.2 ). 2 Background Modern scientific computing and machine learning frequently encounter high-dimensional matrices, such as discretized differential operators in physical simulations or large covariance matrices. A prominent example motivating this work is the Hessian matrix in deep learning. Fundamental operations, like storing ( \mathcal{O}(N^{2}) ), performing explicit MVP ( \mathcal{O}(N^{2}) ), or computing its inverse ( \mathcal{O}(N^{3}) ), become infeasible even for comparably modest neural networks parameter counts, N , in the millions. Implicit, matrix-free, MVP —e.g., via Pearlmutter’s trick for the Hessian ( Pearlmutter 1994 ) —and structured approximations offer ways to nevertheless work with these massive matrices in practice. This work concentrates on achieving high-fidelity approximations for operators that are inherently LoRD ( LoRD ) or can be accurately represented by such a structure. Structured approximations. To render large operators tractable, various structured approximations are employed in practice. Low-rank captures dominant modes while diagonal approximations simplify interactions to element-wise scaling. Another instance, K-FAC ( Martens and Grosse 2015 ) , a popular Hessian approximation, employs a Kronecker-factored block-diagonal structure, primarily for computational efficiency in optimization. Crucially, the “best” approximation strategy is determined not only by the operator’s intrinsic structure but also by a critical trade-off: the application’s demand for approximation quality (low approximation error) versus constraints on the acceptable runtime and available memory . In essence, the specific application dictates whether a fast-but-coarse approximation suffices or if a potentially slower but more accurate representation is desired, and how memory constraints influence this choice. In this paper, we focus on the composite LoRD ( LoRD ) structure. Evidence suggests that important and complex operators, such as the Hessian matrix in deep learning, may be well-approximated by such a structure. For example, spectral analyses show dominant low-rank components ( Sagun et al. 2018 ; Papyan 2018 ; Ghorbani et al. 2019 , e.g.) , while common practices like diagonal regularizers introducing a diagonal contribution. Developing robust methods for high-quality LoRD approximation is thus of significant practical interest. Sketched methods for structured recovery. Sketched methods, based on random matrix theory, offer a data-efficient paradigm for constructing these structured approximations from only a limited number, p , of MVP measurements. Due to their scalability, reliability, and ability to be parallelized ( Halko et al. 2011 ) , they have steadily gained popularity in many applications including signal processing ( Couillet and Debbah 2013 ) , scientific computing ( Li et al. 2014 ; Tropp et al. 2019 ) , or machine learning ( Dereziński and Mahoney 2024 ; Fernandez et al. 2025 ) . Here, we focus on sketched methods for low-rank and diagonal recovery. Sketched methods like XDiag ( Epperly et al. 2024 ) or Diag++ are based on the Girard-Hutchinson estimator and allow estimating \diag({\bm{A}}) from only p\!\ll\!k\eqqcolon\rank({\bm{A}}) random measurements. In this work, we compare to XDiag which exhibits improved measurement-efficiency. Similarly, a SSVD ( SSVD ) provides an approximate SVD of a low-rank operator, using p left and right measurements, followed by QR orthogonalization, and an SVD of size p\!\times\!p (see Algorithm 3 ). Crucially, using p slightly larger than k is enough with high probability ( Halko et al. 2011 ; Tropp et al. 2017 ) . When {\bm{A}} is not truly low-rank, an oversampled recovery mechanism can be used instead to reduce noise ( Boutsidis et al. 2016 ; Tropp et al. 2019 ) Joint recovery with rank minimization. Consider the following general problem of rank minimization under linear mapping {\mathcal{M}} as e.g. studied in Candès and Tao 2010 : \displaystyle(P_{0})\qquad{\bm{X}}_{\natural}=\argmin_{{\bm{X}}}~~\rank({\bm{X}})~~~~~\text{s.t.{} }~~~~~{\mathcal{M}}({\bm{X}})={\bm{M}} (1) Though NP-hard in general ( Natarajan 1995 ) , its convex relaxation is equivalent with high probability when {\mathcal{M}} is sufficiently random and yields enough measurements ( Candès and Tao 2010 ) : \displaystyle(P_{1}\equiv P_{0})\qquad{\bm{X}}_{\natural}=\argmin_{{\bm{X}}}~~\lVert{\bm{X}}\rVert_{*}~~~~~\text{s.t.{} }~~~~~{\mathcal{M}}({\bm{X}})={\bm{M}} (2) This objective, in turn, admits a Lagrangian characterization that is equivalent for some \lambda\!\in\!\mathbb{R}_{\geq 0} : 1 1 1 Analytical \lambda is unavailable, with a few exceptions ( Candès et al. 2011 ; Tomioka and Suzuki 2010 , e.g.) . \displaystyle(P_{\lambda}\equiv P_{1})\qquad{\bm{X}}_{\natural}=\argmin_{{\bm{X}}}~~\frac{1}{2}\underbrace{\lVert{\bm{M}}-{\mathcal{M}}({\bm{X}})\rVert_{\text{F}}^{2}}_{{\mathcal{L}}_{2}}~~+~~\lambda\lVert{\bm{X}}\rVert_{*} (3) To

Read the complete text