CS Paper Radar

Estimating the generator of matrix exponential time-series

Jonáš Fuksa, Jens Eisert, Ingo Roth

cs.IT quant-ph ·submitted 2026-11-03 08:44 UTC · v1
theory

Abstract

The achievable precision in estimating the spectrum of a time-series signal that is promised to be sparse in Fourier space deteriorates rapidly as the spectral peaks get closer together, as soon as we introduce noise. Here, we study the related task of generator estimation: estimating the generator of a matrix exponential time-series and its eigenvalues. We obtain rigorous non-asymptotic precision guarantees on genESPRIT, a practical algorithm solving generator estimation, and show that this task can be solved with precision independent of the spectral spacing. The guarantees are complemented by a Cramér--Rao analysis of a relaxation of the problem. In particular, in the case of unitary data with bounded additive noise with effective entrywise variance $σ^2$, we show that genESPRIT estimates the associated propagator matrix in Frobenius norm with precision scaling as $\tilde{\mathcal{O}}(σNL^{-\frac12})$ in the length of the time-series $L$ and matrix dimension $N$, matching the corresponding spectrum-independent Cramér--Rao standard deviation scaling up to logarithmic factors. We prove that the matching distance error in the spectrum estimated by genESPRIT scales as $\tilde{\mathcal{O}} (σ^2 N^3 L^{-1} + σN^{\frac32} L^{-\frac32} )$, which we compare to the lower bound on the corresponding Cramér--Rao bound with the asymptotic standard deviation scaling $\mathcal{O}(σL^{-\frac32})$. These guarantees provide the first rigorous bounds on solving the generator estimation problem. As the matrix exponential time-series can be obtained from linearly independent vector time-series by concatenation, this work opens up a new direction in spectral estimation, which circumvents the problem of crowded spectra, under the additional assumption of linear independence.

Comment
11 pages + 4 page Appendix, 3 figures. Comments welcome!

Closest papers

Nearest neighbours by meaning across the whole index.

A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation

cs.LG stat.MLstat.ME ·2026-09-06 ·Huan Qing
theoryhot direction similarity 0.64
Abstract · 24 pages

The Davis-Kahan theorem is a fundamental tool in spectral analysis, providing quantitative control over the distance between the eigenspaces of a symmetric matrix and its perturbation. However, when the matrix dimension is large, computing leading eigenvectors is computationally expensive, limiting the practical use of spectral methods in modern large-scale applications. This paper addresses this problem by proposing an independent Bernoulli sampling scheme and proves that the leading left singular vectors of the subsampled matrix faithfully approximate the target subspace of a low-rank symmetric matrix. Our main result is a subsampled Davis-Kahan bound that gives an explicit error bound depending directly on the sampling probability. The bound reveals the trade-off: the computational cost scales linearly with the sampling probability, while the statistical error scales as the inverse square root of the sampling probability. Our result thus extends the Davis-Kahan theorem to the subsampled setting, enabling scalable spectral analysis of large-scale symmetric matrices.

0.25

A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings

cs.DS ·2026-08-28 ·Lorenzo Beretta, Cameron Musco
similarity 0.62
Abstract

We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm ε)$ error, Bujanović et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/ε^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/ε^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/ε^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.

0.38

Double Descent for Random Fourier Series Models

cs.IT math.ST ·2026-09-24 ·Hang Xu, Yi Shen, Yuzhong Zhao
similarity 0.62
Abstract

We investigate the least squares linear regression problem with random partial Discrete Fourier Transform (DFT) matrices, providing a rigorous analysis of the model's generalization error. By leveraging tools from random matrix theory, we derive exact non-asymptotic bounds for the risk of the Moore-Penrose estimator, which hold for finite-dimensional problems and reveal the precise dependence on key parameters such as the sample size, dimension, and noise variance. Then we obtain a characterization of the double descent phenomenon in the linear regression context, demonstrating how the risk evolves when the number of parameters $p$ and the number of samples $n$ tend to infinity, with $p/n$ fixed. The analysis relies on applications of the Stieltjes transform for random Fourier matrices, enabling a precise description of the spectral properties of these matrices and their impact on regression performance. To validate our theoretical findings, we present several numerical examples that illustrate the double descent curves. These simulations align closely with our derived bounds, confirming their predictive power in both under-parameterized and over-parameterized regimes.

0.21

Blind Noise Equalization for Large Data Matrices under General Variance Profiles

cs.LG stat.MLeess.SPmath.ST+1 ·2026-11-05 ·Boris Landa, Francesco Strino, Fabio Parisi, Ruiqi Li, Yuval Kluger
theory similarity 0.61
Abstract

Low-rank approximation is a basic tool for inference from large and noisy data matrices. However, when noise variances differ across entries, a setting known as heteroskedasticity, the noise can distort the observed spectrum, producing spurious components and obscuring weak signals. To address these challenges, we develop BRINE (Blind Resolvent-based Iterative Noise Equalizer), a data-driven procedure that iteratively rescales rows and columns to equalize the average noise variance across both dimensions. Under suitable conditions, this procedure restores the Marchenko-Pastur law for the noise spectrum and can amplify signal components without prior knowledge of the signal or noise structure. A key idea underlying our approach is to equalize the diagonal entries of the data resolvent as a proxy for equalizing the unknown noise variances. At the population level, we identify a potential function that characterizes this equalization and motivates an iterative minimization procedure. We prove convergence of the iterations to the true equalizer for arbitrary positive variance profiles, with a geometric rate under mild conditions. The updates can be estimated directly from noisy data, and we establish probabilistic error bounds for the scaling factors. Simulations and experiments across diverse biological data modalities and preprocessing pipelines illustrate the effectiveness of our approach.

0.30

Fast Length-Squared Sampling for Positive-Semidefinite Matrices

cs.DS cs.LG ·2026-08-12 ·Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian
similarity 0.61
Abstract

We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.

0.04

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.60
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35

Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

cs.LG eess.SY ·2026-09-30 ·Xiaomian Yang, Sungho Shin
similarity 0.60
Abstract

We establish non-asymptotic sample complexity bounds for the least-squares estimation of vector autoregressive models for exponentially stable systems with heavy-tailed noise based on a single observed trajectory. By assuming i.i.d. noise, bounded noise covariance, and persistent excitation, we show that the estimation error is $\widetilde{\mathcal{O}}(r^{1/2}T^{-1/2+1/p})$ under bounded $p$th moment for $p > 2$, where $T$ is the number of samples, $r$ is the noise dimension, and $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic terms. We also introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions and showcase this by deriving error bounds for sub-exponential and sub-Gaussian noise distributions. Finally, we specialize our analysis to autoregressive models with exogenous inputs and show that the dimension factor of the error bound is independent of the model order.

0.20

Dimension-Free Private Mean Estimation is Impossible Without the Covariance

cs.LG cs.DS ·2026-11-04 ·Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, Lydia Zakynthinou
similarity 0.60
Abstract

We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance $Σ$ is known, the optimal sample complexity can depend only on its spectrum, rather than on the ambient dimension $d$. We establish new lower bounds for Gaussian mean estimation with Euclidean error which show that private estimators cannot achieve similar guarantees when the covariance is unknown. First, when the sample size $n$ is smaller than the effective dimension $\mathrm{trace}(Σ)/\|Σ\|_{\text{op}}$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d/n}$. Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by $\log d$, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of $\sqrt{d}/n^{3/2}$. Together, these results show that in the unknown covariance setting, exploiting anisotropic structure under differential privacy can require a dimension-dependent error or sample complexity.

0.21