A Differential Privacy Mechanism Design Under Matrix-Valued Query
Thee Chanyaswad Alex Dytso H. Vincent Poor Prateek Mittal





A Differential Privacy Mechanism Design
Under Matrix-Valued Query
    Thee Chanyaswad  Alex Dytso  H. Vincent Poor  Prateek
Mittal
    December 30, 2023
=================================================================





Princeton University
Princeton, NJ, USA



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 (ϵ,δ)-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.

This is the full version of the work, so parts of the material in this paper are derived from the conference version of this work <cit.>.



§ INTRODUCTION


Differential privacy <cit.>
has become the gold standard for a rigorous privacy guarantee, and
there has been the development of many differentially-private mechanisms.
Some popular mechanisms include the classical Laplace mechanism <cit.>
and the Exponential mechanism <cit.>. In addition, there
are other mechanisms that build upon these two classical ones such
as those based on data partition and aggregation <cit.>,
and those based on adaptive queries <cit.>.
From this observation, differentially-private mechanisms may be categorized
into two groups: the basic mechanisms, and the derived mechanisms.
The basic mechanisms' privacy guarantee is self contained, whereas
the derived mechanisms' privacy guarantee is achieved through a combination
of basic mechanisms, composition theorems, and the post-processing
invariance property <cit.>.

In this work, we consider the design of a basic mechanism for
matrix-valued query functions. Existing basic mechanisms for
differential privacy are designed usually for scalar-valued query
functions. However, in many practical settings, the query functions
are multi-dimensional and can be succinctly represented as matrix-valued
functions. Examples of matrix-valued query functions in the real-world
applications include the covariance matrix <cit.>,
the kernel matrix <cit.>, the adjacency matrix <cit.>,
the incidence matrix <cit.>, the rotation matrix <cit.>,
the Hessian matrix <cit.>, the transition matrix <cit.>,
and the density matrix <cit.>, which find applications
in statistics <cit.>, machine learning <cit.>,
graph theory <cit.>, differential equations <cit.>,
computer graphics <cit.>, probability theory <cit.>,
quantum mechanics <cit.>, and many other fields <cit.>.

One property that distinguishes the matrix-valued query functions
from the scalar-valued query functions is the relationship and interconnection
among the elements of the matrix. One may naively treat these matrices
as merely a collection of scalar values, but that could prove sub-optimal
since the structure and relationship among these scalar
values are often informative and essential to the understanding and
analysis of the system. For example, in graph theory, the adjacency
matrix is symmetric for an undirected graph, but not for a directed
graph <cit.> – an observation which is implausible
to extract from simply looking at the collection of elements without
considering how they are arranged in the matrix.

In differential privacy, the traditional method for dealing with a
matrix-valued query function is to extend a scalar-valued mechanism
by adding independent and identically distributed (i.i.d.)
noise to each element of the matrix <cit.>.
However, this method fails to utilize the structural characteristics
of the matrix-valued noise and query function. Although some advanced
methods have explored this possibility in an iterative/procedural
manner <cit.>, the structural characteristics
of the matrices are still largely under-investigated. This is partly
due to the lack of a basic mechanism that is directly designed for
matrix-valued query functions, making the utilization of matrix structures
and application of available tools in matrix analysis challenging.

In this work, we formalize the study of the matrix-valued differential
privacy, and present a new basic mechanism that can readily exploit
the structural characteristics of the matrices – the Matrix-Variate
Gaussian (MVG) mechanism. The high-level concept of the MVG mechanism
is simple – it adds a matrix-variate Gaussian noise scaled
to the L_2-sensitivity of the matrix-valued query function (cf.
Figure <ref>). We rigorously prove that the MVG
mechanism guarantees (ϵ,δ)-differential privacy, and
show that, with the MVG mechanism, the structural characteristics
of the matrix-valued query functions can readily be incorporated into
the mechanism design. Specifically, we present an example of how the
MVG mechanism can yield greater utility by exploiting the positive-semi
definiteness of the matrix-valued query function. Moreover, due to
the multi-dimensional nature of the noise and the query function,
the MVG mechanism allows flexibility in the design via the novel notion
of directional noise. An important consequence of the concept
of directional noise is that the matrix-valued noise in the MVG mechanism
can be devised to affect certain parts of the matrix-valued query
function less than the others, while providing the same privacy
guarantee. In practice, this property could be advantageous as the
noise can be tailored to have minimal impact on the intended utility.
We present simple algorithms to incorporate the directional noise
into the differential privacy mechanism design, and theoretically
present the optimal design for the MVG mechanism with directional
noise that maximizes the power-to-noise ratio of the mechanism output.



Finally, to illustrate the effectiveness of the MVG mechanism, we
conduct experiments on three privacy-sensitive real-world datasets
– Liver Disorders <cit.>, Movement
Prediction <cit.>, and Cardiotocography <cit.>.
The experiments include three tasks involving matrix-valued query
functions – regression, finding the first principal component,
and covariance estimation. The results show that the MVG mechanism
can evidently outperform four prior state-of-the-art mechanisms –
the Laplace mechanism, the Gaussian mechanism, the Exponential mechanism,
and the JL transform – in utility in all experiments,
and can provide the utility similar to that achieved with the non-private
methods, while guaranteeing differential privacy.

To summarize, the main contributions are as follows. 


  * We formalize the study of matrix-valued query functions in differential
privacy and introduce the novel Matrix-Variate Gaussian (MVG)
mechanism. 

  * We rigorously prove that the MVG mechanism guarantees (ϵ,δ)-differential
privacy.

  * We show that exploiting the structural characteristic of the matrix-valued
query function can improve the utility performance of the MVG mechanism.

  * We introduce a novel concept of directional noise, and propose
two simple algorithms to implement this novel concept with the MVG
mechanism. 

  * We theoretically exhibit how the directional noise can be devised
to provide the maximum utility from the MVG mechanism.

  * We evaluate our approach on three real-world datasets and show that
our approach can outperform four prior state-of-the-art mechanisms
in all experiments, and yields utility performance close to the non-private
baseline. 




§ PRIOR WORKS 


Existing mechanisms for differential privacy may be categorized into
two types: the basic <cit.>;
and the derived mechanisms <cit.>.
Since our work concerns the basic mechanism design, we focus our discussion
on this type, and provide a general overview of the other.



 §.§ Basic Mechanisms 


Basic mechanisms are those whose privacy guarantee is self-contained,
i.e. it does not deduce the guarantee from another mechanism. Here,
we discuss four popular existing basic mechanisms: the Laplace mechanism,
the Gaussian mechanism, the Johnson-Lindenstrauss transform method,
and the Exponential mechanism.



  §.§.§ Laplace Mechanism


The classical Laplace mechanism <cit.> adds noise
drawn from the Laplace distribution scaled to the L_1-sensitivity
of the query function. It was initially designed for a scalar-valued
query function, but can be extended to a matrix-valued query function
by adding i.i.d. Laplace noise to each element of the matrix. The
Laplace mechanism provides the strong ϵ-differential privacy
guarantee and is relatively simple to implement. However, its generalization
to a matrix-valued query function does not automatically utilize the
structure of the matrices involved.



  §.§.§ Gaussian Mechanism


The Gaussian mechanism <cit.>
uses i.i.d. additive noise drawn from the Gaussian distribution scaled
to the L_2-sensitivity of the query function. The Gaussian mechanism
guarantees (ϵ,δ)-differential privacy. It suffers from
the same limitation as the Laplace mechanism when extended to a matrix-valued
query function, i.e. it does not automatically consider the structure
of the matrices.



  §.§.§ Johnson-Lindenstrauss Transform


The Johnson-Lindenstrauss (JL) transform method <cit.>
uses multiplicative noise to guarantee (ϵ,δ)-differential
privacy. It is, in fact, a rare basic mechanism designed for a matrix-valued
query function. Despite its promise, previous works show that the
JL transform method can be applied to queries with certain properties
only, as we discuss here. 


  * Blocki et al. <cit.> use a random matrix, whose entries
are drawn i.i.d. from a Gaussian distribution, and the method is applicable
to the Laplacian of a graph and the covariance matrix. 

  * Blum and Roth <cit.> use a hash function that implicitly
represents the JL transform, and the method is suitable for a sparse
query.

  * Upadhyay <cit.> uses a multiplicative combination
of random matrices to provide a JL transform that is applicable to
any matrix-valued query function whose singular values are all above
a minimum threshold. 

Among these methods, Upadhyay's works <cit.>
stand out as possibly the most general. In our experiments, we show
that our approach can yield higher utility for the same privacy budget
than these methods.



  §.§.§ Exponential Mechanism


In contrast to additive and multiplicative noise used in previous
approaches, the Exponential mechanism uses noise introduced
via the sampling process <cit.>. The Exponential mechanism
draws its query answers from a custom probability density function
designed to preserve ϵ-differential privacy. To provide
reasonable utility, the Exponential mechanism designs its sampling
distribution based on the quality function, which indicates
the utility score of each possible sample. Due to its generality,
the Exponential mechanism has been utilized for many types of query
functions, including the matrix-valued query functions. We experimentally
compare our approach to the Exponential mechanism, and show that,
with slightly weaker privacy guarantee, our method can yield significant
utility improvement.

Finally, we conclude that our method differs from the four existing
basic mechanisms as follows. In contrast with the i.i.d. noise in
the Laplace and Gaussian mechanisms, the MVG mechanism allows a non-i.i.d.
noise (cf. Section <ref>). As opposed to the
multiplicative noise in the JL transform and the sampling noise in
the Exponential mechanism, the MVG mechanism uses an additive noise
for matrix-valued query functions.



 §.§ Derived Mechanisms


Derived mechanisms are those whose privacy guarantee is deduced from
other basic mechanisms via the composition theorems and the post-processing
invariance property <cit.>. Derived mechanisms are often
designed to provide better utility by exploiting some properties of
the query function or of the data. Blocki et al. <cit.>
also define a similar categorization with the term “revised algorithm”.

The general techniques used by derived mechanisms are often translatable
among basic mechanisms, including our MVG mechanism. Given our focus
on a novel basic mechanism, these techniques are less relevant to
our work, and we leave the investigation of integrating them into
the MVG framework in future work. Some of the popular techniques used
by derived mechanisms are summarized here.



  §.§.§ Sensitivity Control


This technique avoids the worst-case sensitivity in basic mechanisms
by using variant concepts of sensitivity. Examples include the smooth
sensitivity framework <cit.> and elastic sensitivity
<cit.>.



  §.§.§ Data Partition and Aggregation


This technique uses data partition and aggregation to produce more
accurate query answers <cit.>.
The partition and aggregation processes are done in a differentially-private
manner either via the composition theorems and the post-processing
invariance property <cit.>, or with a small extra privacy
cost. Hay et al. <cit.> nicely summarize many works
that utilize this concept.



  §.§.§ Non-uniform Data Weighting


This technique lowers the level of perturbation required for the privacy
protection by weighting each data sample or dataset differently
<cit.>. The rationale
is that each sample in a dataset, or each instance of the dataset
itself, has a heterogeneous contribution to the query output. Therefore,
these mechanisms place a higher weight on the critical samples or
instances of the database to provide better utility.



  §.§.§ Data Compression


This approach reduces the level of perturbation required for differential
privacy via dimensionality reduction. Various dimensionality
reduction methods have been proposed. For example, Kenthapadi et al.
<cit.>, Xu et al. <cit.>, and Li et al.
<cit.> use random projection; Chanyaswad et al. <cit.>
and Jiang et al. <cit.> use principal component analysis
(PCA); Xiao et al. <cit.> use wavelet transform; and
Acs et al. <cit.> use lossy Fourier transform.



  §.§.§ Adaptive Queries


The derived mechanisms based on adaptive queries use prior and/or
auxiliary information to improve the utility of the query answers.
Examples include the matrix mechanism <cit.>,
the multiplicative weights mechanism <cit.>,
the low-rank mechanism <cit.>, boosting <cit.>,
and the sparse vector technique <cit.>.

Finally, we conclude with three main observations. First, the MVG
mechanism falls into the category of basic mechanism. Second, techniques
used in derived mechanisms are generally applicable to multiple basic
mechanisms, including our novel MVG mechanism. Third, therefore, for
fair comparison, we will compare the MVG mechanism with the four state-of-the-art
basic mechanisms presented in this section.



§ BACKGROUND


We begin with a discussion of basic concepts pertaining to the MVG
mechanism for matrix-valued query.



 §.§ Matrix-Valued Query 


In our analysis, we use the term dataset interchangeably with
database, and represent it with the matrix 𝐗. The matrix-valued
query function, f(𝐗)∈ℝ^m× n, has m
rows and n columns. We define the notion of neighboring datasets
{𝐗_1,𝐗_2} as two datasets that differ by
a single record, and denote it as d(𝐗_1,𝐗_2)=1.
We note, however, that although the neighboring datasets differ by
only a single record, f(𝐗_1) and f(𝐗_2)
may differ in every element.

We denote a matrix-valued random variable with the calligraphic font,
e.g. 𝒵, and its instance with the bold font, e.g. 𝐙.
Finally, as will become relevant later, we use the columns of 𝐗
to denote the records (samples) in the dataset.



 §.§ (ϵ,δ)-Differential Privacy


In the paradigm of data privacy, differential privacy <cit.>
provides a rigorous privacy guarantee, and has been widely adopted
in the community <cit.>. Differential privacy guarantees
that the involvement of any one particular record of the dataset would
not drastically change the query answer. 

A mechanism 𝒜 on a query
function f(·) is (ϵ,δ)- differentially-private
if for all neighboring datasets {𝐗_1,𝐗_2},
and for all possible measurable matrix-valued outputs 𝐘⊆ℝ^m× n,

    [𝒜(f(𝐗_1))∈𝐘]≤ e^ϵ[𝒜(f(𝐗_2))∈𝐘]+δ.





 §.§ Matrix-Variate Gaussian Distribution


One of our main innovations is the use of the noise drawn from a matrix-variate
probability distribution. More specifically, in the MVG mechanism,
the additive noise is drawn from the matrix-variate Gaussian distribution,
defined as follows <cit.>. 

An m× n matrix-valued random variable
𝒳 has a matrix-variate Gaussian distribution, denoted
as ℳ𝒱𝒢_m,n(𝐌,Σ,Ψ),
if it has the probability density function: 

    p_𝒳(𝐗)=exp{-1/2tr[Ψ^-1(𝐗-𝐌)^TΣ^-1(𝐗-𝐌)]}/(2π)^mn/2|Ψ|^m/2|Σ|^n/2,

where tr(·) is the matrix trace <cit.>,
|·| is the matrix determinant <cit.>,
𝐌∈ℝ^m× n is the mean, Σ∈ℝ^m× m
is the row-wise covariance, and Ψ∈ℝ^n× n
is the column-wise covariance. 

Noticeably, the probability density function (pdf) of ℳ𝒱𝒢_m,n(𝐌,Σ,Ψ)
looks similar to that of the m-dimensional multivariate Gaussian
distribution, 𝒩_m(μ,Σ).
Indeed, ℳ𝒱𝒢_m,n(𝐌,Σ,Ψ)
is a generalization of 𝒩_m(μ,Σ)
to a matrix-valued random variable. This leads to a few notable additions.
First, the mean vector μ now becomes the mean matrix
𝐌. Second, in addition to the traditional row-wise covariance
matrix Σ, there is also the column-wise covariance
matrix Ψ. The latter addition is due to the fact
that, not only could the rows of the matrix be distributed non-uniformly,
but also could its columns.

We may intuitively explain this addition as follows. If we draw n
i.i.d. samples from 𝒩_m(0,Σ)
denoted as 𝐱_1,𝐱_2,…,𝐱_n∈ℝ^m,
and concatenate them into a matrix 𝐗=[𝐱_1,𝐱_2,…,𝐱_n]∈ℝ^m× n,
then, it can be shown that 𝐗 is drawn from ℳ𝒱𝒢_m,n(0,Σ,𝐈),
where 𝐈 is the identity matrix <cit.>. However,
if we consider the case when the columns of 𝐗 are not
i.i.d., and are distributed with the covariance Ψ
instead, then, it can be shown that this is distributed according
to ℳ𝒱𝒢_m,n(0,Σ,Ψ)
<cit.>.



 §.§ Relevant Matrix Algebra Theorems


