A Differential Privacy Mechanism Design Under Matrix-Valued Query
  Traditionally, differential privacy mechanism design has been tailored for a
scalar-valued query function. Although many mechanisms such as the Laplace and
Gaussian mechanisms can be extended to a matrix-valued query function by adding
i.i.d. noise to each element of the matrix, this method is often sub-optimal as
it forfeits an opportunity to exploit the structural characteristics typically
associated with matrix analysis. In this work, we consider the design of
differential privacy mechanism specifically for a matrix-valued query function.
The proposed solution is to utilize a matrix-variate noise, as opposed to the
traditional scalar-valued noise. Particularly, we propose a novel differential
privacy mechanism called the Matrix-Variate Gaussian (MVG) mechanism, which
adds a matrix-valued noise drawn from a matrix-variate Gaussian distribution.
We prove that the MVG mechanism preserves $(\epsilon,\delta)$-differential
privacy, and show that it allows the structural characteristics of the
matrix-valued query function to naturally be exploited. Furthermore, due to the
multi-dimensional nature of the MVG mechanism and the matrix-valued query, we
introduce the concept of directional noise, which can be utilized to mitigate
the impact the noise has on the utility of the query. Finally, we demonstrate
the performance of the MVG mechanism and the advantages of directional noise
using three matrix-valued queries on three privacy-sensitive datasets. We find
that the MVG mechanism notably outperforms four previous state-of-the-art
approaches, and provides comparable utility to the non-private baseline. Our
work thus presents a promising prospect for both future research and
implementation of differential privacy for matrix-valued query functions.
