An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy
Buffered Linear Toeplitz (BLT) matrices are a family of parameterized lower-triangular matrices that play an important role in streaming differential privacy with correlated noise. Our main result is a BLT inversion theorem: the inverse of a BLT matrix is itself a BLT matrix with different parameters. We also present an efficient and differentiable $O(d^3)$ algorithm to compute the parameters of the inverse BLT matrix, where $d$ is the degree of the original BLT (typically $d < 10$). Our characterization enables direct optimization of BLT parameters for privacy mechanisms through automatic differentiation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LU decomposition and Toeplitz decomposition of a neural network
It is well-known that any matrix $A$ has an LU decomposition. Less well-known is the fact that it has a 'Toeplitz decomposition' $A = T_1 T_2 \cdots T_r$ where $T_i$'s are Toeplitz matrices. We will prove that any contin…
Line Spectrum Representation for Vector Processes With Application to Frequency Estimation
A positive semidefinite Toeplitz matrix, which often arises as the finite covariance matrix of a stationary random process, can be decomposed as the sum of a nonnegative multiple of the identity corresponding to a white …
Time Series AnalysisDeep Koopman-layered Model with Universal Property Based on Toeplitz Matrices
We propose deep Koopman-layered models with learnable parameters in the form of Toeplitz matrices for analyzing the transition of the dynamics of time-series data. The proposed model has both theoretical solidness and fl…
subspace methodsTime SeriesExploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices
The Hilbert-space Gaussian Process (HGP) approach offers a hyperparameter-independent basis function approximation for speeding up Gaussian Process (GP) inference by projecting the GP onto M basis functions. These proper…
Hyperparameter Optimization"Blind" Calibration and Toeplitz Covariance Matrix Estimation in Uniform Linear Arrays. Part I. Benchmark Analysis and Matrix-Free Techniques
The problems of uniform linear array (with uniform mutual coupling) calibration and Toeplitz covariance matrix estimation are re-examined for application in the receive arrays of modern High Frequency Over-the-Horizon Ra…