We recite major theorems in matrix algebra that are essential to the
subsequent analysis and discussion as follows.

A matrix 𝐀∈ℝ^m× n can
be decomposed into two unitary matrices 𝐖_1∈ℝ^m× m,𝐖_2∈ℝ^n× n,
and a diagonal matrix Λ, whose diagonal elements
are ordered non-increasingly downward. These diagonal elements are
the singular values of 𝐀 denoted as σ_1≥σ_2≥⋯≥0,
and 𝐀=𝐖_1Λ𝐖_2^T. 



 For a matrix-variate random variable
𝒩∼ℳ𝒱𝒢_m,n(0,𝐈_m,𝐈_n),
δ∈[0,1], and ζ(δ)=2√(-mnlnδ)-2lnδ+mn,
the following inequality holds: 

    [‖𝒩‖ _F^2≤ζ(δ)^2]≥1-δ,

where ‖·‖ _F is the Frobenius norm of
a matrix.



 The non-increasingly ordered singular
values of a matrix 𝐀∈ℝ^m× n have the
values of 

    0≤σ_i≤‖𝐀‖ _F/√(i),

where ‖·‖ _F is the Frobenius norm of
a matrix.



Let 𝐀,𝐁∈ℝ^m× n,
and let σ_i(𝐀) and σ_i(𝐁) be
the non-increasingly ordered singular values of 𝐀 and
𝐁, respectively. Then

    tr(𝐀𝐁^T)≤Σ_i=1^rσ_i(𝐀)σ_i(𝐁),

where r=min{m,n}. 



Let 𝐀∈ℝ^m× n,
and let σ_i(𝐀) be the non-increasingly ordered
singular values of 𝐀. Then

    |tr(𝐀)|≤∑_i=1^rσ_i(𝐀),

where r=min{m,n}.



  Let 𝐀∈ℝ^m× m
be non-singular and 𝐚_i be the i^th column vector
of 𝐀 . Then, 

    |𝐀|^2≤∏_i=1^m‖𝐚_i‖ ^2,

where |·| is the matrix determinant <cit.>,
and ‖·‖ is the L_2-norm of a vector.




§ MVG MECHANISM: DIFFERENTIAL PRIVACY WITH MATRIX-VALUED QUERY


Matrix-valued query functions are different from their scalar counterparts
in terms of the vital information contained in how the elements are
arranged in the matrix. To fully exploit these structural characteristics
of matrix-valued query functions, we present a novel mechanism for
matrix-valued query functions: the Matrix-Variate Gaussian (MVG)
mechanism.



 §.§ Definitions


First, let us introduce the sensitivity of the matrix-valued query
function used in the MVG mechanism. 

Given a matrix-valued query function f(𝐗)∈ℝ^m× n,
define the L_2-sensitivity as, 

    s_2(f)=sup_d(𝐗_1,𝐗_2)=1‖ f(𝐗_1)-f(𝐗_2)‖ _F,

where ‖·‖ _F is the Frobenius norm <cit.>. 

Then, we present the MVG mechanism as follows. 

Given a matrix-valued query function f(𝐗)∈ℝ^m× n,
and a matrix-valued random variable 𝒵∼ℳ𝒱𝒢_m,n(0,Σ,Ψ),
the MVG mechanism is defined as, 

    ℳ𝒱𝒢(f(𝐗))=f(𝐗)+𝒵,

where Σ is the row-wise covariance matrix, and
Ψ is the column-wise covariance matrix. 

Note that so far, we have not specified how to pick Σ
and Ψ according to the sensitivity s_2(f)
in the MVG mechanism. We discuss the explicit form of Σ
and Ψ next.

As the additive matrix-valued noise of the MVG mechanism is drawn
from ℳ𝒱𝒢_m,n(0,Σ,Ψ),
the parameters to be designed for the mechanism are the covariance
matrices Σ and Ψ. In the following
discussion, we derive the sufficient conditions on Σ
and Ψ such that the MVG mechanism preserves (ϵ,δ)-differential
privacy. Furthermore, since one of the motivations of the MVG mechanism
is to facilitate the exploitation of the structural characteristics
of the matrix-value query, we demonstrate how the structural knowledge
about the matrix-value query can improve the sufficient condition
for the MVG mechanism. The term improve here certainly requires
further specification, and we provide such clarification when the
context is appropriate later in this section.

Hence, the subsequent discussion proceeds as follows. First, we present
a sufficient condition for the values of Σ and
Ψ to ensure that the MVG mechanism preserves (ϵ,δ)-differential
privacy without assuming structural knowledge about the matrix-valued
query. Second, we present an alternative sufficient condition for
Σ and Ψ to ensure that the
MVG mechanism preserves (ϵ,δ)-differential privacy
with the assumption that the matrix-value query is symmetric
positive semi-definite (PSD). Finally, we rigorously prove that,
by incorporating the knowledge of positive semi-definiteness about
the matrix-value query, we improve the sufficient condition to guarantee
(ϵ,δ)-differential privacy with the MVG mechanism.



 §.§ Differential Privacy Analysis for General Matrix-Valued Query (No
Structural Assumption) 




First, we consider the most general differential privacy analysis
of the MVG mechanism. More specifically, we do not make explicit structural
assumption about the matrix-query function in this analysis. The following
theorem presents the key result under this general setting.

 Let σ(Σ^-1)=[σ_1(Σ^-1),…,σ_m(Σ^-1)]^T
and σ(Ψ^-1)=[σ_1(Ψ^-1),…,σ_n(Ψ^-1)]^T
be the vectors of non-increasingly ordered singular values of Σ^-1
and Ψ^-1, respectively, and let the relevant
variables be defined according to Table <ref>. Then,
the MVG mechanism guarantees (ϵ,δ)-differential privacy
if Σ and Ψ satisfy the following
condition, 

    ‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2≤(-β+√(β^2+8αϵ))^2/4α^2,

where α=[H_r+H_r,1/2]γ^2+2H_rγ s_2(f),
and β=2(mn)^1/4ζ(δ)H_rs_2(f). 


The MVG mechanism guarantees differential privacy if for every pair
of neighboring datasets {𝐗_1,𝐗_2} and all
possible measurable sets 𝐒⊆ℝ^m× n,

    [f(𝐗_1)+𝒵∈𝐒]≤exp(ϵ)[f(𝐗_2)+𝒵∈𝐒].

The proof now follows by observing that (cf. Section <ref>),

    𝒵=𝐖_ΣΛ_Σ^1/2𝒩Λ_Ψ^1/2𝐖_Ψ^T,

and defining the following events: 

    𝐑_1={𝒩:𝒩_F^2≤ζ(δ)^2}, 𝐑_2={𝒩:𝒩_F^2>ζ(δ)^2},

where ζ(δ) is defined in Theorem <ref>.
Next, observe that 

    [f(𝐗_1)+𝒵∈𝐒]     =[({f(𝐗_1)+𝒵∈𝐒}∩𝐑_1)∪({f(𝐗_1)+𝒵∈𝐒}∩𝐑_2)]
       ≤[{f(𝐗_1)+𝒵∈𝐒}∩𝐑_1]+[{f(𝐗_1)+𝒵∈𝐒}∩𝐑_2],

where the last inequality follows from the union bound. By Theorem
<ref> and the definition of the set 𝐑_2,
we have, 

    [{f(𝐗_1)+𝒵∈𝐒}∩𝐑_2]≤[𝐑_2]=1-[𝐑_1]≤δ.


In the rest of the proof, we find sufficient conditions for the following
inequality to hold: 

    [f(𝐗_1)+𝒵∈(𝐒∩𝐑_1)]≤exp(ϵ)[f(𝐗_2)+𝒵∈𝐒].

this would complete the proof of differential privacy guarantee.

Using the definition of ℳ𝒱𝒢_m,n(0,Σ,Ψ)
(Definition <ref>), this is satisfied if we have, 

    ∫_𝐒∩𝐑_1exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_1))^TΣ^-1(𝐘-f(𝐗_1))]}d𝐘   ≤
    exp(ϵ)·∫_𝐒∩𝐑_1exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_2))^TΣ^-1(𝐘-f(𝐗_2))]}d𝐘.

By inserting exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_2))^TΣ^-1(𝐘-f(𝐗_2))]}/exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_2))^TΣ^-1(𝐘-f(𝐗_2))]}
inside the integral on the left side, it suffices to show that 

    exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_1))^TΣ^-1(𝐘-f(𝐗_1))]}/exp{-1/2tr[Ψ^-1(𝐘-f(𝐗_2))^TΣ^-1(𝐘-f(𝐗_2))]}≤exp(ϵ),

for all 𝐘∈𝐒∩𝐑_1. With some algebraic
manipulations, the left hand side of this condition can be expressed
as, 

    =    exp{-1/2tr[Ψ^-1𝐘^TΣ^-1(f(𝐗_2)-f(𝐗_1))+Ψ^-1(f(𝐗_2)-f(𝐗_1))^TΣ^-1𝐘
        -Ψ^-1f(𝐗_2)^TΣ^-1f(𝐗_2)+Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)]}
    
    =    exp{1/2tr[Ψ^-1𝐘^TΣ^-1Δ+Ψ^-1Δ^TΣ^-1𝐘
        +Ψ^-1f(𝐗_2)^TΣ^-1f(𝐗_2)-Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)]},

where Δ=f(𝐗_1)-f(𝐗_2).
This quantity has to be bounded by ≤exp(ϵ), so we present
the following characteristic equation, which has to be satisfied
for all possible neighboring {𝐗_1,𝐗_2}
and all 𝐘∈𝐒∩𝐑_1, for the MVG
mechanism to guarantee (ϵ,δ)-differential privacy:

    tr[Ψ^-1𝒴^TΣ^-1Δ+Ψ^-1Δ^TΣ^-1𝒴+Ψ^-1f(𝐗_2)^TΣ^-1f(𝐗_2)-Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)]≤2ϵ

Specifically, we want to show that this inequality holds with probability
1-δ.

From the characteristic equation, the proof analyzes the four terms
in the sum separately since the trace is additive.

The first term: tr[Ψ^-1𝒴^TΣ^-1Δ].
First, let us denote 𝒴=f(𝐗)+𝒵, where
f(𝐗) and 𝒵 are any possible instances of
the query and the noise, respectively. Then, we can rewrite the first
term as, tr[Ψ^-1f(𝐗)^TΣ^-1Δ]+tr[Ψ^-1𝒵^TΣ^-1Δ].
The earlier part can be bounded from Lemma <ref>: 

    tr[Ψ^-1f(𝐗)^TΣ^-1Δ]≤∑_i=1^rσ_i(Ψ^-1f(𝐗)^T)σ_i(Δ^TΣ^-1).

Lemma <ref> can then be used to bound each singular
value. In more detail, 

    σ_i(Ψ^-1f(𝐗)^T)≤‖Ψ^-1f(𝐗)^T‖ _F/√(i)≤‖Ψ^-1‖ _F‖ f(𝐗)‖ _F/√(i),

where the last inequality is via the sub-multiplicative property of
a matrix norm <cit.>. It is well-known that ‖Ψ^-1‖_F=‖σ(Ψ^-1)‖_2
(cf. <cit.>), and since γ=sup_𝐗‖ f(𝐗)‖_F,

    σ_i(Ψ^-1f(𝐗)^T)≤γ‖σ(Ψ^-1)‖ _2/√(i).

Applying the same steps to the other singular value, and using Definition
<ref>, we can write, 

    σ_i(Δ^TΣ^-1)≤ s_2(f)‖σ(Σ^-1)‖ _2/√(i).

Substituting the two singular value bounds, the earlier part of the
first term can then be bounded by,

    tr[Ψ^-1f(𝐗)^TΣ^-1Δ]≤γ s_2(f)H_r‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2.

 

The latter part of the first term is more complicated since it involves
𝒵, so we will derive the bound in more detail. First,
let us define 𝒩 to be drawn from ℳ𝒱𝒢_m,n(0,𝐈_m,𝐈_n),
so we can write 𝒵 in terms of 𝒩 using affine
transformation <cit.>: 𝒵=𝐁_Σ𝒩𝐁_Ψ^T.
To specify 𝐁_Σ and 𝐁_Ψ,
we solve the following linear equations, respectively, 

    𝐁_Σ𝐁_Σ^T    =Σ;
    𝐁_Ψ𝐁_Ψ^T    =Ψ.

This can be readily solved with SVD (cf. <cit.>);
hence, 𝐁_Σ=𝐖_ΣΛ_Σ^1/2,
and 𝐁_Ψ=𝐖_ΨΛ_Ψ^1/2,
where Σ=𝐖_ΣΛ_Σ𝐖_Σ^T,
and Ψ=𝐖_ΨΛ_Ψ𝐖_Ψ^T
from SVD. Therefore, 𝒵 can be written as, 

    𝒵=𝐖_ΣΛ_Σ^1/2𝒩Λ_Ψ^1/2𝐖_Ψ^T.

Substituting into the latter part of the first term yields, 

    tr[Ψ^-1𝒵^TΣ^-1Δ]=tr[𝐖_ΨΛ_Ψ^-1/2𝒩Λ_Σ^-1/2𝐖_Σ^TΔ].

This can be bounded by Lemma <ref> as, 

    tr[Ψ^-1𝒵^TΣ^-1Δ]≤∑_i=1^rσ_i(𝐖_ΨΛ_Ψ^-1/2𝒩Λ_Σ^-1/2𝐖_Σ^T)σ_i(Δ).

The two singular values can then be bounded by Lemma <ref>.
For the first singular value, 

    σ_i(𝐖_ΨΛ_Ψ^-1/2𝒩Λ_Σ^-1/2𝐖_Σ^T)    ≤‖𝐖_ΨΛ_Ψ^-1/2𝒩Λ_Σ^-1/2𝐖_Σ^T‖ _F/√(i)
       ≤‖Λ_Σ^-1/2‖ _F‖Λ_Ψ^-1/2‖ _F‖𝒩‖ _F/√(i).

By definition, ‖Λ_Σ^-1/2‖ _F=√(tr(Λ_Σ^-1))=‖σ(Σ^-1)‖ _1^1/2,
where ‖·‖ _1 is the 1-norm. By norm relation,
‖σ(Σ^-1)‖ _1^1/2≤ m^1/4‖σ(Σ^-1)‖ _2^1/2.
With similar derivation for ‖Λ_Ψ^-1/2‖_F
and with Theorem <ref>, the singular value can
be bounded with probability 1-δ as, 

    σ_i(𝐖_ΨΛ_Ψ^-1/2𝒩Λ_Σ^-1/2𝐖_Σ^T)≤(mn)^1/4ζ(δ)‖σ(Σ^-1)‖ _2^1/2‖σ(Ψ^-1)‖ _2^1/2/√(i).

Meanwhile, the other singular value can be readily bounded with Lemma
<ref> as σ_i(Δ)≤ s_2(f)/√(i).
Hence, the latter part of the first term is bounded with probability
≥1-δ as,

    tr[Ψ^-1𝒵^TΣ^-1Δ]≤(mn)^1/4ζ(δ)H_rs_2(f)‖σ(Σ^-1)‖ _2^1/2‖σ(Ψ^-1)‖ _2^1/2.

 Since the parameter (‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2)^1/2
appears a lot in the derivation, let us define 

    ϕ=(‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2)^1/2.

Finally, combining Eq. (<ref>) and (<ref>)
yields the bound for the first term, 

    tr[Ψ^-1𝒴^TΣ^-1Δ]≤γ H_rs_2(f)ϕ^2+(mn)^1/4ζ(δ)H_rs_2(f)ϕ.


The second term: tr[Ψ^-1Δ^TΣ^-1𝒴].
By following the same steps as in the first term, it can be shown
that the second term has the exact same bound as the first terms,
i.e. 

    tr[Ψ^-1Δ^TΣ^-1𝒴]≤γ H_rs_2(f)ϕ^2+(mn)^1/4ζ(δ)H_rs_2(f)ϕ.


