# shape_and_structure_preserving_differential_privacy__0f7a65ce.pdf

Shape And Structure Preserving Differential Privacy

Carlos Soto Department of Statistics Pennsylvania State University University Park, PA cjs7363@psu.edu

Karthik Bharath School of Mathematical Sciences University of Nottingham Nottingham, UK Karthik.Bharath@nottingham.ac.uk

Matthew Reimherr Department of Statistics Pennsylvania State University University Park, PA mreimherr@psu.edu

Aleksandra Slavkovic Department of Statistics Pennsylvania State University University Park, PA sesa@psu.edu

It is common for data structures such as images and shapes of 2D objects to be represented as points on a manifold. The utility of a mechanism to produce sanitized differentially private estimates from such data is intimately linked to how compatible it is with the underlying structure and geometry of the space. In particular, as recently shown, utility of the Laplace mechanism on a positively curved manifold, such as Kendall s 2D shape space, is significantly influenced by the curvature. Focusing on the problem of sanitizing the Fréchet mean of a sample of points on a manifold, we exploit the characterisation of the mean as the minimizer of an objective function comprised of the sum of squared distances and develop a K-norm gradient mechanism on Riemannian manifolds that favors values that produce gradients close to the the zero of the objective function. For the case of positively curved manifolds, we describe how using the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism, and demonstrate this numerically on a dataset of shapes of corpus callosa. Further illustrations of the mechanism s utility on a sphere and the manifold of symmetric positive definite matrices are also presented.

1 Introduction

The amount of publicly available data has increased exponentially over the past decade and alongside with it the need for data privacy has emerged. As data gets increasingly more complex from scalar values to data on nonlinear manifolds, such as images, shapes and covariance matrices, there is a need for data privacy algorithms to adapt to the nonlinearity in, and preserve the geometric structure of, the data or parameter space. Intuitively, when the geometry of the manifold significantly influences sensitivity bounds through curvature-dependent terms, one would expect a structurepreserving privacy mechanism developed directly on manifolds to have better utility than its Euclidean counterpart on higher-dimensional ambient spaces within which the manifold is embedded. This was observed in recent work on a Laplace mechanism on manifolds [Reimherr et al., 2021], and especially for manifolds with positive curvature.

Apart from spherical, or directional, data, an archetypal example of data on a positively curved manifold arises in statistical shape analysis of planar configurations representing 2D objects; the Kendall shape space of 2D points [Kendall, 1984] modulo shape-preserving similarity transformations (e.g., rotations) is a Riemannian manifold with positive curvature. It is evident in this setting that

36th Conference on Neural Information Processing Systems (Neur IPS 2022).

the utility of a privacy mechanism will depend on how well it is compatible with shape preserving transformations of the data sanitized versions of a shape summary of a 2D image of a bird should look like a bird, impervious to (global) rotation, scaling and translation.

Structure-preserving mechanisms within specific contexts have been considered before; see, for example Jiang et al. [2016] concerning covariance matrices; Imtiaz and Sarwate [2018, 2016], Gilad Bachrach and Gonen [2017], Awan et al. [2019], Chaudhuri et al. [2013], Biswas et al. [2020] for private principal component analysis; and Sheffet [2015] for private linear regression. A general structure-preserving Laplace mechanism on manifolds was considered by Reimherr et al. [2021], in Awan and Slavkovi c [2021] the relationship between the data space and the sensitivity was examined in sufficient generality, and a general Gaussian mechanism on Riemmanian manifolds for approximate differential privacy was considered by Han et al. [2022]. However, research on privatizing shape summaries with theoretical guarantees is conspicuous in its absence within the privacy literature; the most relevant one we have found comes from computer vision which produces random faces but offers no differentially private guarantees [Karras et al., 2019].

The two-fold motivation for our paper is to a develop a privacy mechanism for statistical shape analysis, and more generally for data on manifolds, that is compatible with the geometry of the underlying space, and further, offers better control on how the curvature influences global sensitivity bounds. To this end, our main contributions are as follows.

1. We develop an extension of the K-norm Gradient Mechanism (KNG) on Rd [Reimherr and Awan, 2019] for producing sanitized private estimates under the pure differential privacy framework to the setting of Riemannian manifolds, with a focus on mean estimation. 2. We derive a curvature-dependent upper bound on global sensitivity, which for the important case of positively curved manifolds is smaller than the corresponding one arising from a recently proposed Laplace mechanism [Reimherr et al., 2021]. Our numerical examples verify that the KNG mechanism on manifolds shares the powerful utility of its counterpart on Rd, and this is is tied to the curvature of the manifold and not to the dimension of the ambient space. 3. We introduce the first, to our knowledge, differentially private shape analysis under Kendall s 2D shape space framework, and favorably compare its performance to mechanisms designed for the higher-dimensional ambient space (and not directly on the manifold) on a dataset of corpus callosa obtained from MR images.

2 Background

