Extreme points of the local differential privacy polytope

被引：10
作者：
Holohan, Naoise [1 ,4 ]
Leith, Douglas J. [1 ]
Mason, Oliver [2 ,3 ]
机构：
[1] Trinity Coll Dublin, Sch Comp Sci & Stat, Dublin, Ireland
[2] Maynooth Univ, Hamilton Inst, Dept Math & Stat, Maynooth, Kildare, Ireland
[3] Lero, Limerick, Ireland
[4] IBM Res, Dublin, Ireland
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2017年 / 534卷
基金：
爱尔兰科学基金会;
关键词：
Data privacy; Stochastic matrices; Matrix polytopes; Differential privacy; MATRICES;
D O I：
10.1016/j.laa.2017.08.011
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We study the convex polytope of n x n stochastic matrices that define locally &differentially private mechanisms. We first present invariance properties of the polytope and results reducing the number of constraints needed to define it. Our main results concern the extreme points of the polytope. In particular, we completely characterise these for matrices with 1, 2 or n non-zero columns. (C) 2017 Elsevier Inc. All rights reserved.
引用
收藏
页码：78 / 96
页数：19
相关论文
共 19 条
  • [1] ADAM NR, 1989, COMPUT SURV, V21, P515, DOI 10.1145/76894.76895
  • [2] Barvinok A., 2002, COURSE CONVEXITY, V54, DOI DOI 10.1101/gr.178756.114
  • [3] Birkhoff's polytope and unistochastic matrices, N=3 and N=4
    Bengtsson, I
    Ericsson, Å
    Kus, M
    Tadej, W
    Zyczkowski, K
    [J]. COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2005, 259 (02) : 307 - 324
  • [4] Brualdi R.A., 2006, ENCY MATH ITS APPL, V108
  • [5] Budnitz M. E., 1997, SC L REV, V49, P847
  • [6] On the volume of the polytope of doubly stochastic matrices
    Chan, CS
    Robbins, DP
    [J]. EXPERIMENTAL MATHEMATICS, 1999, 8 (03) : 291 - 300
  • [7] PRIVACY AND AUTHENTICATION - INTRODUCTION TO CRYPTOGRAPHY
    DIFFIE, W
    HELLMAN, ME
    [J]. PROCEEDINGS OF THE IEEE, 1979, 67 (03) : 397 - 427
  • [8] Practical data-oriented microaggregation for statistical disclosure control
    Domingo-Ferrer, J
    Mateo-Sanz, JM
    [J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2002, 14 (01) : 189 - 201
  • [9] Local Privacy and Statistical Minimax Rates
    Duchi, John C.
    Jordan, Michael I.
    Wainwright, Martin J.
    [J]. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 429 - 438
  • [10] Dwork C., 2011, Differential privacy encyclopedia of cryptography and security, P338, DOI [DOI 10.1007/978-1-4419-5906-5752, 10.1007/978-1-4419-5906-5752]
12