The third term: tr[Ψ^-1f(𝐗_2)^TΣ^-1f(𝐗_2)].
Applying Lemma <ref> and <ref>,
we can readily bound it as, 

    tr[Ψ^-1f(𝐗_2)^TΣ^-1f(𝐗_2)]≤γ^2H_rϕ^2.


The fourth term: -tr[Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)].
Since this term has the negative sign, we consider the absolute value
instead. Using Lemma <ref>, 

    |tr[Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)]|≤∑_i=1^rσ_i(Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)).

Then, using the singular value bound in Lemma <ref>,

    σ_i(Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1))≤‖Ψ^-1‖ _F‖ f(𝐗_1)‖ _F^2‖Σ^-1‖ _F/√(i).

Hence, the fourth term can be bounded by, 

    |tr[Ψ^-1f(𝐗_1)^TΣ^-1f(𝐗_1)]|≤γ^2H_r,1/2ϕ^2.


Four terms combined: by combining the four terms and rearranging
them, the characteristic equation becomes, 

    αϕ^2+βϕ≤2ϵ.

This is a quadratic equation, of which the solution is ϕ∈[-β-√(β^2+8αϵ)/2α,-β+√(β^2+8αϵ)/2α].
Since we know ϕ≥0, due to the axiom of the norm, we only
have the one-sided solution, 

    ϕ≤-β+√(β^2+8αϵ)/2α,

which immediately implies the criterion in Theorem <ref>. 



In Theorem <ref>, we assume that the Frobenius
norm of the query function is bounded for all possible datasets by
γ. This assumption is valid in practice because real-world
data are rarely unbounded (cf. <cit.>), and it is a
common assumption in the analysis of differential privacy for multi-dimensional
query functions (cf. <cit.>). 



The values of the generalized harmonic numbers – H_r,
and H_r,1/2 – can be obtained from the table lookup
for a given value of r, or can easily be computed recursively <cit.>. 

The sufficient condition in Theorem <ref> yields
an important observation: the privacy guarantee by the MVG mechanism
depends only on the singular values of Σ
and Ψ through their norm. In other words, we may
have multiple instances of ℳ𝒱𝒢_m,n(0,Σ,Ψ)
that yield the exact same privacy guarantee (cf. Figure <ref>).
This phenomenon gives rise to an interesting novel concept of directional
noise, which will be discussed in Section <ref>.

We emphasize again that, in Theorem <ref>, we
derive the sufficient condition for the MVG mechanism to guarantee
(ϵ,δ)-differential privacy without making structural
assumption about the matrix-valued query function. In the next two
sections, we illustrate how incorporating the knowledge about the
intrinsic structural characteristic of the matrix-valued query function
of interest can yield an alternative sufficient condition. Then, we
prove that such alternative sufficient condition can provide the better
utility, when compared to the analysis without using the structural
knowledge.



 §.§ Differential Privacy Analysis for Symmetric Positive Semi-Definite
(PSD) Matrix-Valued Query 


To provide a concrete example of how the structural characteristics
of the matrix-valued query function can be exploited via the MVG mechanism,
we consider a matrix-valued query function that is symmetric
positive semi-definite (PSD). To avoid being cumbersome, we will
drop the explicit 'symmetric' in the subsequent references, but the
readers should keep in mind that we work with symmetric matrices here.
First, let us define a positive semi-definite matrix in our context.

A symmetric matrix 𝐗∈ℝ^n× n is positive
semi-definite (PSD) if 𝐯^T𝐗𝐯≥0
for all non-zero 𝐯∈ℝ^n.

Conceptually, we can think of a positive semi-definite matrix in matrix
analysis as the similar notion to a non-negative number in scalar-valued
analysis. More importantly, positive semi-definite matrices occur
regularly in practical settings. Examples of positive semi-definite
matrices in practice include the maximum likelihood estimate of the
covariance matrix <cit.>, the Hessian matrix
<cit.>, the kernel matrix in machine learning
<cit.>, and the Laplacian matrix of a graph
<cit.>.

With respect to differential privacy analysis, the assumption of positive
semi-definiteness on the query function is only applicable if it holds
for every possible instance of the datasets. Fortunately, this is
true for all of the aforementioned matrix-valued query functions because
the positive semi-definiteness is the intrinsic nature of such
functions. In other words, if a user queries the maximum likelihood
estimate of the covariance matrix of the dataset, the (non-private)
matrix-valued query answer would always be positive semi-definite
regardless of the dataset from which it is computed. The same property
applies to other examples given. We refer to this type of property
as intrinsic to the matrix-valued query function since it holds
due only to the nature of the query function regardless of the nature
of the dataset. This is clearly crucial in differential privacy analysis
as differential privacy considers the worst-case scenario, so any
assumption made would only be valid if it applies even in such scenario.

Before presenting the main result, we emphasize that the intrinsic
nature phenomenon is not unique to positive semi-definite matrix.
In other words, there are many other structural properties of the
matrix-valued query function that are also intrinsic. For example,
the adjacency matrix for an undirected graph is always symmetric <cit.>,
and the bi-stochastic matrix always has all non-negative entries with
each row and column sums up to one <cit.>. Therefore,
the idea of exploiting structural characteristics of the matrix-valued
query function is very applicable in practice under the setting of
privacy-aware analysis.

Returning to the main result, we consider the MVG mechanism on a query
function that is symmetric positive semi-definite. Due to the definitive
symmetry of the query function output, it is reasonable to impose
the design choice Σ=Ψ on the
MVG mechanism. The rationale is that, since the query function is
symmetric, its row-wise covariance and column-wise covariance are
necessarily equal if we view the query output as a random variable.
Hence, it is reasonable to employ the matrix-valued noise with the
same symmetry. As a result, this helps restrict our design space to
that with Σ=Ψ. With this setting,
we present the following theorem which states the sufficient condition
for the MVG mechanism to preserve (ϵ,δ)-differential
privacy when the query function is symmetric positive semi-definite.

 Given a symmetric positive semi-definite
(PSD) matrix-valued query function f(𝐗)∈ℝ^r× r,
let σ(Σ^-1)=[σ_1(Σ^-1),…,σ_r(Σ^-1)]^T
be the vectors of non-increasingly ordered singular values of Σ^-1,
let Ψ=Σ, and let the relevant
variables be defined according to Table <ref>. Then,
the MVG mechanism guarantees (ϵ,δ)-differential privacy
if Σ satisfy the following condition,

    ‖σ(Σ^-1)‖ _2^2≤(-β+√(β^2+8ωϵ))^2/4ω^2,

where ω=4H_rγ s_2(f), and β=2r^1/2ζ(δ)H_rs_2(f). 


The proof starts from the same characteristic equation (Eq. (<ref>))
as in Theorem <ref>. However, since the query
function is symmetric, f(𝐗)=f(𝐗)^T. Furthermore,
since we impose Ψ=Σ, the characteristic
equation can be simplified as, 

    tr[Σ^-1𝒴^TΣ^-1Δ+Σ^-1Δ^TΣ^-1𝒴+Σ^-1f(𝐗_2)Σ^-1f(𝐗_2)-Σ^-1f(𝐗_1)Σ^-1f(𝐗_1)]≤2ϵ.

Again, this condition needs to be met with probability ≥1-δ
for the MVG mechanism to preserve (ϵ,δ)-differential
privacy.

First, consider the first term: tr[Σ^-1𝒴^TΣ^-1Δ].
This term is exactly the same as the first term in the proof of Theorem
<ref>, i.e. the first term of Eq. (<ref>).
Hence, we readily have the upper bound on this term as 

    tr[Σ^-1𝒴^TΣ^-1Δ]≤γ s_2(f)H_r‖σ(Σ^-1)‖ _2^2+m^1/2ζ(δ)H_rs_2(f)‖σ(Σ^-1)‖ _2,

with probability ≥1-δ. We note two minor differences between
Eq. (<ref>) and Eq. (<ref>).
First, the factor of (mn)^1/4 becomes m^1/2. This is simply
due to the fact that n=m in the current setup with a PSD query
function. Second, the variable ϕ=(‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2)^1/2
in Eq. (<ref>) becomes simply ‖σ(Σ^-1)‖ _2
in Eq. (<ref>). This is due to the fact that
Ψ=Σ with the current PSD setting.
Apart from these, Eq. (<ref>) and Eq. (<ref>)
are equivalent.

Second, consider the second term: tr[Σ^-1Δ^TΣ^-1𝒴].
Again, the second term of Eq. (<ref>) is
the same as that of Eq. (<ref>). Hence, we can
readily write,

    tr[Σ^-1Δ^TΣ^-1𝒴]≤γ H_rs_2(f)‖σ(Σ^-1)‖ _2^2+m^1/2ζ(δ)H_rs_2(f)‖σ(Σ^-1)‖ _2,

with probability ≥1-δ. Again, we note the same two differences
between Eq. (<ref>) and Eq. (<ref>)
as those between Eq. (<ref>) and Eq. (<ref>).

Next, consider the third term and fourth term combined:
tr[Σ^-1f(𝐗_2)Σ^-1f(𝐗_2)-Σ^-1f(𝐗_1)Σ^-1f(𝐗_1)].
Let us denote for a moment 𝐀=Σ^-1f(𝐗_2)
and 𝐁=Σ^-1f(𝐗_1). Then,
this combined term can be re-written as, tr[𝐀^2-𝐁^2].
Next, we show that 

    tr[𝐀^2-𝐁^2]=tr[(𝐀-𝐁)(𝐀+𝐁)]

by starting from the right hand side and proceeding to equate it to
the left hand side.

    tr([𝐀-𝐁][𝐀+𝐁])=    tr(𝐀𝐀+𝐀𝐁-𝐁𝐀-𝐁𝐁)
    
    =    tr(𝐀^2)+tr(𝐀𝐁)-tr(𝐁𝐀)-tr(𝐁^2)
    
    =    tr(𝐀^2)+tr(𝐀𝐁)-tr(𝐀𝐁)-tr(𝐁^2)
    
    =    tr(𝐀^2)-tr(𝐁^2)
    
    =    tr(𝐀^2-𝐁^2),

whereas the first-to-second line uses the additive property of the
trace, and the second-to-third line uses the commutative property
of the trace. Therefore, from this equation, we can write 

    tr[Σ^-1f(𝐗_2)Σ^-1f(𝐗_2)-Σ^-1f(𝐗_1)Σ^-1f(𝐗_1)]
    
    =    tr[(Σ^-1f(𝐗_2)-Σ^-1f(𝐗_1))(Σ^-1f(𝐗_2)+Σ^-1f(𝐗_1))]
    
    =    tr[Σ^-1(f(𝐗_2)-f(𝐗_1))Σ^-1(f(𝐗_2)+f(𝐗_1))]
    
    =    tr[Σ^-1Δ̃Σ^-1(f(𝐗_2)+f(𝐗_1))],

where Δ̃=-Δ. Then, we
can use Lemma <ref> to write,

    tr[Σ^-1Δ̃Σ^-1(f(𝐗_2)+f(𝐗_1))]≤∑_i=1^rσ_i(Σ^-1Δ̃)σ_i(Σ^-1(f(𝐗_2)+f(𝐗_1))).

Next, we use Lemma <ref> to bound the two sets
of singular values as follows. For the first set of singular values,

    σ_i(Σ^-1Δ̃)≤‖Σ^-1Δ̃‖ _F/√(i)≤‖Σ^-1‖ _F‖Δ̃‖ _F/√(i)≤‖σ(Σ^-1)‖ _2s_2(f)/√(i),

whereas the last step follows from the fact that ‖Δ̃‖ _F=‖ -Δ‖ _F=‖Δ‖ _F≤ s_2(f).
For the second set of singular values,

    σ_i(Σ^-1(f(𝐗_2)+f(𝐗_1)))    ≤‖Σ^-1(f(𝐗_2)+f(𝐗_1))‖ _F/√(i)
       ≤‖Σ^-1‖ _F‖ (f(𝐗_2)+f(𝐗_1))‖ _F/√(i)
       ≤‖Σ^-1‖ _F(‖ f(𝐗_2)‖ _F+‖ f(𝐗_1)‖ _F)/√(i)
       ≤‖σ(Σ^-1)‖ _22γ/√(i),

whereas the second-to-third line follows from the triangular inequality.
Then, we combine the two bounds on the two sets of singular values
to get a bound for the third term and fourth term combined as,

    tr[Σ^-1f(𝐗_2)Σ^-1f(𝐗_2)-Σ^-1f(𝐗_1)Σ^-1f(𝐗_1)]≤2γ s_2(f)H_r‖σ(Σ^-1)‖ _2.


Four terms combined: by combining the four terms and rearranging
them, the characteristic equation becomes, 

    ω‖σ(Σ^-1)‖ _2^2+β‖σ(Σ^-1)‖ _2≤2ϵ.

This is a quadratic equation, of which the solution is ‖σ(Σ^-1)‖ _2∈[-β-√(β^2+8ωϵ)/2ω,-β+√(β^2+8ωϵ)/2ω].
Since we know that ‖σ(Σ^-1)‖ _2≥0
due to the axiom of the norm, we only have the one-sided solution,

    ‖σ(Σ^-1)‖ _2≤-β+√(β^2+8ωϵ)/2ω,

which immediately implies the criterion in Theorem <ref>. 

The sufficient condition in Theorem <ref> shares
the similar observation to that in Theorem <ref>,
i.e. the privacy guarantee by the MVG mechanism with a positive semi-definite
query function depends only on the singular values of Σ
(and Ψ, effectively). However, the two theorems
differ slightly in that one is a function of α, while the
other is a function of ω. This is clearly the result of the
PSD assumption made by Theorem <ref>, but not by
Theorem <ref>. In the next section, we claim that,
if the matrix-valued query function of interest is positive semi-definite,
it is more beneficial to apply Theorem <ref> than
Theorem <ref> in most practical cases. This fosters
the notion that exploiting the structure of the matrix-valued query
function is attractive.



 §.§ Comparative Analysis on the Benefit of Exploiting Structural Characteristics
of Matrix-Valued Query Functions 


In Section <ref> and
Section <ref>, we discuss
two sufficient conditions for the MVG mechanism to guarantee (ϵ,δ)-differential
privacy in Theorem <ref> and Theorem <ref>,
respectively. The two theorems differ in one significant way –
Theorem <ref> does not utilize the structural
characteristic of the matrix-valued query function, whereas Theorem
<ref> does. More specifically, Theorem <ref>
utilizes the positive semi-definiteness of the matrix-valued query
function.

In this section, we establish the claim that such utilization can
be beneficial to the MVG mechanism for privacy-aware data analysis.
To establish the benefit notion, we first observe that both Theorem
<ref> and Theorem <ref> put an
upper-bound on the singular values σ(Σ^-1)
and σ(Ψ^-1). Let us consider
only σ(Σ^-1) for the moment.
It is well-known that the singular values of an inverted matrix is
the inverse of the singular values, i.e. σ_i(Σ^-1)=1/σ_i(Σ).
Hence, we can write

    ‖σ(Σ^-1)‖ _2=√(∑_i=1^m1/σ_i^2(Σ)).

This representation of ‖σ(Σ^-1)‖ _2
provides a very intuitive view of the sufficient conditions in Theorem
<ref> and Theorem <ref> as follows.

In the MVG mechanism, the privacy preservation is achieved via the
addition of the matrix noise. Higher level of privacy guarantee requires
more perturbation. For additive noise, the notion of “more” here
can be quantified by the variance of the noise. Specifically,
the noise with higher variance provides more perturbation. The last
connection we need to make is that between the notion of the noise
variance and the singular values of the covariance σ_i(Σ).
In Section <ref>, we provide the detail
of this connection. Here, it suffices to say that each singular value
of the covariance matrix, σ_i(Σ), corresponds
to a component of the overall variance of the matrix-variate Gaussian
noise. Therefore, intuitively, the larger the singular values
are, the larger the overall variance becomes, i.e. the higher the
perturbation is. However, there is clearly a tradeoff. Although higher
variance can provide better privacy protection, it can also inadvertently
hurt the utility of the MVG mechanism. In signal-processing terminology,
this degradation of the utility can be described by the reduction
in the signal-to-noise ratio (SNR) due to the increase in the
perturbation level, i.e. the increase in noise variance. Hence, our
notion of better MVG mechanism, and, more broadly, better
mechanism for differential privacy, corresponds to that of higher
SNR as follows.