In this section we introduce the necessary tools from differential geometry and differential privacy as well as the notation for this paper. For a thorough exposition of differential geometry and shape analysis we refer to Do Carmo [1992], Srivastava and Klassen [2016] and for DP we refer to Dwork and Roth [2014].

2.1 Differential geometry

Let M be a complete, connected Riemannian manifold of dimension d. Denote by Tm M the tangent space at each point m M and by TM = {Tm M : m M} the collection of tangent spaces, known as the tangent bundle. On the tangent space Tm M at each point m, we can define an inner product , m : Tm M Tm M R with induced norm m; the collection { , m : m M} is referred to as a Riemannian metric. The Riemannian metric varies smoothly along the manifold and allows us to measure distances, volumes, and angles.

For a curve, or path, α : [0, 1] M, the vector α (t) is its instantaneous velocity, and its length L(α) is the value R 1 0 α (t) 1/2 α(t)dt. A curve α is said to be arc-length parameterised if α (t) α(t) 1 and thus L(α(0), α(t0)) = t0. Geodesic curves are those with zero acceleration for all t. The distance ρ between two points p and q is the length of the shortest path, a segment of a geodesic curve connecting the two known as the minimal geodesic: ρ(p, q) = inf{L(α)|α : [0, 1] M; α(0) = p, α(1) = q}.

Given a point p and a geodesic α with α(0) = p, a cut point of p is defined as the point α(t0) such that α is a minimal geodesic on the interval [0, t0] but fails to be for t > t0. The set of all cut points of geodesics starting at p is its cut locus. The injectivity radius of p is the distance to its cut locus, and the injectivity radius inj M of M is the infimum of the injectivity radii of all points in M.

The next two tools are necessary for moving on the manifold, moving to and from the tangent spaces, and are particularly useful for sampling from distributions on manifolds. For a geodesic α starting at p with initial velocity v, the exponential map exp(p, ) : Tp M M : is defined as exp(p, v) = α(1). From the Hopf-Rinow theorem, on a complete manifold the exponential map is surjective. On an open ball around the origin in Tp M it is a diffeomorphism onto its image outside of the cut locus of p, and a well-defined inverse exp 1(p, ) : M Tp M exists, known as the inverse exponential or logarithm map, that maps a point on M outside of the cut locus of p to Tp M; thus for any q outside of the cut locus of p, ρ(p, q) = exp 1(p, q) p.

There are many notions of curvature of a Riemannian manifold. We will mainly be concerned with sectional curvature at a point p, defined to be the Gaussian curvature at p of the two-dimensional surface swept out by the set of all geodesics starting at p with initial velocities lying in the twodimensional subspace of Tp M spanned by two linear independent vectors.

Further, volumes of sets can be computed using the Riemannian volume form dµ. In local coordinates, the coordinate-independent Riemannian volume form is defined as p

det(g)dx1 dx2 dxd, where gij = xi, xj is the Riemannian metric tensor. A vector field on M is a differentiable mapping M TM that assigns to each point m on M a tangent vector in Tm M. Suppose we have a smooth function h defined over M, the gradient h of h is the vector field defined by the relationship h(p), v p = hp(v) for p M and v Tp M.

2.2 Differential privacy

Let D = {x1, . . . , xn} M denote a dataset of size n. In several statistical and machine learning problems, one of the most popular tools for releasing a sanitized version of a minimizer

ˆθ = argmaxx M U(x; D)

of a utility function U over M is the exponential mechanism introduced by Mc Sherry and Talwar [2007], based on a density f(x; D) exp σ 1U(x; D) , where the scale or rate parameter σ is chosen to achieve a desired level of privacy and accounts for the sensitivity of U. If M is the Euclidean space, the density is with respect to the Lebesgue measure, and for finite or countable M, it is with respect to the counting measure.

A modification of the exponential mechanism is the K-norm Gradient Mechanism (KNG) introduced by Reimherr and Awan [2019], which turns out to have better utility quite generally. The idea is that the maximizer of U(x; D) is also the point at which its gradient is zero. On a Riemannian manifold M, a KNG mechanism can be constructed using the gradient vector field U(x; D), where the gradient is defined with respect to the Riemannian metric, with the (unnormalised) density

f(x; D) exp{ σ 1 U(x; D) x}

defined with respect to the volume measure [Reimherr et al., 2021], where x refers to the norm with respect to Riemannian metric at x, not be confused with the subscript k as in a k-norm. For general manifolds M, conditions on the sectional curvatures are typically needed to ensure that the density is integrable with a finite normalizing constant. Under such conditions we can introduce a definition of differential privacy similar to that of Blum et al. [2005]. Definition 1. For ϵ > 0, a privacy mechanism satisfies ϵ-differential privacy (pure differential privacy, ϵ-DP) if for any pair of adjacent databases D and D , denoted D D , we have that Z

S f(x; D)dµ eϵ Z

S f(x; D )dµ

for any measurable set S M.

To determine the rate parameter for the KNG mechanism, one needs to quantify the robustness or sensitivity, of the norm of gradient vector field for adjacent databases. Theorem 1. If for all neighboring D D and almost all x we have

