An Inversion Theorem for Buffered Linear Toeplitz (BLT) Matrices and Applications to Streaming Differential Privacy
This work addresses a specific computational bottleneck in streaming differential privacy mechanisms, offering incremental improvements for researchers and practitioners in privacy-preserving data analysis.
The paper tackled the problem of inverting Buffered Linear Toeplitz (BLT) matrices, which are crucial for streaming differential privacy with correlated noise, by proving that the inverse is also a BLT matrix and providing an efficient O(d^3) algorithm to compute its parameters, enabling direct optimization via automatic differentiation.
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.