A differential-private mechanism
has the higher signal-to-noise ratio (SNR) if it employs the perturbation
with the lower variance.

With this axiom and the given intuition about σ_i(Σ),
let us revisit Eq. (<ref>). To achieve
low noise variance, σ_i(Σ) needs to be
as low as possible. From Eq. (<ref>),
it is clear that low σ_i(Σ) corresponds
to large ‖σ(Σ^-1)‖ _2.
Hence, from Axiom <ref>, it is desirable
to have ‖σ(Σ^-1)‖ _2
as large as possible, while still preserving differential privacy.
However, the sufficient conditions in Theorem <ref>
and Theorem <ref> put the (different) constraints
on how large ‖σ(Σ^-1)‖ _2
can be in order to preserve (ϵ,δ)-differential privacy.
Then, clearly, for fixed (ϵ,δ), the better mechanism
according to Axiom <ref> is the one with
the higher upper-bound on ‖σ(Σ^-1)‖ _2.
Therefore, we establish the following axiom for our comparative analysis.

For the MVG mechanism, the (ϵ,δ)-differential
privacy sufficient condition with the higher SNR is the one with the
larger upper-bound on ‖σ(Σ^-1)‖ _2
and ‖σ(Ψ^-1)‖ _2
for any fixed (ϵ,δ).

Then, we can now return to the main objective of this section, i.e.
to establish the benefit of exploiting structural characteristics
of matrix-valued query functions. Recall that the main difference
in the setup of Theorem <ref> and Theorem <ref>
is that the former does not utilize the structural characteristic
of the matrix-valued query function, while the latter utilizes the
positive semi-definiteness characteristic. As a result, Theorem <ref>
and Theorem <ref> have different sufficient conditions.
More specifically, taken into the fact that Ψ=Σ
in the setting of Theorem <ref>, the two sufficient
conditions only differ by the upper-bound they constrain on how large
‖σ(Σ^-1)‖ _2
and ‖σ(Ψ^-1)‖ _2
can be. Therefore, to compare the two sufficient conditions, we only
need to compare their upper-bounds. The following theorem presents
the main result of this comparison.

Let f(𝐗)∈ℝ^r× r
be a symmetric positive semi-definite matrix-valued query function.
Then, the MVG mechanism on f(𝐗) implemented by Theorem
<ref> – which utilizes the PSD characteristic
– has higher SNR than that implemented by Theorem <ref>
– which does not utilize the PSD characteristic, if one
of the following conditions is met:

    s_2(f)≤γ

or

    r>12.



Recall that the two upper-bounds are (-β+√(β^2+8αϵ))^2/4α^2
and (-β+√(β^2+8ωϵ))^2/4ω^2 for
Theorem <ref> and Theorem <ref>,
respectively. Recall also that both upper-bounds are derived from
their respective quadratic equations (Eq. (<ref>)
and Eq. (<ref>)). The proof is considerably
simpler if we start from these two quadratic equations. 

We first restate the two quadratic equations again here for Theorem
<ref> and Theorem <ref>, respectively:

    αϕ^2+βϕ-2ϵ   ≤0
    ωϕ^2+βϕ-2ϵ   ≤0.

Note that in the current setup, f(𝐗)∈ℝ^r× r
and Ψ=Σ, so ϕ=‖σ(Σ^-1)‖ _2
in both theorems. Then, we use a lesser-known formula for finding
roots of a quadratic equation, which has appeared in the Muller's
method for root-finding algorithm <cit.> and Vieta's
formulas for polynomial coefficient relations <cit.>.

    ϕ∈[4ϵ/β+√(β^2+8αϵ),4ϵ/β-√(β^2+8αϵ)],

and 

    ϕ∈[4ϵ/β+√(β^2+8ωϵ),4ϵ/β-√(β^2+8ωϵ)],

for Eq. (<ref>) and Eq. (<ref>),
respectively. Since we know that ϕ≥0 in both cases due to
the axiom of the norm, we have a one-sided solution for both as,

    ϕ≤4ϵ/β-√(β^2+8αϵ),

and 

    ϕ≤4ϵ/β-√(β^2+8ωϵ),

for Eq. (<ref>) and Eq. (<ref>),
respectively. These two solutions are particularly simple to compare
since they are similar except for the term α and ω
in the denominator. Recall from Axiom <ref> that the
better MVG mechanism is the one with the larger upper-bound. Hence,
from Eq. (<ref>) and Eq. (<ref>), we
want to show that,

    4ϵ/β-√(β^2+8ωϵ)≥4ϵ/β-√(β^2+8αϵ).

The denominator is always positive since ϵ,θ,α>0,
so we can simplify this condition as follows.

    4ϵ/β-√(β^2+8ωϵ)   ≥4ϵ/β-√(β^2+8αϵ)
    β-√(β^2+8αϵ)   ≥β-√(β^2+8ωϵ)
    β^2+8αϵ   ≥β^2+8ωϵ
    α   ≥ω.

Substitute in the definition of α and ω and we have,

    [H_r+H_r,1/2]γ^2+2H_rγ s_2(f)    ≥4H_rγ s_2(f)
    
    [H_r+H_r,1/2]γ^2   ≥2H_rγ s_2(f)
    
    [H_r+H_r,1/2]γ   ≥2H_rs_2(f).

From the inequality in Eq. (<ref>), we can
take two routes to ensure that this inequality is satisfied, and that
gives rise to the two either-or conditions in Theorem <ref>.
We explore each route separately next.

Route I. First, let us consider the relationship between γ
and s_2(f) for PSD query functions, and show that, for PSD matrix-valued
query functions, s_2(f)≤√(2)γ. From the definition
of the Frobenius norm,

    s_2(f)=    sup_d(𝐗_1,𝐗_2)=1‖𝐗_1-𝐗_2‖ _F
    
    =    sup_d(𝐗_1,𝐗_2)=1√(tr[(𝐗_1-𝐗_2)(𝐗_1-𝐗_2)^T])
    
    =    sup_d(𝐗_1,𝐗_2)=1√(tr[𝐗_1𝐗_1^T-𝐗_1𝐗_2^T-𝐗_2𝐗_1^T+𝐗_2𝐗_2^T])
    
    =    sup_d(𝐗_1,𝐗_2)=1√(tr[𝐗_1𝐗_1^T]-2tr[𝐗_1𝐗_2^T]+tr[𝐗_2𝐗_2^T])

Since both 𝐗_1 and 𝐗_2 are PSD, 𝐗_1𝐗_2^T
is also PSD <cit.>. Hence, it follows from a property
of the trace and the PSD matrix that, 

    tr[𝐗_1𝐗_2^T]=∑λ_i(𝐗_1𝐗_2^T)≥0.

With this fact, along with the fact that ‖𝐗‖ _F=√(tr(𝐗𝐗^T))≤γ,
it immediately follows that,

    s_2(f)≤√(tr[𝐗_1𝐗_1^T]+tr[𝐗_2𝐗_2^T])≤√(2γ^2)=√(2)γ.

Next, let us return to the inequality in Eq. (<ref>)
and substitute in s_2(f)≤√(2)γ.

    [H_r+H_r,1/2]γ   ≥2√(2)H_rγ
    
    H_r+H_r,1/2   ≥2√(2)H_r
    
    H_r,1/2   ≥(2√(2)-1)H_r.

Using the definition of the harmonic number, we can write

    ∑_i=1^r1/√(r)≥(2√(2)-1)∑_i=1^r1/r.

Since 1/√(r)>1/r for all r>1, it is clear
that this condition is met for all r greater than a certain threshold.
The threshold can easily be acquired numerically or analytically to
be r>12. This completes the proof of the first route.

Route II. Second, we use the fact that 1/√(r)≥1/r
for r>0. Then, it is clear from the definition of the harmonic
number that H_r,1/2≥ H_r. Hence, we can write the inequality
in Eq. (<ref>) as,

    [H_r+H_r,1/2]γ   ≥2H_rs_2(f)
    
    2H_rγ   ≥2H_rs_2(f)
    γ   ≥ s_2(f),

which immediately completes the proof of the second route.

One final necessary remark regarding this comparative analysis is
to justify the practicality of the conditions in Theorem <ref>.
We reiterate that only one of the two conditions needs to be
met and discuss separately the practicality of each. 

The first condition, i.e s_2(f)≤γ, can be interpret
conceptually as that the sensitivity should not be greater than the
largest value of the query output. Two observations support the pragmatism
of this condition. First, the sensitivity is derived from the change
in the query output when only one input record changes. Intuitively,
this suggests that such change should be confined to the largest possible
value of the query output, especially for a positive semi-definite
query function whose output is always non-negative. Second, one of
the premises of differential privacy for statistical query is that
the query can be answered accurately if the sensitivity of such query
is small <cit.>. Hence, this condition coincides properly
with the primary premise of differential privacy. To concretely illustrate
its practicality, we consider two examples of matrix-valued query
functions as follows.

Let us consider a dataset consisting of n records
drawn i.i.d. from an unknown ℝ^m distribution with zero
mean, and consider the covariance estimation as the query function
<cit.>, i.e. f(𝐗)=𝐗𝐗^T/n.
Let us assume without the loss of generality that 𝐗∈[-c,c]^m× n.
Then, the largest query output value can be computed as,

    γ=sup_𝐗‖𝐗𝐗^T/n‖ _F=sup_𝐗‖1/n∑_i=1^n𝐱_i𝐱_i^T‖ _F=mc^2.

Next, the sensitivity can be computed by considering that f(𝐗)=1/n𝐗𝐗^T=1/n∑_i=1^n𝐱_i𝐱_i^T.
Hence, for neighboring datasets 𝐗 and 𝐗',
the query outputs differ by only one summand and the sensitivity can
be computed as,

    s_2(f)=sup_𝐗,𝐗'‖𝐱_j𝐱_j^T-𝐱_j'𝐱_j'^T‖ _F/n≤2√(∑_j=1^m^2x_j(i)^4)/n=2mc^2/n.

Clearly, s_2(f)≪γ for any reasonably-sized dataset.



Let us consider the kernel matrix often used
in machine learning <cit.>. Given a kernel
function k(𝐱_i,𝐱_j)∈ℝ, the kernel
matrix query is f(𝐗)=𝐆∈ℝ^n× n,
where [𝐆]_ij=k(𝐱_i,𝐱_j). We note
that the notation [·]_ij indicates the [i^th,j^th]-element
of the matrix. Let us assume further without the loss of generality
that k(𝐱_i,𝐱_j)≤ c. Then, the largest
query output value can be computed as,

    γ=sup_𝐗‖𝐆‖ _F=sup√(∑_i,jk(𝐱_i,𝐱_j)^2)=nc.

Next, the sensitivity can be computed by considering that the [i^th,j^th]-element
of the matrix 𝐆 only depends on 𝐱_i,𝐱_j∈𝐗,
but not on any other record. Hence, for neighboring datasets 𝐗
and 𝐗', the query outputs differ by only one row and column.
Then, the sensitivity can be computed as,

    s_2(f)=sup_𝐗,𝐗'‖𝐆-𝐆'‖ _F=sup√(2∑_i=1^n4k(𝐱_k,𝐱_i)^2-4k(𝐱_k,𝐱_k)^2)=c√(8n-4).

From the values of γ and s_2(f), it can easily be shown
that s_2(f)<γ for n>7. For the kernel matrix used in
machine learning, n corresponds to the number of samples in the
dataset. Clearly, in practice, the dataset has considerably more than
7 samples, so this condition is always met for the kernel matrix query
function.


Next, let us consider the second condition, i.e. r>12, which
simply states that the dimension of the positive semi-definite matrix-valued
query function should be larger than 12. This can be justified simply
by noting that many real-world positive semi-definite matrix-valued
query functions have dimensions significantly larger than 12. For
example, as seen in Example <ref> and Example <ref>,
the dimensions of the covariance matrix and the kernel matrix depend
on the number of features and data samples, respectively. Both quantities
are generally considerably larger than 12 in practice. Similarly,
the Laplacian matrix of a graph has its dimension depending upon the
number of nodes in the graph, which is usually considerably larger
than 12 <cit.>.

Finally, we emphasize that only one of the two conditions,
i.e. s_2(f)≤γ or r>12, needs to be satisfied in order
for the MVG mechanism to fully exploit the positive semi-definiteness
characteristic of the matrix-valued query function. As we have shown,
this poses little restriction in practice.

As a segue to the next section, we revisit the sufficient conditions
for the MVG mechanism to guarantee (ϵ,δ)-differential
privacy in Theorem <ref> and Theorem <ref>.
In both theorems, the sufficient conditions put an upper-bound only
on the singular values of the two covariance matrices Σ
and Ψ. We briefly describe in this section that
each singular value can be interpret as a variance of the noise. In
the next section, we provide a detailed analysis on this interpretation
and how it can be exploited for the application of privacy-aware data
analysis with the MVG mechanism.



§ DIRECTIONAL NOISE FOR MATRIX-VALUED QUERY 


Recall from the differential privacy analysis of the MVG mechanism
(Theorem <ref> and Theorem <ref>)
that the sufficient conditions for the MVG mechanism to guarantee
(ϵ,δ)-differential privacy in both theorems only apply
to the singular values of the two covariance matrices Σ
and Ψ. Here, we investigate the ramification of
this result via the novel notion of directional noise.



 §.§ Motivation for Non-i.i.d. Noise for Matrix-Valued Query


For a matrix-valued query function, the standard method for basic
mechanisms that use additive noise is by adding the independent
and identically distributed (i.i.d.) noise to each element of the
matrix query. However, as common in matrix analysis <cit.>,
the matrices involved often have some geometric and algebraic characteristics
that can be exploited. As a result, it is usually the case that only
certain “parts” – the term which will be defined more
precisely shortly – of the matrices contain useful information.
In fact, this is one of the rationales behind many compression techniques
such as the popular principal component analysis (PCA) <cit.>.
Due to this reason, adding the same amount of noise to every “part”
of the matrix query may be highly suboptimal.



 §.§ Directional Noise as a Non-i.i.d. Noise






Let us elaborate further on the “parts” of a matrix. In matrix
analysis, the prevalent paradigm to extract underlying properties
of a matrix is via matrix factorization <cit.>.
This is a family of algorithms and the specific choice depends upon
the application and types of insights it requires. Particularly, in
our application, the factorization that is informative is the singular
value decomposition (SVD) (Theorem <ref>) of the two covariance
matrices of ℳ𝒱𝒢_m,n(0,Σ,Ψ).

Consider first the covariance matrix Σ∈ℝ^m× m,
and write its SVD as, Σ=𝐖_1Λ𝐖_2^T.
It is well-known that, for the covariance matrix, we have the equality
𝐖_1=𝐖_2 since it is positive definite (cf.
<cit.>). Hence, let us more concisely write
the SVD of Σ as, 

    Σ=𝐖_ΣΛ_Σ𝐖_Σ^T.

This representation gives us a very useful insight to the noise generated
from ℳ𝒱𝒢_m,n(0,Σ,Ψ):
it tells us the directions of the noise via the column vectors
of 𝐖_Σ, and variance of the
noise in each direction via the singular values in Λ_Σ.

For simplicity, let us consider a two-dimensional multivariate Gaussian
distribution, i.e. m=2, so there are two column vectors of 𝐖_Σ=[𝐰_Σ1,𝐰_Σ2].
The geometry of this distribution can be depicted by an ellipsoid,
e.g. the dash contour in Figure <ref>, Left
(cf. <cit.>, <cit.>). This
ellipsoid is characterized by its two principal axes –
the major and the minor axes. It is well-known that the two column
vectors from SVD, i.e. 𝐰_Σ1 and 𝐰_Σ2,
are unit vectors pointing in the directions of the major and minor
axes of this ellipsoid, and more importantly, the length of each axis
is characterized by its corresponding singular value, i.e. σ_Σ1
and σ_Σ2, respectively (cf. <cit.>)
(recall from Theorem <ref> that diag(Λ_Σ)=[σ_Σ1,σ_Σ2]).
This is illustrated by Figure <ref>, Left.
Therefore, when we consider the noise generated from this 2D multivariate
Gaussian distribution, we arrive at the following interpretation of
the SVD of its covariance matrix: the noise is distributed toward
the two principal directions specified by 𝐰_Σ1
and 𝐰_Σ2, with the variance
scaled by the corresponding singular values, σ_Σ1
and σ_Σ2.