U(x; D) U(x; D ) x ,

then one can take σ = 2 /ϵ so that the KNG mechanism will be ϵ-DP. Here is referred to as the global sensitivity.

The proof of Theorem 1 follows directly from an application of the triangle inequality. The global sensitivity plays a crucial role in determining the behavior of KNG about the optimizer of U. Thus far, U has been a generic utility function however consideration needs to be taken for cases when U does not have a global optimizer.

3 Differentially private Fréchet mean estimation theory

Possibly the most fundamental summary statistic is the average or mean. In a Euclidean setting, the mean has a closed form expression, which for general manifolds is rarely the case. Generalizing the notion of the Euclidean mean, the Fréchet mean is defined as the minimizer of the variance functional

F( , D) : M R+, F(x; D) := 1

i=1 ρ(xi, x)2,

where ρ is the Riemannian distance. In general, the minimizer may not exist, and may not be unique when it does. Study of conditions that ensure existence and uniqueness has a long history (see for e.g., Karcher [1977] and Afsari [2011]), and we thus take some necessary precautions outlined in Assumption 1. Assumption 1. The dataset D Br(p0), a geodesic ball centered at p0 with finite radius r, with r < 1

2 min{inj M, π

2 κ 1/2 max } and κmax > 0 is an upper bound on the sectional curvatures of M.

For non-positively curved M, κ 1/2 max is interpreted as + , and Assumption 1 states that the data D must be bounded. That is, the data can lie in a ball of any arbitrary size as long as we know how large the ball is as this directly affects the global sensitivity. The weaker requirement r < 1/2 min{inj M, πκ 1/2 max } suffices to ensure existence and uniqueness of the Fréchet mean. However, the stronger Assumption 1 is required to ensure that (x, y) 7 ρ2(x, y) is convex along geodesics (geodesically convex) within Br(p0) Le [2001]; for example, ρ2 is convex when restricted to a ball of radius smaller than π/4 on unit spheres since κmax = 1. For ρ2 to be strong geodesically convex, an additional lower bound on sectional curvatures of M is required (see Lemma 1).

For mean estimation a natural utility function is U(x; D) = F(x; D). The KNG mechanism makes use of the gradient of U(x; D) at x and hence the (Riemannian) gradient of F(x; D), which in-turn is linked to the gradient of square-distance function x 7 ρ(xi, x)2 for fixed xi. Under Assumption 1, each xi lies within the injectivity radius of x, and the gradient ρ(xi, x)2 = 2 exp 1(x, xi). Thus

F(x; D) = 1

i=1 exp 1(x, xi).

The KNG mechanism then samples from the density (with respect to the volume measure)

f(x; D) exp

i=1 exp 1(x, xi)

to release a private statistical summary of the mean; note that when restricted to an open ball as per Assumption 1, the density f has a finite normalising constant that depends on σ.

In Theorem 2 we provide a bound for the the global sensitivity of the KNG mechanism for mean estimation on Riemannian manifolds. The bound is curvature-dependent in the sense that it depends on the radius r of the ball in which the data lies, the sample size n, and a function of r and κmax. Specifically, the bound is equivalent to the bound obtained for Euclidean spaces for non-positively curved M but is inflated for positively curved M. Theorem 2. Under Assumption 1 let D = {x1, x2, . . . , xn} and D = {x1, x2, . . . , x n} be adjacent datasets . Then

U(x; D) U(x; D ) x 2r(2 hmax(2r, κmax))

hmax(s, κmax) := s κmax cot(s κmax), κmax > 0 ; 1, κmax 0 . (1)

Proof. For two adjacent databases D D that, without loss of generality, differ in the last element we have that

U(x; D) U(x; D ) x = F(x; D) F(x; D ) x = 1

exp 1(x, xn) exp 1(x, x n) x

n2r(2 hmax(2r, κmax)),

based on Jacobi field estimates from Karcher [1977]; see also [Reimherr et al., 2021, Lemma 1].

Remark 1. For the Laplace mechanism on M with density f(x; D) e 1

σ ρ(x,η) for a fixed point η, whenever r is chosen as per Assumption 1, the magnitude of inflation of global sensitivity due to curvature was shown to be 2r(2 hmax(2r, κmax))/(nhmax(2r, κmax)) in Reimherr et al. [2021]. The upper bound obtained by the KNG mechanism is thus strictly smaller for positively curved spaces since 0 < hmax(2r, κmax) < 1; in our experiments (see 4.1), this difference in sensitivity appears to result in better utility. Although the densities for the KNG and the Laplace are not the same, they are related to the norm of a vector in Tx M: when η = x, the Fréchet mean, since ρ(x, x) = exp 1(x, x) x, the Laplace density uses the norm of the Fréchet mean x when projected onto Tx M; on the other hand, the KNG density uses the norm of the sample mean of data {xi} when projected onto Tx M.