We can extend this interpretation to a more general case with m>2,
and also to the other covariance matrix Ψ. Then,
we have a full interpretation of ℳ𝒱𝒢_m,n(0,Σ,Ψ)
as follows. The matrix-valued noise distributed according to ℳ𝒱𝒢_m,n(0,Σ,Ψ)
has two components: the row-wise noise, and the column-wise
noise. The row-wise noise and the column-wise noise are characterized
by the two covariance matrices, Σ and Ψ,
respectively, as follows.



  §.§.§ For the row-wise noise



  * The row-wise noise is characterized by Σ. 

  * SVD of Σ=𝐖_ΣΛ_Σ𝐖_Σ^T
decomposes the row-wise noise into two components – the
directions and the variances of the noise in those directions. 

  * The directions of the row-wise noise are specified by the column
vectors of 𝐖_Σ. 

  * The variance of each row-wise-noise direction is indicated
by its corresponding singular value in Λ_Σ. 




  §.§.§ For the column-wise noise



  * The column-wise noise is characterized by Ψ. 

  * SVD of Ψ=𝐖_ΨΛ_Ψ𝐖_Ψ^T
decomposes the column-wise noise into two components –
the directions and the variances of the noise in those directions. 

  * The directions of the column-wise noise are specified by the
column vectors of 𝐖_Ψ. 

  * The variance of each column-wise-noise direction is indicated
by its corresponding singular value in Λ_Ψ. 

Since ℳ𝒱𝒢_m,n(0,Σ,Ψ)
is fully characterized by its covariances, these two components of
the matrix-valued noise drawn from ℳ𝒱𝒢_m,n(0,Σ,Ψ)
provide a complete interpretation of the matrix-variate Gaussian noise.



 §.§ Directional Noise via the MVG Mechanism 


With the notion of directional noise, we now revisit Theorem <ref>
and Theorem <ref>. Recall that the sufficient conditions
for the MVG mechanism to preserve (ϵ,δ)-differential
privacy according to both theorems put the constraint only on the
singular values of Σ and Ψ.
However, as we discuss in the previous section, the singular values
of Σ and Ψ only indicate the
variance of the noise in each direction, but not the
directions they are attributed to. In other words, Theorem <ref>
and Theorem <ref> suggest that the MVG mechanism
preserves (ϵ,δ)-differential privacy as long
as the overall variances of the noise satisfy a certain threshold,
but these variances can be attributed non-uniformly in any direction.

This major claim certainly warrants further discussion, and we will
defer it to Section <ref>, where we
present the technical detail on how to actually implement this concept
of directional noise in practical settings. It is important to only
note here that this claim does not mean that we can avoid adding
noise in any particular direction altogether. On the contrary, there
is still a minimum amount of noise required in every direction
for the MVG mechanism to guarantee differential privacy, but the noise
simply can be attributed unevenly in different directions (cf. Fig.
<ref>, Right, for an example).

Finally, with the understanding of directional noise via the MVG mechanism,
we can revisit the discussion in Sec. <ref>.
Conceptually, the sufficient conditions in Theorem <ref>
and Theorem <ref> impose a threshold on the minimum
overall variance of the noise in every direction. Therefore, intuitively,
to achieve the most utility out of the noisy query output, we want
the threshold to be as low as possible (cf. Figure <ref>,
Right). As discussed in Section <ref>,
since both sufficient conditions put the constraint upon the inverse
of the variance, this means that we want the upper-bound of the sufficient
conditions to be as large as possible for maximum utility, and, hence,
the derivation of Theorem <ref>.



 §.§ Utility Gain via Directional Noise 


As the concept of the directional noise is established, one important
remaining question is how we can exploit this to enhance the utility
of differential privacy. The answer to this question depends on the
query function. Here, we present examples for two popular matrix-valued
query functions: the identity query and the covariance matrix.



  §.§.§ Identity Query


Formally, the identity query is f(𝐗)=𝐗. We illustrate
how to exploit directional noise for enhancing utility via the following
two examples. 

Consider the personalized warfarin dosing problem <cit.>,
which can be considered as the regression problem with the identity
query. In the i.i.d. noise scheme, every feature used in the warfarin
dosing prediction is equally perturbed. However, domain experts may
have prior knowledge that some features are more critical than the
others, so adding directional noise designed such that the more critical
features are perturbed less can potentially yield better prediction
performance. 

We note from this example that the directions chosen here are among
the standard basis, e.g. 𝐞_1=[1,0,…,0]^T,𝐞_2=[0,1,…,0]^T,
which is one of the simplest forms of directions. Moreover, the directions
in this example are decided based on the domain expertise. When domain
knowledge is unavailable, we may still identify the useful directions
by spending a fraction of the privacy budget on deriving the directions. 

Consider again the warfarin dosing problem <cit.>, and
assume that we do not possess any prior knowledge about the predictive
features. We can still learn this information from the data by spending
a small privacy budget on deriving differentially-private principal
components (P.C.) from available differentially-private PCA algorithms
<cit.>.
Each P.C. can then serve as a direction and, with directional noise,
we can selectively add less noise in the highly informative directions
as indicated by PCA. 

As opposed to the previous example, the directions in this example
are not necessary among the standard basis, but can be any unit
vector. Nevertheless, this example illustrates how directional noise
can provide additional utility benefit even with no assumption on
the prior knowledge.

Figure <ref>, Middle, illustrates an example
of how directional noise can provide the utility gain over i.i.d.
noise. In the illustration, we assume the data with two features,
and assume that we have obtained the utility direction, e.g. from
PCA, represented by the green line. This can be considered as the
utility subspace we desire to be least perturbed. The many small circles
in the illustration represent how the i.i.d. noise and directional
noise are distributed under the 2D multivariate Gaussian distribution.
Clearly, directional noise can reduce the perturbation experienced
on the utility subspace when compared to the i.i.d. noise.



  §.§.§ Covariance Matrix


Let us consider a slightly more involved matrix-valued query similar
to Example <ref>: the covariance matrix, i.e. f(𝐗)=1/n𝐗𝐗^T.
Here, we consider the dataset with n samples and m features.
The following example illustrates how we can utilize directional noise
for this query function. 

Consider the Netflix prize dataset <cit.>.
A popular method for solving the Netflix challenge is via the low-rank
approximation <cit.>. One way to perform this method
is to query the covariance matrix of the dataset <cit.>.
Suppose we use output perturbation to preserve differential privacy,
i.e. 𝒜(f(𝐗))=f(𝐗)+𝒵, and
suppose we have prior knowledge from domain experts that some features
are more informative than the others. Since the covariance matrix
has the underlying property that each row and column correspond to
a single feature <cit.>, we can use this prior knowledge
with directional noise by adding less noise to the rows and columns
corresponding to the informative features. 

This example emphasizes the usefulness of the concept of directional
noise even when the query function is more complex than the simple
identity query.

In the recent three examples, we derive the directions for the noise
either from PCA or prior knowledge. PCA, however, is probably only
suitable to the data-release type of query, e.g. the identity query.
It is, therefore, still unclear how to derive the directions of the
noise for a general matrix-valued query function when prior knowledge
may not be available. We discuss a possible solution to this problem
in the next section.



  §.§.§ Directional Noise for General Matrix-Valued Query




For a general matrix-valued query function, one general possible approach
to derive the directions of the noise is to use the SVD. As discussed
in Section <ref>, SVD can decompose a matrix
into its directions and variances. Hence, for a general matrix-valued
query function, we can cast aside a small portion of privacy budget
to derive the directions from the SVD of the query function. Clearly,
the direction-derivation process via SVD needs to be private. Fortunately,
there have been many works on differentially-private SVD <cit.>.
We experimentally demonstrate the feasibility of the approach in Section
<ref>.

In the next section, we discuss how we implement directional noise
with the MVG mechanism in practice and propose two simple algorithms
for two types of directional noise.



§ PRACTICAL IMPLEMENTATION OF MVG MECHANISM 


The differential privacy condition in Theorem <ref>
and Theorem <ref>, even along with the notion of
directional noise in the previous section, still leads to a large
design space for the MVG mechanism. In this section, we present two
simple algorithms to implement the MVG mechanism with two types of
directional noise that can be appropriate for a wide range of real-world
applications. Then, we conclude the section with a discussion on the
sampling algorithms for ℳ𝒱𝒢_m,n(0,Σ,Ψ)
necessary for the practical implementation of our mechanism.

As discussed in Section <ref>, Theorem <ref>
and Theorem <ref> state that the MVG mechanism satisfies
(ϵ,δ)-differential privacy as long as the singular
values of the row-wise and column-wise covariance matrices satisfy
the sufficient condition. This provides tremendous flexibility in
the choice of the directions of the noise. First, we notice
from the sufficient condition in Theorem <ref>
that the singular values for Σ and Ψ
are decoupled, i.e. they can be designed independently, whereas Theorem
<ref> explicitly imposes Ψ=Σ.
Hence, the row-wise noise and column-wise noise can
be considered as the two modes of noise in the MVG mechanism.
By this terminology, we discuss two types of directional noise: the
unimodal and equi-modal directional noise.



 §.§ Unimodal Directional Noise 


For the unimodal directional noise, we select one mode of the
noise to be directional noise, whereas the other mode of the noise
is set to be i.i.d. For this discussion, we assume that the row-wise
noise is directional noise, while the column-wise noise is i.i.d.
However, the opposite case can be readily analyzed with the similar
analysis. Furthermore, for simplicity, we only consider the differential
privacy guarantee provided by Theorem <ref> for
the unimodal directional noise.

We note that, apart from simplifying the practical implementation
that we will discuss shortly, this type of directional noise can be
appropriate for many applications. For example, for the identity query,
we may not possess any prior knowledge on the quality of each sample,
so the best strategy would be to consider the i.i.d. column-wise noise
(recall that in our notation, samples are the column vectors).

Formally, the unimodal directional noise sets Ψ=𝐈_n,
where 𝐈_n is the n× n identity matrix. This,
consequently, reduces the design space for the MVG mechanism with
directional noise to only the design of Σ. Next,
consider the left side of the sufficient condition in Theorem <ref>,
and we have 

    ‖σ(Σ^-1)‖ _2=√(∑_i=1^m1/σ_i^2(Σ)) , and ‖σ(Ψ^-1)‖ _2=√(n).

If we square both sides of the sufficient condition and re-arrange
it, we get a form of the condition such that the row-wise noise in
each direction is completely decoupled: 

    ∑_i=1^m1/σ_i^2(Σ)≤1/n(-β+√(β^2+8αϵ))^4/16α^4.


This form gives a very intuitive interpretation of the directional
noise. First, we note that, to have small noise in the i^th direction,
σ_i(Σ) has to be small (cf. Section <ref>).
However, the sum of 1/σ_i^2(Σ) of the
noise in all directions, which should hence be large, is limited by
the quantity on the right side of Eq. (<ref>).
This, in fact, explains why even with directional noise, we still
need to add noise in every direction to guarantee differential
privacy. Consider the case when we set the noise in one direction
to be zero, and we have σ→0lim1/σ=∞,
which immediately violates the sufficient condition in Eq. (<ref>).

From Eq. (<ref>), the quantity 1/σ_i^2(Σ)
is the inverse of the variance of the noise in the i^th direction,
so we may think of it as the precision measure of the query
answer in that direction. The intuition is that the higher this value
is, the lower the noise added in that direction, and, hence, the more
precise the query value in that direction is. From this description,
the constraint in Eq. (<ref>) can be aptly
named as the precision budget, and we immediately have the
following theorem. 

For the MVG mechanism with Ψ=𝐈_n, the
precision budget is (-β+√(β^2+8αϵ))^4/(16α^4n). 

Finally, the remaining task is to determine the directions of the
noise and form Σ accordingly. To do so systematically,
we first decompose Σ by SVD as, 

    Σ=𝐖_ΣΛ_Σ𝐖_Σ^T.

This decomposition represents Σ by two components
– the directions of the row-wise noise indicated by 𝐖_Σ,
and the variance of the noise indicated by Λ_Σ.
Since the precision budget only puts constraint upon Λ_Σ,
this decomposition allows us to freely chose any unitary matrix for
𝐖_Σ such that each column of 𝐖_Σ
indicates each independent direction of the noise.

Therefore, we present the following simple approach to design the
MVG mechanism with the unimodal directional noise: under a given precision
budget, allocate more precision to the directions of more importance.

Algorithm <ref> formalizes this procedure.
It takes as inputs, among other parameters, the precision allocation
strategy θ∈(0,1)^m, and the directions
𝐖_Σ∈ℝ^m× m. The
precision allocation strategy is a vector of size m, whose elements,
θ_i∈(0,1), corresponds to the importance of the i^th
direction indicated by the i^th orthonormal column vector of
𝐖_Σ. The higher the value of θ_i,
the more important the i^th direction is. Moreover, the algorithm
enforces that ∑_i=1^mθ_i≤1 to ensure that we do
not overspend the precision budget. The algorithm, then, proceeds
as follows. First, compute α and β and, then, the precision
budget P. Second, assign precision to each direction based on the
precision allocation strategy. Third, derive the variance of the noise
in each direction accordingly. Then, compute Σ
from the noise variance and directions, and draw a matrix-valued noise
from ℳ𝒱𝒢_m,n(0,Σ,𝐈).
Finally, output the query answer with additive matrix noise.

We make a remark here about choosing directions of the noise. As discussed
in Section <ref>, any orthonormal set of vectors
can be used as the directions. The simplest instance of such set is
the the standard basis vectors, e.g. 𝐞_1=[1,0,0]^T,𝐞_2=[0,1,0]^T,𝐞_3=[0,0,1]^T
for ℝ^3.





 §.§ Equi-Modal Directional Noise 


Next, we consider the type of directional noise of which the row-wise
noise and column-wise noise are distributed identically, which we
call the equi-modal directional noise. We recommend this type of directional
noise for a symmetric query function, i.e. f(𝐗)=f(𝐗)^T∈ℝ^m× m.
This covers a wide-range of query functions including the covariance
matrix <cit.>, the kernel
matrix <cit.>, the adjacency matrix of an undirected
graph <cit.>, and the Laplacian matrix <cit.>.
The motivation for this recommendation is that, for symmetric query
functions, any prior information about the rows would similarly apply
to the columns, so it is reasonable to use identical row-wise and
column-wise noise. Since Theorem <ref> considers
the symmetric positive semi-definite matrix-valued query function,
the equi-modal directional noise can be used with both Theorem <ref>
and Theorem <ref>. However, we note that to use the
equi-modal directional noise with Theorem <ref>,
the matrix-valued query function also has to be positive semi-definite.

Formally, this type of directional noise imposes that Ψ=Σ.
Following a similar derivation to the unimodal type, we have the following
precision budget. 

 For the MVG mechanism with Ψ=Σ,
the precision budget is (-β+√(β^2+8αϵ))^2/(4α^2)
with Theorem <ref>, or (-β+√(β^2+8ωϵ))^2/(4ω^2)
with Theorem <ref>.

We emphasize again that the choice between applying Theorem <ref>
or Theorem <ref> for the precision budget depends
on the particular query function, as discussed in Sec. <ref>.
Then, following a similar procedure to the unimodal type, we present
Algorithm <ref> for the MVG mechanism with
the equi-modal directional noise. The algorithm follows the same steps
as Algorithm <ref>, except it derives the
precision budget from Theorem <ref>, and draws the
noise from ℳ𝒱𝒢_m,m(0,Σ,Σ).





 §.§ Sampling from ℳ𝒱𝒢_m,n(0,Σ,Ψ)



One remaining question on the practical implementation of the MVG
mechanism is how to efficiently draw the noise from ℳ𝒱𝒢_m,n(0,Σ,Ψ).
Here, we present two methods to implement the ℳ𝒱𝒢_m,n(0,Σ,Ψ)
samplers from currently available samplers of other distributions.
The first is based on the equivalence between ℳ𝒱𝒢_m,n(0,Σ,Ψ)
and the multivariate Gaussian distribution, and the second is based
on the affine transformation of the i.i.d. normal distribution.



  §.§.§ Sampling via the Multivariate Gaussian


This method uses the equivalence between ℳ𝒱𝒢_m,n(0,Σ,Ψ)
and the multivariate Gaussian distribution via the vectorization operator
vec(·), and the Kronecker product ⊗ <cit.>.
The relationship is described by the following lemma <cit.>. 

𝒳∼ℳ𝒱𝒢_m,n(𝐌,Σ,Ψ)
if and only if vec(𝒳)∼𝒩_mn(vec(𝐌),Ψ⊗Σ),
where 𝒩_mn(vec(𝐌),Ψ⊗Σ)
denotes the mn-dimensional multivariate Gaussian distribution with
mean vec(𝐌) and covariance Ψ⊗Σ. 

There are many available packages that implement the 𝒩_mn(vec(𝐌),Ψ⊗Σ)
samplers <cit.>, so this relationship
allows us to use them to build a sampler for ℳ𝒱𝒢_m,n(0,Σ,Ψ).
To do so, we take the following steps: 


  * Convert the desired ℳ𝒱𝒢_m,n(0,Σ,Ψ)
into its equivalent 𝒩_mn(vec(𝐌),Ψ⊗Σ). 

  * Draw a sample from 𝒩_mn(vec(𝐌),Ψ⊗Σ). 

  * Convert the vectorized sample into its matrix form. 

The computational complexity of this sampling method depends on the
multivariate Gaussian sampler used. Plus, the Kronecker product has
an extra complexity of 𝒪(m^2n^2) <cit.>.



  §.§.§ Sampling via the Affine Transformation of the i.i.d. Normal Noise


 The second method to implement a sampler
for ℳ𝒱𝒢_m,n(0,Σ,Ψ)
is via the affine transformation of samples drawn i.i.d. from the
standard normal distribution, i.e. 𝒩(0,1). The transformation
is described by the following lemma <cit.>. 

Let 𝒩∈ℝ^m× n be a matrix-valued random
variable whose entries are drawn i.i.d. from the standard normal distribution
𝒩(0,1). Then, the matrix 𝒵=𝐁_Σ𝒩𝐁_Ψ^T
is distributed according to 𝒵∼ℳ𝒱𝒢_m,n(0,𝐁_Σ𝐁_Σ^T,𝐁_Ψ𝐁_Ψ^T). 

This transformation consequently allows the conversion between mn
samples drawn i.i.d. from 𝒩(0,1) and a sample drawn from
ℳ𝒱𝒢_m,n(0,𝐁_Σ𝐁_Σ^T,𝐁_Ψ𝐁_Ψ^T).
To derive 𝐁_Σ and 𝐁_Ψ
from given Σ and Ψ for ℳ𝒱𝒢_m,n(0,Σ,Ψ),
we solve the two linear equations: 𝐁_Σ𝐁_Σ^T=Σ,
and 𝐁_Ψ𝐁_Ψ^T=Ψ,
and the solutions of these two equations can be acquired readily via
the Cholesky decomposition or SVD (cf. <cit.>). We summarize
the steps for this implementation here using SVD: 


  * Draw mn samples from 𝒩(0,1), and form a matrix 𝒩. 

  * Let 𝐁_Σ=𝐖_ΣΛ_Σ^1/2
and 𝐁_Ψ=𝐖_ΨΛ_Ψ^1/2,
where 𝐖_Σ,Λ_Σ
and 𝐖_Ψ,Λ_Ψ
are derived from SVD of Σ and Ψ,
respectively. 

  * Compute the sample 𝒵=𝐁_Σ𝒩𝐁_Ψ^T. 

The complexity of this method depends on that of the 𝒩(0,1)
sampler used. Plus, there is an additional 𝒪(max{m^3,n^3})
complexity from SVD <cit.>.



 §.§ Complexity Analysis


Comparing the complexity of the two sampling methods presented in
Section <ref>, it is apparent that the choice
between the two methods depends primarily on the values of m and
n. From this, we can show that Algorithm <ref>
is 𝒪(min{max{m^3,n^3},(mn)^2}}), while Algorithm
<ref> is 𝒪(m^3) as follows.

For Algorithm <ref>, the two most expensive
steps are the matrix multiplication in step 5 and the sampling in
step 6. The multiplication in step 5 is 𝒪(m^3), while
the sampling in step 6 is 𝒪(min{max{m^3,n^3},(mn)^2}})
if we pick the faster sampling methods among the two presented in
Section <ref>. Hence, the complexity of
Algorithm <ref> is 𝒪(min{max{m^3,n^3},(mn)^2}}).

For Algorithm <ref>, the two most expensive
steps are similarly the matrix multiplication in step 5 and the sampling
in step 6. The multiplication in step 5 is 𝒪(m^3),
while the sampling in step 6 is 𝒪(m^3) if we use the
affine transformation method (cf. Section <ref>).
Hence, the complexity of Algorithm <ref>
is 𝒪(m^3).



§ THE DESIGN OF THE PRECISION ALLOCATION STRATEGY


Algorithm <ref> and Algorithm <ref>
take as an input the precision allocation strategy θ∈(0,1)^m:|θ|_1=1.
As discussed in Section <ref>,
elements of θ are chosen to emphasize how informative
or useful each direction is. The design of θ
to optimize the utility gain via the directional noise is an interesting
topic for future research. For example, one strategy we use in our
experiments is the binary allocation strategy, i.e. give most
precision budget to the useful directions in equal amount, and give
the rest of the budget to the other directions in equal amount. This
strategy follows from the intuition that our prior knowledge only
tells us whether the directions are informative or not, but we do
not know the granularity of the level of usefulness of these directions.



 §.§ Power-to-Noise Ratio (PNR)


However, in other situations when we have more granular knowledge
about the directions, the problem of designing the best strategy can
be more challenging. Here, we propose a method to optimize the utility
with the MVG mechanism and directional noise based on maximizing the
power-to-noise ratio (PNR) <cit.>.
The formulation treats the matrix-valued query function output as
a random variable. Let us denote this matrix-valued random variable
of the query function as 𝒮∈ℝ^m× n.
Then, the output of the MVG mechanism, denoted by 𝒴∈ℝ^m× n,
can be written as 𝒴=𝒮+𝒵, where 𝒵∼ℳ𝒱𝒢_m,n(0,Σ,Ψ).
From this description, the PNR can be defined in statistical sense
based on the covariance of each random variable as (cf. <cit.>),

    PNR=signal+noise/noise=|cov(𝒮)+cov(𝒵)/cov(𝒵)|,

where the cov(·) operator indicates the covariance of the random
variable, and |·| is the matrix determinant. We
note that the determinant operation is necessary here since the covariance
of each random variable is a matrix, but the PNR is generally interpret
as a scalar value. We may use either the trace or determinant operator
for this purpose, but for mathematical simplicity which will be clear
later, we adopt the determinant here.



 §.§ Maximizing PNR under (ϵ,δ)-Differential Privacy Constraint




With the definition of PNR in Eq. (<ref>), we need to
make a connection to the sufficient conditions in Theorem <ref>
and Theorem <ref> to ensure that the MVG mechanism
guarantees (ϵ,δ)-differential privacy. For brevity,
throughout the subsequent discussion and unless otherwise stated,
we assume that we implement the MVG mechanism according to Theorem
<ref>. This presents no limitation to our approach
since the same technique can be readily applied to Theorem <ref>
simply by changing the (ϵ,δ)-differential privacy constraint
based on its sufficient condition.

First, we can utilize the equivalence in Lemma <ref>
and write the noise term as cov(𝒵)=Ψ⊗Σ∈ℝ^mn× mn.
Then, we formulate the constrained optimization problem of maximizing
PNR with (ϵ,δ)-differential privacy constraint as follows.

 Given a matrix-valued query function
with the covariance cov(𝒮)=𝐊_f∈ℝ^mn× mn,
find Σ∈ℝ^m× m and Ψ∈ℝ^n× n
that optimize

    max_Σ,Ψ | K_f+Ψ⊗Σ|/|Ψ⊗Σ|
    s.t. ‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2≤   (-β+√(β^2+8αϵ))^2/4α^2.


This problem is difficult to solve, but the following relaxation allows
the problem to be solved analytically. Hence, we consider the following
relaxed problem.

 Given the matrix-valued
query function with the covariance cov(𝒮)=𝐊_f∈ℝ^mn× mn,
find Σ∈ℝ^m× m and Ψ∈ℝ^n× n
that optimize

    max_Σ,Ψ | K_f+Ψ⊗Σ|/|Ψ⊗Σ|
    s.t. ‖σ(Σ^-1)‖ _1‖σ(Ψ^-1)‖ _1=    (-β+√(β^2+8αϵ))^2/4α^2.


The fact that the relaxation still satisfies the same differential
privacy as Problem <ref> can be readily
verified by the the norm inequality 𝐱_2≤𝐱_1
<cit.>. 

Before we delve into its solution, we first clarify the connection
between this optimization and the precision allocation strategy. Recall
from Section <ref> that the covariances Σ
and Ψ can be decomposed via the SVD into the directions
and variances. The inverses of the variances then correspond to the
singular values σ(Σ^-1) and
σ(Ψ^-1). This, hence, relates
the objective function in Problem <ref>
to its inequality constraint. Recall further that, for a given set
of directions of the noise, the precision allocation strategy θ
indicates the importance of each direction. More precisely, high value
of θ(i) for the i^th direction means that the variance
of the noise in that direction would be small, i.e. large σ_i(Σ^-1)
or σ_i(Ψ^-1). In other words, for a given
set of noise directions, the design of θ is equivalently
done via the design of σ(Σ^-1)
and σ(Ψ^-1). Since the optimization
in Problem <ref> or Problem <ref>
directly concerns with the design of σ(Σ^-1)
and σ(Ψ^-1), this completes
the connection between the optimization in Problem <ref>
or Problem <ref> and the design
of the precision allocation strategy θ.

Next, we seek for a solution to the optimization in Problem <ref>
in order to guide us to the optimal design of the precision allocation
strategy. The following theorem summarizes the solution.

 Consider the optimization in Problem <ref>.
Let the SVD of K_f be given by K_f= QΛ_f Q^T∈ℝ^mn× mn,
and let Λ_𝒵∈ℝ^mn× mn
be a a diagonal matrix whose diagonal entries are positive and are
given by, 

    [Λ_𝒵]_ii^-1=c-[Λ_f]_ii^-1,

where [·]_ii indicates the [i^th,i^th]-element of
the matrix, and the scalar c is given by

    c=(-β+√(β^2+8αϵ))^2+4α^2tr(Λ_f^-1)/4mnα^2.

Then, the solution to the optimization in Problem <ref>
is given by,

    Ψ⊗Σ= Q^TΛ_𝒵 Q.



We observe that the optimization in Problem <ref>
is in the form close to the water filling problem in communication
systems design <cit.>. Hence, the goal is
to modify our optimization problem into the form solvable by the water
filling algorithm. We seek to find the optimal solution to the following
optimization problem. 

    max_‖σ(Σ^-1)‖ _1‖σ(Ψ^-1)‖ _1=d| K_f+Ψ⊗Σ|/|Ψ⊗Σ|,

where d=(-β+√(β^2+8αϵ))^2/4α^2.
By using multiplicative property of the determinant and the SVD of
K_f= QΛ_f Q^T we have that, 

    | K_f+Ψ⊗Σ|/|Ψ⊗Σ|    =| K_f+Ψ⊗Σ|/|Ψ⊗Σ|
        =| K_f(Ψ⊗Σ)^-1+ I|
        =| K_f||(Ψ⊗Σ)^-1+ K_f^-1|
        =| K_f||(Ψ⊗Σ)^-1+ Q^TΛ_f^-1 Q|
        =| K_f|| Q^T|| Q(Ψ⊗Σ)^-1 Q^T+ Q^TΛ_f^-1|| Q|
        =| K_f|| Q(Ψ⊗Σ)^-1 Q^T+Λ_f^-1|.


Therefore, find the optimizer of Problem <ref>
is equivalent to finding the optimizer of 

    max_‖σ(Ψ^-1)‖ _1‖σ(Σ^-1)‖ _1=d| Q(Ψ⊗Σ)^-1 Q^T+Λ_f^-1|
    (a)=   max_Σ,Ψ: tr(Ψ^-1⊗Σ^-1)=d| Q(Ψ⊗Σ)^-1 Q^T+Λ_f^-1|
    (b)=   max_ tr( Q(Ψ⊗Σ)^-1 Q^T)=d| Q(Ψ⊗Σ)^-1 Q^T+Λ_f^-1|
    (c)=   max_Λ_𝒵: tr(Λ_𝒵^-1)=d|Λ_𝒵^-1+Λ_f^-1|
    (d)≤   max_Λ_𝒵: tr(Λ_𝒵^-1)=d∏_i=1^mn([Λ_𝒵]_ii^-1+[Λ_f]_ii^-1),

where (in)-equalities follow from the following properties.




  * Step (a) uses the property of the Kronecker product that tr(Ψ^-1⊗Σ^-1)= tr(Ψ^-1)· tr(Σ^-1)
<cit.>, and then uses the property of the trace that
tr(Σ^-1)=‖σ(Σ^-1)‖ _1
and tr(Ψ^-1)=‖σ(Ψ^-1)‖ _1
since Σ and Ψ are positive
definite <cit.>, <cit.>.


  * Step (b) follows from the identity of the Kronecker product
that (Ψ^-1⊗Σ^-1)=(Ψ⊗Σ)^-1
<cit.>, and the unitary invariance property
of the trace, i.e. tr(𝐀)=tr(𝐀𝐐^T𝐐)=tr(𝐐𝐀𝐐^T)
since Q^T Q= I. 


  * Step (c) follows from the unitary transformation Q(Ψ⊗Σ)^-1 Q^T=𝐐(𝐐^TΛ_𝒵𝐐)^-1𝐐^T=𝐐(𝐐^TΛ_𝒵^-1𝐐)𝐐^T=Λ_𝒵^-1. 


  * Finally, step (d) uses the Hadamard's inequality (Lemma <ref>),
which holds with equality if and only if Λ_𝒵^-1
is a diagonal matrix <cit.>.



The solution to the problem in Eq. (<ref>) is given
by the water filling solution <cit.> to be,

    [Λ_𝒵]_ii^-1=(c-[Λ_f]_ii^-1)^+,

where c is chosen such that 

    ∑_i=1^mn(c-[Λ_f]_ii^-1)^+=d.

Then, we can solve for c by some elementary algebraic modifications
as

    c=d+∑_i=1^mn[Λ_f]_ii^-1/mn=d+tr(Λ_f^-1)/mn.

Substitute in the definition of d and this concludes the proof.

The solution in Theorem <ref> has a very intuitive
interpretation. Consider first the decomposition of the solution Ψ⊗Σ= Q^TΛ_𝒵 Q.
This is a decomposition of the total covariance of the noise cov(𝒵)
into its directions specified by 𝐐 and the corresponding
variances specified by Λ_𝒵. Noticeably,
the directions 𝐐 are directly taken from the SVD of the
covariance of the query function, i.e. K_f= QΛ_f Q^T,
and the directional variances Λ_𝒵
are a function of Λ_f. This matches our intuition
in Section <ref> –
given the SVD of the query function, we know which directions of the
matrix-valued query function are more informative than the others,
so we should design the directional noise of the MVG mechanism to
minimize its impact on the informative directions.

In more detail, the solution in Theorem <ref> suggests
the following procedure for designing the MVG mechanism with directional
noise to maximize the utility.


  * Pick the noise directions from the SVD of the matrix-valued query
function.

  * To determine the noise variance for each direction, consider the singular
values of the matrix-valued query function as follows.


  * Suppose for the direction 𝐪_i, the singular value of
the query function – which indicates how informative that
direction is – is σ_i(𝐊_f). Then,
we design the noise variance in that direction, σ_i(𝒵)
to be proportional to the inverse of the singular value of the query
function, i.e. σ_i(𝒵)∝σ_i^-1(𝐊_f).

  * Furthermore, since the overall noise variance is constrained by the