Our next theorem shows that the utility of KNG on manifolds, as measured by the intrinsic distance ρ( x, x) matches the optimal rate of O(d/nϵ) as in Euclidean space. For the theorem however we require the following Lemma, proof of which is available in the Supplemental materials. Lemma 1. In addition to Assumption 1, assume that there exists a κmin R that lower bounds the sectional curvatures of M. Denote by x the Fréchet mean of D. For every x Br(p0),

hmax(2r, κmax)ρ( x, x) U(x, D) x hmin(2r, κmin)ρ( x, x), where

hmin(s, κmin) := s p

|κmin| coth(s p

|κmin|), κmin < 0 ; 1, κmin 0 . (2)

Theorem 3. Assume the setting of Lemma 1. Let x denote a draw from the KNG mechanism restricted to Br(p0), and x be the unique global optimizer of U(x; D). We have that

E ρ( x, x)2 = O d2

Proof. Recall that under Assumption 1, f(x; D) = C 1 σ exp σ 1 U(x; D) x for a finite normalizing constant C 1 σ . Then

Br(p0) exp σ 1hmin(2r, κmin)ρ(x, x) dµ(x),

which due to Lemma 1 results in the upper bound

E ρ( x, x)2

Br(p0) ρ(x, x)2e 1

σ hmax(2r,κmax)ρ(x, x)dµ(x) R

σ hmin(2r,κmin)ρ(x, x)dµ(x) . (3)