(ϵ,δ)-differential privacy condition, we design the
scalar c to ensure that Λ_𝒵 satisfies
the constraint.

  * Finally, the proportional σ_i(𝒵)∝σ_i^-1(𝐊_f)
is achieved by Eq. (<ref>).


  * Compose the overall covariance of the noise via Eq. (<ref>).




§ EXPERIMENTAL SETUPS






We evaluate the proposed MVG mechanism on three experimental setups
and datasets. Table <ref> summarizes our setups. In
all experiments, 100 trials are carried out and the average and 95%
confidence interval are reported. These experimental setups are discussed
in detail here.



 §.§ Experiment I: Regression




  §.§.§ Task and Dataset


The first experiment considers the regression application on the Liver
Disorders dataset <cit.>. The dataset derives
5 features from the blood sample of 345 patients. We leave out the
samples from 97 patients for testing, so the private dataset contains
248 patients. We follow the suggestion of Forsyth and Rada <cit.>
by using these features to predict the average daily alcohol consumption
of the patients. All features and the teacher values are centered-adjusted
and are ∈[-1,1].



  §.§.§ Query Function and Evaluation Metric


We perform the regression task in a differentially-private manner
via the identity query, i.e. f(𝐗)=𝐗. Since regression
involves the teacher values, we treat them as a feature, so the query
size becomes 6×248. We use the kernel ridge regression (KRR)
<cit.> as the regressor, and the root-mean-square
error (RMSE) <cit.> as the evaluation metric.



  §.§.§ MVG Mechanism Design


As discussed in Section <ref>,
Algorithm <ref> is appropriate for the identity
query, so we employ it for this experiment. The L_2-sensitivity
of this query can be derived as follows. The query function is f(𝐗)=𝐗∈[-1,1]^6×248.
For neighboring datasets {𝐗,𝐗'}, the L_2-sensitivity
is 

    s_2(f)=sup_𝐗,𝐗'‖𝐗-𝐗'‖ _F=sup_𝐗,𝐗'√(∑_i=1^6(x(i)-x'(i))^2)=2√(6).

To design the noise directions, we employ two methods as follows.



  
Via Domain Knowledge with Binary Allocation Strategy

For this method, to identify the informative directions to allocate
the precision budget, we refer to the domain knowledge by Alatalo
et al. <cit.>, which indicates that alanine aminotransferase
(ALT) is the most indicative feature for predicting the alcohol consumption
behavior. Additionally, from our prior experience working with regression
problems, we recognize that the teacher value (Y) is another important
feature to allocate more precision budget to. With this setup, we
use the standard basis vectors as the directions (cf. Section <ref>)
and employ the following binary allocation strategy.


  * Allocate τ% of the precision budget to the two important features
(ALT and Y) by equal amount. 

  * Allocate the rest of the precision budget equally to the rest of the
features. 

We vary τ∈{55,65,…,95} and report the best results[Note that, in the real-world deployment, this parameter selection
process should also be made private, as suggested by Chaudhuri and
Vinterbo <cit.>.]. The rationale for this strategy is from the intuition that our prior
knowledge only tells us whether the directions are highly informative
or not, but we do not know the granularity of the level of
usefulness of these directions. Hence, this strategy give most precision
budget to the useful directions in equal amount, and give the rest
of the budget to the other directions in equal amount.



  
Via Differentially-Private SVD with Max-PNR Allocation Strategy



To illustrate the feasibility of the directional noise when prior
knowledge may not be available, we design another implementation of
the MVG mechanism with directional noise according to the method described
in Section <ref>. This method derives the
directions from the SVD of the query function. However, since the
SVD itself can leak sensitive information about the dataset, the algorithm
for SVD also needs to be differentially-private. This means that we
need to allocate some privacy budget into this process. In this experiment,
we employ the differentially-private SVD algorithm in <cit.>,
and allocate 20% of the total ϵ and δ privacy budget
to it. We pick this fraction based on an observation on our results
from other experiments, which show that the MVG mechanism can yield
good performance even when we pick the wrong informative directions
(cf. Section <ref>). Hence, it is advantageous
to allocate more budget to the MVG mechanism than to the noise direction
derivation.

In addition, to illustrate the full capability of the MVG mechanism,
we employ the optimal precision allocation strategy presented in Section
<ref>. However, since we consider the unimodal
directional noise, we only need to design Σ since
we set Ψ=𝐈. Consequently, the term Ψ⊗Σ
in Theorem <ref> can be replaced by simply Σ,
and we can estimate 𝐊_f=𝐗𝐗^T∈ℝ^6×6,
which is the covariance among the features. This takes into account
the fact that the covariance among the samples are not considered
in the unimodal directional noise for this task (cf. Section <ref>).



 §.§ Experiment II: 1^st Principal Component (1^st P.C.)




  §.§.§ Task and Dataset


The second experiment considers the problem of determining the first
principal component (1^st P.C.) from the principal component
analysis (PCA). This is one of the most popular problem both in machine
learning and differential privacy. Note that we only consider the
first principal component here for two reasons. First, many prior
works in differentially-private PCA algorithm consider this problem
or the similar problem of deriving a few major P.C. (cf. <cit.>),
so this allows us to compare our approach to the state-of-the-art
approaches of a well-studied problem. Second, in practice, this method
for deriving the 1^st P.C. can be used iteratively along with
an orthogonal projection method to derive the rest of the principal
components (cf. <cit.>)[The iterative algorithm as a whole has to be differentially-private
as well, so this can be an interesting topic for future research.].

We use the Movement Prediction via RSS (Movement) dataset <cit.>,
which consists of the radio signal strength measurement from 4 sensor
anchors (ANC{0-3}) – corresponding to the 4 features
– from 10,176 movement samples. The features are center-adjusted
and are ∈[-100,100].



  §.§.§ Query Function and Evaluation Metric


We consider the setting presented in Example <ref>, so
the query is f(𝐗)=1/n𝐗𝐗^T.
Then, we use SVD to derive the 1^st P.C. from it. Hence, the
query size is 4×4.

We adopt the common quality metric traditionally used for P.C. <cit.>
and also used by Dwork et al. <cit.> – the
captured variance ρ. For a given P.C. 𝐯,
the capture variance by 𝐯 on the covariance matrix 𝐒̅
is defined as ρ=𝐯^T𝐒̅𝐯. To
be consistent with other experiments, we use the absolute error in
ρ as deviated from the maximum ρ for a given 𝐒̅.
It is well-established that the maximum ρ is equal to the largest
eigenvalue of 𝐒̅ (cf. <cit.>,
<cit.>). Hence, this metric can be written concisely
as, 

    Δρ(𝐯)=λ_1-ρ(𝐯),

where λ_1 is the largest eigenvalue of 𝐒̅.
For the ideal, non-private case, the error would clearly be zero.



  §.§.§ MVG Mechanism Design


As discussed in Section <ref>,
Algorithm <ref> is appropriate for the covariance
query, so we employ it for this experiment. The L_2-sensitivity
of this query is derived as follows. The query function is f(𝐗)=1/n𝐗𝐗^T,
where 𝐗∈[-100,100]^4×2021. For neighboring datasets
{𝐗,𝐗'}, the L_2-sensitivity is 

    s_2(f)=sup_𝐗,𝐗'‖𝐱_j𝐱_j^T-𝐱_j'𝐱_j'^T‖ _F/10,176=2√(∑_j=1^4^2x_j(i)^4)/10,176=8·10^4/10,176.

To identify the informative directions to allocate the precision budget,
we inspect the data collection setup described by Bacciu et al. <cit.>,
and hypothesize that that two of the four anchors should be more informative
due to their proximity to the movement path (ANC0 & ANC3). Hence,
we use the standard basis vectors as the directions (cf. Section <ref>)
and allocate more precision budget to these two features using the
same strategy as in Exp. I.

Since this query function is positive semi-definite, we can use either
Theorem <ref> or Theorem <ref>
to guarantee the same (ϵ,δ)-differential privacy. Therefore,
to illustrate the improvement achievable via the exploitation of the
structural characteristic of the matrix-valued query function, we
implement the MVG mechanism with both theorems.



 §.§ Experiment III: Covariance Estimation




  §.§.§ Task and Dataset


The third experiment considers the similar problem to Exp. II but
with a different flavor. In this experiment, we consider the task
of estimating the covariance matrix from the perturbed database.
This differs from Exp. II in three major ways. First, for covariance
estimation, we are interested in every P.C., rather than just the
first one. Second, as mentioned in Exp. II, many previous works do
not consider every P.C. in their design, so the previous works for
comparison are different. Third, to give a different taste of our
approach, we consider the method of input perturbation for estimating
the covariance, i.e. we query the database itself and use it to compute
the covariance.

We use the Cardiotocography (CTG) dataset <cit.>,
which consists of 21 features from 2,126 fetal samples. All features
have the range of [0,1].



  §.§.§ Query Function and Evaluation Metric


We consider covariance estimation via input perturbation, so we use
the identity query, i.e. f(𝐗)=𝐗. The query size
is 21×2126.

We adopt the captured variance as the quality metric similar to Exp.
II, but since we are interested in every P.C., we consider the residual
sum of square (RSS) <cit.> of every P.C. This is similar
to the total residual variance used by Dwork et al. <cit.>.
Formally, given the perturbed database 𝐗̃, the
covariance estimate is 𝐒̃=1/n𝐗̃𝐗̃^T.
Let {𝐯̃_i} be the set of P.C.'s derived from
𝐒̃, and the RSS is, 

    RSS(𝐒̃)=∑_i(λ_i-ρ(𝐯̃_i))^2,

where λ_i is the i^th eigenvalue of 𝐒̅
(cf. Exp. II), and ρ(𝐯̃_i) is the captured
variance of the i^th P.C. derived from 𝐒̃.
Clearly, in the non-private case, RSS(𝐒̅)=0.



  §.§.§ MVG Mechanism Design


Since we consider the identity query, we employ Algorithm <ref>
for this experiment. The query function is the same as Exp. I, so
the L_2-sensitivity can be readily derived as s_2(f)=sup_𝐗,𝐗'√(∑_i=1^21(x(i)-x'(i))^2)=√(21).
To identify the informative directions to allocate the precision budget
to, we refer to the domain knowledge from Costa Santos et al. <cit.>,
which identifies three features to be most informative, i.e. fetal
heart rate (FHR), %time with abnormal short term variability (ASV),
and %time with abnormal long term variability (ALV). Hence, we use
the standard basis vectors as the directions and allocate more precision
budget to these three features using the similar strategy to that
in Exp. I.



 §.§ Comparison to Previous Works


Since our approach falls into the category of basic mechanism, we
compare our work to four prior state-of-the-art basic mechanisms discussed
in Section <ref>, namely, the Laplace mechanism,
the Gaussian mechanism, the Exponential mechanism, and the JL transform
method.

For Exp. I and III, since we consider the identity query, the four
previous works for comparison are the works by Dwork et al. <cit.>,
Dwork et al. <cit.>, Blum et al. <cit.>,
and Upadhyay <cit.>, for the four basic mechanisms respectively.

For Exp. II, we consider the 1^st P.C. As this problem has been
well-investigated, we compare our approach to the state-of-the-art
algorithms specially designed for this problem. These algorithms using
the four prior basic mechanisms are, respectively: Dwork et al. <cit.>,
Dwork et al. <cit.>, Chaudhuri et al. <cit.>,
and Blocki et al. <cit.>.

For all previous works, we use the parameter values as suggested by
the authors of the method, and vary the free variable before reporting
the best performance.

Finally, we recognize that some of these prior works have a different
privacy guarantee from ours, namely, ϵ-differential privacy.
Nevertheless, we present these prior works for comprehensive coverage
of prior basic mechanisms, and we will keep this difference in mind
when discussing the results.



§ EXPERIMENTAL RESULTS 






 §.§ Experiment I: Regression


Table <ref> reports the results for Exp. I. Here
are the key observations. 


  * Compared to the non-private baseline, the MVG mechanisms using both
precision allocation strategies yield similar performance (difference
of .004 in RMSE). 

  * Compared to other (ϵ,δ)-basic mechanisms, i.e. Gaussian
and JL transform, the MVG mechanism provides better utility with the
same privacy guarantee (by .003 and .0006 in RMSE, respectively). 

  * Compared to other ϵ-basic mechanisms, i.e. Laplace and Exponential,
the MVG mechanism provides significantly better utility (up
to ~150%) with slightly weaker (ϵ,1/n)-differential
privacy guarantee. 

  * Among the compared methods, the MVG mechanism using the directional
noise derived from SVD and the max-PNR allocation strategy has the
best performance.

Overall, the results from regression show the promise of the MVG mechanism.
Our approach can outperform all other (ϵ,δ)-basic mechanisms.
Although it provides a weaker privacy guarantee than other ϵ-basic
mechanisms, it can provide considerably more utility (up to ~150%).
As advocated by Duchi et al. <cit.> and Fienberg et
al. <cit.>, this trade-off could be attractive in some
settings, e.g. critical medical situation. In addition, it shows that,
even when domain knowledge is not available to design the noise directions,
the process in Section <ref>, which uses differentially-private
SVD and the PNR maximization based on Section <ref>,
can provide an even better – and, in fact, the best –
performance.



 §.§ Experiment II: 1^st Principal Component




Table <ref> reports the results for Exp. II. Here
are the key observations. 


  * Compared to the non-private baseline, the MVG mechanism has very small
error Δρ as low as 0.1434, which is achieved when the
PSD structure of the query function is exploited by the mechanism
via Theorem <ref>. 

  * Compared to other (ϵ,δ)-basic mechanisms, i.e. the
Gaussian mechanism and the JL transform, the best MVG mechanism, which
exploits the PSD structure of the query via Theorem <ref>,
provides significantly better utility (error of 0.1434 vs 0.2290/0.2258)
with the same privacy guarantee. 

  * Compared to other ϵ-basic mechanisms, i.e. the Laplace and
Exponential mechanisms, the best MVG mechanism, which exploits the
PSD structure of the query via Theorem <ref>, also
yields higher utility (error of 0.1434 vs 0.2432/0.1742) with a slightly
weaker (ϵ,1/n)-differential privacy guarantee.

  * Comparing the two MVG mechanism designs, the one with utilizes the
structural characteristic of the query function with Theorem <ref>
performs notably better (error of 0.1434 vs 0.2138) over its counterpart
which uses Theorem <ref>.

Overall, the MVG mechanism which exploits the PSD structure of the
query via Theorem <ref> provides the best utility
among competing methods. Noticeably, without the utilization of the
PSD structure of the query function, the MVG mechanism which uses
Theorem <ref> actually performs worse than the
state-of-the-art method by Chaudhuri et al. <cit.>.
Though, it can be said that the method by Chaudhuri et al. <cit.>
also utilizes the PSD property of the query function since the algorithm
is designed specifically for deriving the 1^st P.C. This reinforces
the notion that exploiting the structural characteristics of the matrix-valued
query function can provide utility improvement. 



 §.§ Experiment III: Covariance Estimation




Table <ref> reports the results for Exp. III. Here
are the key observations. 


  * Compared to the non-private baseline, the MVG mechanism has very small
RSS error of .06657. 

  * Compared to other (ϵ,δ)-basic mechanisms, i.e. Gaussian
and JL transform, the MVG mechanism provides better utility with the
same privacy guarantee (.004 and .001 smaller RSS error, respectively). 

  * Compared to other ϵ-basic mechanisms, i.e. Laplace and Exponential,
the MVG mechanism gives better utility with slightly weaker (ϵ,1/n)-differential
privacy guarantee (.005 and .006 smaller RSS error, respectively). 

Overall, the MVG mechanism provides the best utility (smallest error).
When compared to other methods with stronger privacy guarantee, the
MVG mechanism can provide much higher utility. Again, we point out
that in some settings, the trade-off of weaker privacy for better
utility might be favorable <cit.>, and
our approach provides the best trade-off.





§ DISCUSSION AND FUTURE WORKS




 §.§ Effect of Noise Directions on the Utility




In Section <ref>, we discuss how
the choice of noise directions can affect the utility. Here, we investigate
this effect on the obtained utility in the three experiments. Figure
<ref> depicts our results, and we discuss
our key observations here.

Figure <ref>, Left, shows the direction
comparison from Exp. I with the directions derived from the domain
knowledge <cit.>. We compare four choices of directions.
Direction (a), which uses the domain knowledge (ALT) and the teacher
label (Y), yields the best result when compared to: (b) using only
the domain knowledge (ALT), (c) using only the teacher label (Y),
and (d) using an arbitrary extra feature (ALT+Y+AST). In addition,
it is noticeable that the MVG mechanism still generally provides good
utility despite the less optimal directions being chosen.

Figure <ref>, Middle, shows the direction
comparison from Exp. II using the MVG mechanism with Theorem <ref>.
We compare four choices of directions. Direction (a), which makes
full use of the prior information (ANC0 and ANC3), performs best when
compared to: (b), (c) using only partial prior information (ANC0 or
ANC3), and (d) having the wrong priors completely (ANC1 and ANC2).

Figure <ref>, Right, shows the comparison
from Exp. III. We compare three choices of directions. Direction (a),
which uses the domain knowledge (FHR, ASV, ALV3), gives the best performance
compared to: (d) using the completely wrong priors (all other features),
and (c) having no prior at all (i.i.d.).

Overall, these observations confirm the merit of both using directional
noise for the utility gain, and using prior information to properly
select the noise directions. However, we emphasize that, when prior
information is not available, we can still exploit the notion of directional
noise as shown in Section <ref>.



 §.§ Directional Noise as a Generalized Subspace Analysis


Directional noise provides utility gain by adding less noise in useful
directions and more in other directions. This has a connection to
subspace projection or dimensionality reduction, in which the non-useful
directions are simply removed. Clearly, the main difference between
the two is that, in directional noise, the non-useful directions are
kept, although are highly perturbed. However, despite being highly
perturbed, these directions may still be able to contribute to the
utility performance. With dimensionality reduction, which discards
them completely, we forfeit that additional information.

We test this hypothesis by running two additional regression experiments
(Exp. I) as follows. Given the same two important features used for
the MVG mechanism (ALT & Y), we use the Gaussian mechanism <cit.>
and the JL transform method <cit.> to perform the regression
task using only these two features (i.e. discarding the rest of the
features). With ϵ=1 and δ=1/n, the results
are (2.538±.065)×10^-2 and (2.863±.022)×10^-2
of RMSE, respectively. Noticeably, these results are significantly
worse (i.e. larger error) than that of the MVG mechanism ((1.624±.026)×10^-2
or (1.611±.046)×10^-2), with the same privacy guarantee.
Specifically, by incorporating all features with directional noise
via the MVG mechanism, we can achieve over 150% gain in utility over
the dimensionality reduction alternatives.



 §.§ Information Theoretic Perspective on the MVG Mechanism


In this work, we analyze the MVG mechanism primarily from the perspectives
of differential privacy and signal processing. However, as discussed
by Cuff and Yu <cit.>, there is a strong connection
between differential privacy and information theory. Therefore, in
this section, we discuss several advantageous properties of the MVG
mechanism from the perspective of information theory. First, we introduce
the necessary definitions, concepts, lemmas, and theorems. Second,
we discuss how maximizing PNR in Section <ref>
is equivalent to maximizing the mutual information between the MVG
mechanism output and the true query answer. Third, we derive the optimal
type of query function to be used with the MVG mechanism. Finally,
we show that, under a certain condition, not only does the MVG mechanism
preserves (ϵ,δ)-differential privacy, but it also guarantees
the minimum correlation between the dataset and the output of the
mechanism.



  §.§.§ Background Concepts


From the perspective of information theory, we view both the query
answer f(𝒳) and the mechanism output ℳ𝒱𝒢(f(𝒳))
as two random variables. One of the key measurements in information
theory concerns the mutual information, defined as follows.

 Let 𝒳 and 𝒴 be two matrix-valued random
variables with joint probability density given by p_𝒳,𝒴(𝒳,𝒴).
Then, the mutual information between 𝒳 and 𝒴
is defined as 

    I(𝒳;𝒴)=𝔼[logp_𝒳,𝒴(𝒳,𝒴)/p_𝒳(𝒳)p_𝒴(𝒴)].


The mutual information I(𝒳;𝒴) is a non-negative
quantity that measures the dependency between the two random variables
(cf. <cit.>). In relation to our analysis, it is important
to discuss a property of the mutual information with respect to entropy.
To the best of our knowledge, the notion of entropy for a matrix-valued
random variable has not been substantially studied. Therefore, we
define the terms here, and note that this topic in itself might be
of interest for future research in information theory and matrix analysis. 

Given a matrix-valued random variable 𝒳 with the pdf
p_𝒳(𝒳), the differential entropy is

    h(𝒳)=𝔼[-log p_𝒳(𝒳)].

For a joint pdf p_𝒳,𝒴(𝒳,𝒴),
the conditional entropy is 

    h(𝒳|𝒴)=𝔼[-log p_𝒳|𝒴(𝒳|𝒴)].

For two pdfs p_𝒳(𝒳) and p_𝒴(𝒴),
the relative entropy is 

    D(p_𝒳∥ p_𝒴)=𝔼[logp_𝒳(𝒳)/p_𝒴(𝒴)].


Using the definitions of entropy, the mutual information can be written
as 

    I(𝒳;𝒴)=h(𝒴)-h(𝒴|𝒳).

Next, let us define 

    Cov(vec(𝒳))=𝔼[[vec(𝒳)-𝔼[vec(𝒳)]][vec(𝒳)-𝔼[vec(𝒳)]]^T],

and let ≼ be the Loewner partial order defined as follows
<cit.>.

Given 𝐀,𝐁∈ℝ^n× n, we write
𝐀≼𝐁 if 𝐀 and 𝐁
are symmetric and 𝐁-𝐀 is positive semi-definite.

Then, we present the following two lemmas. 

Given a matrix-valued random variable
𝒳∈ℝ^m× n with Cov(vec(𝒳))≼𝐊,
the entropy of 𝒳 has the property 

    h(𝒳)≤1/2log[(2π e)^mn|𝐊|],

with equality if and only if 𝒳∼ℳ𝒱𝒢_m,n(𝐌,Σ,Ψ)
with Ψ⊗Σ=𝐊. 


The proof parallels the proof in <cit.>, where we use
the property that D(f_𝒜g_𝒳) is non-negative.
Let g_𝒳 be the pdf of MVG random variable such that
Cov(vec(𝒳))=Cov(vec(𝒜)). We observe that 

    0≤ D(fg)     =𝔼[logf_𝒜(𝒜)/g_𝒳(𝒜)]=-h(𝒜)-𝔼[log g_𝒳(𝒜)].

Next, we show that 𝔼[log g_𝒳(𝒳)]=𝔼[log g_𝒳(𝒜)]
as follows. 

    𝔼[log g_𝒳(𝒜)]     =-1/2𝔼[tr[Σ^-1(𝒜-𝐌)^TΨ^-1(𝒜-𝐌)]]+log((2π)^mn/2|Σ|^m/2|Ψ|^n/2)
        =-1/2𝔼[(vec(𝒜)-vec(𝐌))^T(Ψ⊗Σ)(vec(𝒜)-vec(𝐌))]+log((2π)^mn/2|Ψ⊗Σ|)
        =-1/2Cov(vec(𝒳))+log((2π)^mn/2|Ψ⊗Σ|)=𝔼[log g_𝒳(𝒳)].

Using the equality 𝔼[log g_𝒳(𝒳)]=𝔼[log g_𝒳(𝒜)],
we have h(𝒜)≤-𝔼[log g_𝒳(𝒜)]=h(𝒳),
which concludes the proof. 



 Given two matrix-valued random
variables 𝒳∈ℝ^m× n and 𝒴∈ℝ^p× q
with Cov(vec(𝒳)|𝒴)=𝐊, the conditional
entropy of 𝒳 upon 𝒴 has the property 

    h(𝒳|𝒴)≤1/2log[(2π e)^mn|𝐊|],

with equality if and only if (𝒳,𝒴) is jointly
MVG with Cov(vec(𝒳)|𝒴)=𝐊. 


The proof follows that of Lemma <ref> by
working with the conditional probability version. 




  §.§.§ Maximizing PNR is Maximizing Mutual Information


Recall from Section <ref> that we optimize
utility of the MVG mechanism using the PNR criterion. In this section,
we present how maximizing PNR is equivalent to maximizing the mutual
information between the MVG mechanism output and the true query answer.

Here, we can consider the true query answer f(𝒳), and
the mechanism output ℳ𝒱𝒢(f(𝒳)) as two random
variables. Then, we use the mutual information I(f(𝒳);ℳ𝒱𝒢(f(𝒳)))
to measure how informative the MVG mechanism output is, with respect
to the true answer. More importantly, we can optimize this measure
over the design flexibility of the MVG mechanism as follows: 

    𝒵max I(f(𝒳);f(𝒳)+𝒵)
    s.t.  𝒵∼ℳ𝒱𝒢(0,Σ,Ψ), 𝒵∈ℙ,

where ℙ is the set of all possible random variables 𝒵
that satisfy (ϵ,δ)-differential privacy according to
Theorem <ref>, i.e. the conceptual shaded area
in Figure <ref>. If f(𝒳) is
Gaussian, the optimization can be simplified as follows. 

The optimization in Problem <ref>
is equivalent to 

    Σ,Ψmax |Ψ_f⊗Σ_f+Ψ⊗Σ|/|Ψ⊗Σ|
    s.t.  ‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2≤   (-β+√(β^2+8αϵ))^2/4α^2,

where |·| is the matrix determinant; β, α,
and ϵ are defined in Theorem <ref>;
and f(𝒳)∼ℳ𝒱𝒢(0,Σ_f,Ψ_f). 


Because f(𝒳) and 𝒵 are Gaussian, their mutual
information can be explicitly evaluated. With the relationship in
between the mutual information and entropy in Eq. (<ref>)
and Lemma <ref>, the optimization in Eq.
(<ref>) becomes, 

    Σ,Ψmax1/2log(|Ψ_f⊗Σ_f+Ψ⊗Σ|/|Ψ⊗Σ|)
    s.t. ‖σ(Σ^-1)‖ _2‖σ(Ψ^-1)‖ _2≤   (-β+√(β^2+8ϵ))^2/4α^2.

By using the monotonicity property of the log function, this concludes
the proof. 

Noticeably, comparing Lemma <ref> to Problem
<ref>, if we replace Ψ_f⊗Σ_f
with 𝐊_f, we readily see that the two optimizations
are equivalent. In other words, maximizing PNR of the MVG mechanism
output is equivalent to maximizing the mutual information between
the MVG mechanism output and the true query answer.



  §.§.§ Optimal Query Function for the MVG Mechanism


With an alternative view on the formulation of mutual information
in Eq. (<ref>), we can also study what type
of query function would yield the maximum mutual information between
the MVG mechanism output and the true query answer. Here, we prove
that such query functions have the form f(𝐗)=∑_ig_i(𝐱_i),
where 𝐱_i is the i^th column (sample) of 𝐗.

 The mutual information between the true query
answer f(𝒳) and the query answer via the MVG mechanism
ℳ𝒱𝒢(f(𝒳)) is maximum when the query function
has the form f(𝐗)=∑_ig_i(𝐱_i), where
𝐱_i is the i^th column (sample) in 𝐗. 


For clarity, let 𝒴=ℳ𝒱𝒢(f(𝒳))=f(𝒳)+𝒵.
For any query function with Cov(vec(f(𝒳))≼𝐊,
write the mutual information in terms of the entropy, 

    max_fI(f(𝐗);𝒴)=max_fh(𝒴)-h(𝒵).

From Lemma <ref>, the maximum is reached
when both 𝒴 and 𝒵 are Gaussian. Since 𝒵∼ℳ𝒱𝒢_m,n(0,Σ,Ψ),
𝒴 is Gaussian when f(𝐗) is Gaussian. Then,
with the multivariate central limit theorem <cit.>,
and a mild condition on g_i(·), e.g. g_i(·) is bounded,
we arrive at the latter condition f(𝐗)=∑_ig_i(𝐱_i). 

Theorem <ref> states that to obtain the highest amount
of information on the true query answer from the MVG mechanism, the
query function should be in the form f(𝐗)=∑_ig_i(𝐱_i).
Conceptually, this condition states that the query function can be
decomposed into functions of individual records in the dataset. We
note that this can cover a wide range of real-world query functions.
Several statistical queries can be formulated in this form including
the average, covariance, and correlation. In machine learning, the
kernel classifiers and the loss functions can often be formulated
in this form <cit.>.



  §.§.§ Proof of Minimum Privacy Leakage


Apart from considering the mutual information between the MVG mechanism
output and the true query answer as in Eq. (<ref>),
we can alternatively consider the mutual information between the MVG
mechanism output and the dataset itself. This can be thought
of as the correlation between the dataset and the output of the MVG
mechanism. From the privacy point of view, clearly, we want this correlation
to be minimum. Here, we show that, if the query function has the form
f(𝐗)=∑ g_i(𝐱_i), the MVG mechanism also
guarantees the minimum correlation between the dataset and the output
of the mechanism.

First, we treat the dataset 𝒳 as a random variable. Then,
the claim is readily proved by the following theorem.

If the matrix-valued query function is of
the form f(𝐗)=∑ g_i(𝐱_i), then for an
arbitrary positive definite matrix 𝐊, 

    min_𝒵:Cov(vec(𝒵))=𝐊I(𝒳;f(𝒳)+𝒵)=I(𝒳;f(𝒳)+𝒵_ℳ𝒱𝒢),

where 𝒵_ℳ𝒱𝒢∼ℳ𝒱𝒢_m,n(0,Σ,Ψ)
such that Ψ⊗Σ=𝐊. 


First, we use the multivariate central limit theorem <cit.>
to claim that f(𝒳) is Gaussian. Then, using the decomposition
in Eq. (<ref>), we have that 

    I(𝒳;f(𝒳)+𝒵)     =h(f(𝒳)+𝒵)-h(f(𝒳)+𝒵|𝒳)
        =h(f(𝒳)+𝒵)-h(f(𝒳)+𝒵|f(𝒳))
        =I(f(𝒳);f(𝒳)+𝒵)
        =h(f(𝒳))-h(f(𝒳)|f(𝒳)+𝒵),

where the second line follows from the independence of f(𝒳)
and 𝒵, and from the fact that by conditioning on 𝒳,
we have h(f(𝒳)+𝒵|𝒳)=h(𝒵).
Therefore, we have 

    min_𝒵:Cov(vec(𝒵))=𝐊I(𝒳;f(𝒳)+𝒵)     =h(f(𝒳))-max_𝒵:Cov(vec(𝒵))=𝐊h(f(𝒳)|f(𝒳)+𝒵)
        =h(f(𝒳))-h(f(𝒳)|f(𝒳)+𝒵_ℳ𝒱𝒢),

where the last step follows from Lemma <ref>.

Combining result of Theorem <ref> and Theorem
<ref>, we have a remarkable observation that not
only does the MVG mechanism guarantees (ϵ,δ)-differential
privacy but it also guarantees the minimum possible correlation (in
terms of mutual information) between the database and the output of
the mechanism. Finally, we note that the result of Theorem (<ref>)
is very general as it does not assume anything about the distribution
of the dataset 𝒳 at all.



§ CONCLUSION


In this work, we study the matrix-valued query function in differential
privacy. We present the MVG mechanism that can fully exploit the structural
nature of the matrix-valued analysis. We present two sufficient conditions
for the MVG mechanism to guarantee (ϵ,δ)-differential
privacy – one for the general matrix-valued query function,
and another for the positive semi-definite query function. As a result
of the sufficient conditions, we introduce the novel concept of directional
noise, which can be used to reduce the impact of the noise on the
utility of the query answer. Furthermore, we show how design the directional
noise such that the power-to-noise ratio (PNR) of the MVG mechanism
output is maximum. Finally, we evaluate our approach experimentally
for three matrix-valued query functions on three privacy-sensitive
datasets. The results show that our approach can provide significant
utility improvement over existing methods, and yield the utility performance
close to that of the non-private baseline while preserving (1.0,1/n)-differential
privacy. We hope that our work may inspire further development in
the problem of differential privacy under matrix-valued query functions.

IEEEtran