Since r 1 2inj M, there exists a unique vx exp 1( x, (Br(p0)) B2r( x) such that vx = exp 1( x, x), where B2r( x) = {v T x M : v x < 2r} is the open ball of radius 2r centred at the origin in T x M. Denote by S x the bounded subset exp 1( x, (Br(p0)) B2r( x) of T x M with compact closure. With respect to the pushforward of dµ on to T x M under the inverse exponential map at x, the ratio in (3) equals R

S x vx 2 xe 1

σ hmax(2r,κmax) vx xd(µ exp( x, ))(vx) R

σ hmin(2r,κmin) vx xd(µ exp( x, ))(vx) .

The induced measure d(µ exp( x, )) on T x M can be extended to Rd by settings its value on the complement of S x to be zero. It is then absolutely continuous with respect to the Lebesgue measure

dλ on Rd with a Jacobian determinant uniformly bounded above and below, respectively, by constants c1 and c2 on (the closure) of S x. This ensures that the above ratio is upper bounded by

Rd vx 2 xe 1

σ hmax(2r,κmax) vx xdλ(vx) R

σ hmin(2r,κmin) vx xdλ(vx) ,

which, with a change of variables and using spherical coordinates, equals

hmin(2r, κmin) hmax(2r, κmax)3

0 zd 1e zdλ(z) 1 Z

0 zd+1e zdλ(z) = O d2

since the curvature-dependent terms hmin(2r, κmin) and hmax(2r, κmax), defined in (1) and (2), are both positive and finite under Assumption 1, σ is as in Theorems 1 and 2, and the integrals in the numerator and denominator equal (d + 1)! and (d 1)!, respectively.

In this Section, we consider two simulated examples and a real data example on 2D shapes. For the former, we consider the positively curved unit d-sphere and the set of symmetric positive definite matrices (SPDM), which when equipped with an affine invariant metric is negatively curved. Manifold valued data naturally emerges in statistical applications such as with SPDM matrices in computer vision Caseiro et al. [2012] and brain diffusion tensor data Niethammer et al. [2006], discrete distributions can be modeled on a sphere, in network analysis Ginestet et al. [2017] for instance, and we refer to Younes [2012], Kimmel [2003] as references with a more complete overview.

In each scenario we sample from KNG via Metropolis-Hastings, a Monte Carlo Markov Chain method. This sampling method estimates our target distribution KNG and can incur a privacy loss. That is, KNG is an instantiation of the exponential mechanism and sampling from such a mechanism via MCMC produces approximate DP samples rather than pure DP samples Shen and Yu [2013], Wang et al. [2015]. The size of this cost is a function of the chain length, however, and decreases to zero at a geometric rate, so sampling must be done in a careful manner. An exact sampler would be ideal, however even for some cases of well-behaved distributions sampling is not so simple Seeman et al. [2021]. This issue is a limitation of this work and we leave this as an open problem.

4.1 Spheres

Let Sd κ denote the d-dimensional sphere with radius κ 1/2. The sphere equipped with the induced metric from Rd+1, the canonical metric, has constant positive curvature κ. The tangent space at p Sd κ is then Tp Sd κ = {v Rd+1| v, p = 0}. The exponential map, defined on all of Tp Sd κ, is given by exp(p, v) = cos( v )p + κ 1/2 sin( v )v/ v and exp(p, 0) = p. The set of points at a distance at least π from p constitutes its cut locus, which then is the singleton { p}. With θ := ρ(p, q) = cos 1( p, q ), the inverse exponential map exp 1(p, q) = θ(sin(θ)) 1(q cos(θ)p) at p is hence defined only within the open ball around p with radius π/(2κ1/2).

Next, we consider the utility of KNG on a manifold and compare it to other sanitization techniques. We generate random samples D from S2 1 and compute the Fréchet mean x, both as described in the Supplemental material. We set ϵ = 1 and sanitize x with three separate methods; first with the proposed method KNG on manifolds to produce x KNG, second with the Laplace on manifolds as in Reimherr et al. [2021] to produce x L, and lastly embedding x into R3 and privatizing with the Euclidean Laplace to produce x E. The latter almost surely will not be on the sphere, however, since the privacy guarantees are invariant to post-processing, we project the estimate back onto the sphere by normalizing as x E x E/ x E .

We compute several such replicates at different sample sizes and display the utility comparison in the first (left) panel of Figure 1, where the utility is measured using the average Euclidean distance x x such that x is a the respective sanitized estimate. We see that adding noise in the ambient space with the Euclidean Laplace adds the most noise, which may be attributed to the need to sanitize over an extra dimension. After post-processing x E by projecting onto the sphere, the Euclidean Laplace mechanism does have better utility than its manifold counterpart, but this is not unexpected since the sensitivity of the manifold Laplace for positively curved manifolds is inflated compared to

Figure 1: Utility measured using average Euclidean distance between the Fréchet mean x and its sanitized version x, when M is the unit sphere S2 1 in two dimensions (left) and k k SPD matrices P(k) (right), under the following frameworks: (i) Manifold KNG; (ii) Euclidean Laplace by embedding x into the ambient space; (iii) Manifold Laplace on the manifold; and additionally, with (iv) Projected Euclidean Laplace for the unit sphere. For the Euclidean Laplace x was embedded into R3 for S2 1 and within k k symmetric matrices for P(k). For each sample size, 10000 replicates were used for S2 1, whereas 500 were used for P(k). Shaded regions represent the average distance 2SE, where the Euclidean distance for P(k) is vech( x) vech( x) .

the Euclidean rate of 2r/n Reimherr et al. [2021]. Lastly, our proposed mechanism has the best utility in this comparison which may be attributed to its sensitivity being strictly less than the sensitivity of the Laplace on the manifold for positively curved manifolds. Further, our approach will always produce a private summary which is on the manifold and does not require any post-processing.

4.2 Symmetric positive-definite matrices

Denote by P(k) the k(k + 1)/2 dimensional manifold of k k symmetric positive-definite matrices equipped with the affine-invariant Rao-Fisher metric v, u p = Tr(p 1up 1v), where u, v Tp P(k) = Symk are symmetric matrices. With this Riemannian metric P(k) has negative sectional curvature everywhere with exponential map exp(p, v) = p1/2Exp p 1/2vp 1/2 p1/2 and globally defined inverse exponential map exp 1(q, p) = q1/2Log q 1/2pq 1/2 q1/2, where Exp( ) and Log( ) are the matrix exponential and logarithm, respectively. The distance between q and p in P(k) is thus ρ(q, p) = exp 1(q, p) q = Tr[Log(q 1/2pq 1/2)2]1/2.

For the simulations we set k = 2. We generate random samples D P(k) by sampling from the Wishart distribution as discussed in the Supplemental materials. We compute the Fréchet mean x and sanitize it with three separate approaches: (i) we generate a private mean x KNG by sanitizing on P(k) using the proposed approach KNG, (ii) we generate a private mean x L on P(k) with the Laplace distribution as in Reimherr et al. [2021], Hajri et al. [2016], and (iii) we embed x into Symk the space of symmetric matrices, represent x as a vector vech( x) R3, sanitize by sampling from the Euclidean Laplace to produce vech( x E), and lastly we revert the vectorization to obtain x E. There is no guarantee that x E will remain in P(k) and further without a unique projection to P(k) since it is an open cone within Rk(k+1)/2.

Similarly to Section 4.1, in the second panel of Figure 1 we display an average utility comparison of the privatization techniques over 500 replicates with respect to the distance vech( x) vech( x) , where x is the sanitized estimate corresponding to one of the three approaches. We see that our approach has better utility compared to the Euclidean approach and comparable utility to the Laplace on P(k). The latter is not entirely surprising since the Laplace is equivalent to KNG for mean estimation in Euclidean space [Reimherr and Awan, 2019]. Sampling from the Laplace on P(k) is fairly simple since it was thoroughly studied by Hajri et al. [2016] and has nearly a closed form sampler; sampling from KNG on P(k) however is not as straightforward and we employed an Metropolis-Hastings algorithm which may account for its inconsistent behavior compared to the Laplace. However, our proposed method has better utility than the Euclidean approach, which is designed on the higher-dimensional ambient space.

4.3 Kendall s 2D shape space

Statistical shape analysis is a relatively recent field dating back to the seminal paper by Thompson and Thompson [1942] where shapes of animals, such as fish, were shown to differ in geometric transformations such as a shear. Since this conception there have been many branches of shape analysis that have arisen such as Kendall s shape space [Kendall, 1984], large deformation diffeomorphic metric mapping (LDDMM) [Grenander and Miller, 2007], and elastic shape analysis [Srivastava and Klassen, 2016]. No matter the choice, shape analysis has demonstrated to be widely applicable in the medical field (ERCAN et al. [2012], Li et al. [2014]), computer vision [Jimenez et al., 2000, Sharon and Mumford, 2006], and functional data analysis (Harris et al. [2021], Zhang and Srivastava [2020]). By shape" of an object in two dimensions, we refer to the intrinsic geometric property of a set of points on the plane (representing the object) that remains unchanged under similarity transformations such as translation, rotation and scale Kendall [1984], and additionally on reparameterisations if an outline curve representation is used Srivastava and Klassen [2016]. Of the many areas of shape analysis available (for e.g., the theory of deformable templates [Trouvé and Younes, 2005] and Large deformation diffeomorphic metric mapping [Grenander and Miller, 2007]) we consider the Kendall shape space of two-dimensional landmark configurations Kendall [1984].

Consider a set x = {xj} Ck of labelled k points on a 2D object, known as landmarks, in the complex plane. If the object has been extracted from a densely sampled outline curve (for e.g., when extracted/segmented from a 2D image), then the parameterisation of the curve induces the labelling through an ordering of the points. Labelling thus establishes a correspondence between points on different objects, and is considered to be fixed.

The shape of x is what remains once translation, scaling and rotation variabilities are removed or accounted for. Translation is removed by by transforming x x 1

k Pk j=1 xj resulting in a reduced space of the complex (k 1) dimensional hyperplane C = {x Ck\0| 1

k P xj = 0}. Scaling and rotation of x amounts to multiplying by a complex number reiθ where r is the scaling factor and θ is the angle of rotation. The shape of x then can be considered as the curve ( π, π] θ 7 eiθu on the complex unit (k 1)-dimensional sphere CSk 1 in C, where u = x/ x C (or the real sphere of dimension 2k 3), x =

x x and x the complex conjugate of x. The shape space is thus identified with the compact complex projective space CP k 2 of dimension k 2 following the scaling x x/ x , x C. Therefore, the geodesic shape distance between landmark configurations x and y with corresponding centred and scaled versions p and q is ρ(x, y) = infθ (π,π] cos 1 |e iθpq | ; thus, the injectivity radius of the shape space is π/2.

Let x be a centred and scaled configuration. Minimizing unit-speed geodesics starting at x and initial velocity v in the shape space are isometrically identified with unit-speed geodesics ( π/2, π/2] s 7 x cos(s) + v cos sin(s) on CSk 1 wherein v satisfies v1k = 0 in addition to xv = 0, and 1k is the vector of ones[Kendall et al., 1999, Chapter 6]; such geodesics are known as horizontal geodesics. Consequently, the exponential map on the shape space is given by the corresponding one on the sphere with the additional condition on the velocity vectors. The inverse exponential map at x exists within a ball of radius smaller than π/2 in the shape space, and is thus given by exp 1(x, y) = θ y Projx(y) , where Projx(y) := x(y x) is the projection of y onto x and θ = cos 1 |x y|. The (complex) holomorphic sectional curvature of the 2D Kendall s shape space is constant and equals 4 [Kendall et al., 1999].

As an application we consider the pre-processed corpus callosum data of Cornea et al. [2017] from the Alzheimer s Disease Neuroimaging Initiative (ADNI). The data are from the mid-sagittal slices of MRIs (magnetic resonance images) and we refer to Cornea et al. [2017] on details of how the data was processed. Their data contains 409 total corpus callosa. The left portion of Figure 2 displays 10 sample corpus callosa where the parameterization is visually displayed as a color gradient from blue to yellow. In the middle we display the Fréchet mean of all 409 corpus callosa. Having computed the mean, we then sanitize the mean with three techniques: (i) using the proposed KNG mechanism (Right: top row); (ii) for a comparison with (i), sanitize each landmark of the mean using the Laplace mechanism splitting the privacy budget (Right: middle row); (iii) sanitize each landmark as in (ii) without factoring in rotational alignment in the corpus callosum. We expand on (ii) and (iii) in the Supplemental material.

Figure 2: Left panel: A sample of ten corpus callosa from the sample of 409. Middle: The Fréchet mean corpus callosum. Right, top row: Six sample private corpus callosa privatized under the KNG framework on Kendall s 2D shape space. Right, middle row: Six sample private corpus callosa privatized point-wise with the Laplace mechanism. Right, bottom row: Six sample private corpus callosa privatized point-wise with the Laplace without accounting for rotational alignment. For more details, please refer to 4.3.

Figure 3: Differentially private corpus callosa estimates post-processed by using a first order local linear regression for smoothness. The left six are private under the proposed KNG framework while the right six are private under the point-wise Laplace as explained in Section 4.3.

As we can observe in Figure 2, when one does not account for shape-preserving transformations (rotations alignment in this example), the shape of the corpus callosum is entirely destroyed during sanitization. Sanitization over the shape manifold (Right: top row) tends to retain the structure of corpus callosum when compared with sanitizing over each coordinate (Right: middle row), which appears more distorted; for example, we observe that the shape of the fifth corpus callosum (Right: middle row) has a contour with crossings. Further, we post-process to smooth the private estimates by a first order local linear regression. Left panel of Figure 3 displays the post-processed KNG private estimates while the right panel shows point-wise Laplace private estimates, where rotational alignment has been carried out. We do not post-process the private estimates which do not consider rotational alignment as they appear to be non informative. Considering the mean shape in Figure 2, the hook" at the top is quite prominent and comparing this to the private corpus callosa of Figure 3 we notice that the KNG estimates tend to preserve this structure. Even though all the private estimates are processed in the same way, we notice the Laplace estimates are not only less smooth but can possess undesirable distortions, such as additional features such as loops.

5 Conclusions and future work

In this paper we demonstrate that versatility and powerful utility of the K-norm gradient mechanism on Rd carries over to the manifold setting. In particular, better control over global sensitivity when compared to the recently introduced manifold Laplace mechanism [Reimherr et al., 2021] for positively curved manifolds motivates the development of, to our knowledge, the first privacy mechanism for statistical shape analysis of 2D point configurations. Gains in utility when working directly on the manifold, as opposed to the higher-dimensional ambient space, are observed in the numerical examples: in terms of utility, the KNG not only outperforms the Euclidean mechanism but also the manifold Laplace mechanism. Further, the Laplace on the manifold and our mechanism are intricately connected as they both are the exponential of a norm in a particular tangent space as we

note in Remark 1; this similarity in formulation and difference in sensitivity is tied to the better utility in the case of positively curved manifolds.

Depending on the manifold, statistical utility gains enjoyed by working on the manifold can be tempered by expensive geometric computation. For example, in the case of SPDM, the clear gains in utility are obtained within the context of computationally expensive sampling from the KNG (see also Supplemental material) owing to repeated computations of matrix inverses and square roots related to the exponential, inverse-exponential maps and the geodesic distance. Indeed in practice, however, only a single instantiation suffices. In contrast, sampling from the Laplace on manifolds is straightforward, and there is thus room for improvement in sampling from the KNG on manifolds.

Our work represents a step in the right direction in developing privacy mechanisms for a myriad of approaches to state-of-the-art statistical shape analysis on infinite-dimensional manifolds of curves and surfaces [Srivastava and Klassen, 2016], and diffeomorphisms [Grenander and Miller, 2007]. Moreover, our work opens up the possibility of developing geometry-driven privacy mechanisms for standard data analytic procedures used in various applications, such as principal component analysis (Grassmannian manifold of subspaces), rank-constrained matrix completion (quotient manifold of nonsingular matrices), and optimizing the Rayleigh quotient (Grassmannian), Procrustes problem (manifold of orthogonal matrices or frames), and pose estimation in computer vision (manifold of rotation matrices).

Acknowledgments and Disclosure of Funding

This work was funded in part by NSF SES-1853209 (to CS, MR, AS), NSF DMS-2015374 and EPSRC EP/V048104/1 (to KB).

B. Afsari. Riemannian Lp center of mass: existence, uniqueness and convexity. Proceedings of the American Mathematical Society, 139(2):655 673, 2011.

J. Awan and A. Slavkovi c. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, 116(534):935 954, 2021.

J. Awan, A. Kenney, M. Reimherr, and A. Slavkovi c. Benefits and pitfalls of the exponential mechanism with applications to hilbert spaces and functional pca. In International Conference on Machine Learning, pages 374 384. PMLR, 2019.

S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33, 2020.

A. Blum, C. Dwork, F. Mc Sherry, and K. Nissim. Practical privacy: the Su LQ framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128 138, 2005.

R. Caseiro, P. Martins, J. F. Henriques, and J. Batista. A nonparametric riemannian framework on tensor field with application to foreground segmentation. Pattern Recognition, 45(11):3997 4017, 2012.

K. Chaudhuri, A. D. Sarwate, and K. Sinha. A near-optimal algorithm for differentially-private principal components. Journal of Machine Learning Research, 14, 2013.

E. Cornea, H. Zhu, P. Kim, J. G. Ibrahim, and A. D. N. Initiative. Regression models on riemannian symmetric spaces. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79 (2):463 482, 2017.

M. P. Do Carmo. Riemannian geometry, volume 6. Springer, 1992.

C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 4):211 407, 2014.

I. ERCAN, G. OCAKO GLU, D. SI GIRLI, and G. ÖZKAYA. Statistical shape analysis and usage in medical sciences. Turkiye Klinikleri Journal of Biostatistics, 4(1), 2012.

R. Gilad-Bachrach and A. Gonen. Smooth sensitivity based approach for differentially private principal component analysis. ar Xiv preprint ar Xiv:1710.10556, 2017.

C. E. Ginestet, J. Li, P. Balachandran, S. Rosenberg, and E. D. Kolaczyk. Hypothesis testing for network data in functional neuroimaging. The Annals of Applied Statistics, pages 725 750, 2017.

U. Grenander and M. Miller. Pattern Theory: From Representation to Inference. Oxford University Press, 2007.

H. Hajri, I. Ilea, S. Said, L. Bombrun, and Y. Berthoumieu. Riemannian Laplace distribution on the space of symmetric positive definite matrices. Entropy, 18(3):98, 2016.

A. Han, B. Mishra, P. Jawanpuria, and J. Gao. Differentially private riemannian optimization. ar Xiv preprint ar Xiv:2205.09494, 2022.

T. Harris, J. D. Tucker, B. Li, and L. Shand. Elastic depths for detecting shape anomalies in functional data. Technometrics, 63(4):466 476, 2021.

H. Imtiaz and A. D. Sarwate. Symmetric matrix perturbation for differentially-private principal component analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2339 2343. IEEE, 2016.

H. Imtiaz and A. D. Sarwate. Differentially private distributed principal component analysis. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2206 2210. IEEE, 2018.

W. Jiang, C. Xie, and Z. Zhang. Wishart mechanism for differentially private principal components analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.

A. Jimenez, R. Ceres, and J. L. Pons. A survey of computer vision methods for locating fruit on trees. Transactions of the ASAE, 43(6):1911, 2000.

H. Karcher. Riemannian center of mass and mollifier smoothing. Communications on pure and applied mathematics, 30(5):509 541, 1977.

T. Karras, S. Laine, and T. Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401 4410, 2019.

D. G. Kendall. Shape manifolds, procrustean metrics, and complex projective spaces. Bulletin of the London mathematical society, 16(2):81 121, 1984.

D. G. Kendall, D. Barden, T. K. Carne, and H. Le. Shape and Shape Theory. Wiley, 1999.

R. Kimmel. Numerical geometry of images: Theory, algorithms, and applications. Springer Science & Business Media, 2003.

H. Le. Locating Fréchet means with applications to shape spaces. Advances in Applied Probability, 33(2):324 338, 2001.

S. Li, J. M. R. Tavares, et al. Shape Analysis in Medical Image Analysis. Springer, 2014.

F. Mc Sherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07), pages 94 103, 2007. doi: 10.1109/ FOCS.2007.66.

M. Niethammer, R. S. J. Estepar, S. Bouix, M. Shenton, and C.-F. Westin. On diffusion tensor estimation. In 2006 International Conference of the IEEE Engineering in Medicine and Biology Society, pages 2622 2625. IEEE, 2006.

M. Reimherr and J. Awan. Kng: The k-norm gradient mechanism. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings. neurips.cc/paper/2019/file/faefec47428cf9a2f0875ba9c2042a81-Paper.pdf.

M. Reimherr, K. Bharath, and C. J. Soto. Differential privacy over riemannian manifolds. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https://openreview.net/forum?id=6oye Q-1c_91.

J. Seeman, M. Reimherr, and A. Slavkovi c. Exact privacy guarantees for markov chain implementations of the exponential mechanism with artificial atoms. Advances in Neural Information Processing Systems, 34:13125 13136, 2021.

E. Sharon and D. Mumford. 2d-shape analysis using conformal mapping. International Journal of Computer Vision, 70(1):55 75, 2006.

O. Sheffet. Private approximations of the 2nd-moment matrix using existing techniques in linear regression. ar Xiv preprint ar Xiv:1507.00056, 2015.

E. Shen and T. Yu. Mining frequent graph patterns with differential privacy. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 545 553, 2013.

A. Srivastava and E. P. Klassen. Functional and shape data analysis, volume 1. Springer, 2016.

D. W. Thompson and D. W. Thompson. On growth and form, volume 2. Cambridge university press Cambridge, 1942.

A. Trouvé and L. Younes. Local geometry of deformable templates. SIAM journal on mathematical analysis, 37(1):17 59, 2005.

Y.-X. Wang, S. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2493 2502. PMLR, 2015.

L. Younes. Spaces and manifolds of shapes in computer vision: An overview. Image and Vision Computing, 30(6-7):389 397, 2012.

R. Zhang and A. Srivastava. On shape analysis of functional data. In Riemannian Geometric Statistics in Medical Image Analysis, pages 417 438. Elsevier, 2020.

1. For all authors...

(a) Do the main claims made in the abstract and introduction accurately reflect the paper s contributions and scope? [Yes] (b) Did you describe the limitations of your work? [Yes]

(c) Did you discuss any potential negative societal impacts of your work? [N/A] (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] 2. If you are including theoretical results...

(a) Did you state the full set of assumptions of all theoretical results? [Yes] The overall assumptions are outlined in Assumption 1 which we reference in each theorem along with any other necessary assumptions. (b) Did you include complete proofs of all theoretical results? [Yes] 3. If you ran experiments...

(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] All code is provided as a zipped folder. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] This is mentioned in Section 4 and expanded on in the Supplemental materials. (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] In our Figure 1 we display standard error bars from replications.

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] This is included in the Supplemental materials. 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...

(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4.3. (b) Did you mention the license of the assets? [N/A]

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]

(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A] (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] 5. If you used crowdsourcing or conducted research with human subjects...

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]