ABSTRACT
This work is at theintersection of two lines of research. One line, initiated by Dinurand Nissim, investigates the price, in accuracy, of protecting privacy in a statistical database. The second, growing from an extensive literature on compressed sensing (see in particular the work of Donoho and collaborators [4,7,13,11])and explicitly connected to error-correcting codes by Candès and Tao ([4]; see also [5,3]), is in the use of linearprogramming for error correction.
Our principal result is the discovery of a sharp threshhold ρ*∠ 0.239, so that if ρ < ρ* and A is a random m x n encoding matrix of independently chosen standardGaussians, where m = O(n), then with overwhelming probability overchoice of A, for all x ∈ Rn, LP decoding corrects ⌊ ρ m⌋ arbitrary errors in the encoding Ax, while decoding can be made to fail if the error rate exceeds ρ*. Our boundresolves an open question of Candès, Rudelson, Tao, and Vershyin [3] and (oddly, but explicably) refutesempirical conclusions of Donoho [11] and Candès et al [3]. By scaling and rounding we can easilytransform these results to obtain polynomial-time decodable random linear codes with polynomial-sized alphabets tolerating any ρ < ρ* ∠ 0.239 fraction of arbitrary errors.
In the context of privacy-preserving datamining our results say thatany privacy mechanism, interactive or non-interactive, providingreasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.
- D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci., 66(4):671--687, 2003. Google ScholarDigital Library
- A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the sulq framework. In C. Li, editor, PODS, pages 128--138. ACM, 2005. Google ScholarDigital Library
- E.J. Candès, M. Rudelson, T. Tao, and R. Vershynin. Error correction via linear programming. In FOCS, pages 295--308. IEEE Computer Society, 2005.Google ScholarCross Ref
- E.J. Candès and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203--4215, 2005. Google ScholarDigital Library
- E.J. Candès and T. Tao. Error correction via linear programming, 2005.Google Scholar
- E.J. Candès and PRandall. Highly robust error correction by convex programming. Submitted, 2006.Google Scholar
- S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM J. Sci Comp, 48(1):33--61, 1999. Google ScholarDigital Library
- I. Dinur, C. Dwork, and K. Nissim. Privacy in public databases: A foundational approach, 2005. Manuscript.Google Scholar
- I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS, pages 202--210. ACM, 2003. Google ScholarDigital Library
- D. Donoho. For most large underdetermined systems of linear equations, the minimal 11-norm near-solution approximates the sparsest near-solution. Communications on Pure and Applied Mathematics, 59(7):907--934, 2006.Google ScholarCross Ref
- D. Donoho. For most large underdetermined systems of linear equations, the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6):797--829, 2006.Google ScholarCross Ref
- D. Donoho. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete and Computational Geometry, 35(4):617--652, 2006.Google ScholarDigital Library
- D. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Transactions on Information Theory, 48:2845--2862, 2001. Google ScholarDigital Library
- D. Donoho and I.M. Johnstone. Minimax estimation via wavelet shrinkage. Annals of Statistics, 26(3):879--921, 1998.Google ScholarCross Ref
- D. Donoho and J. Tanner. Thresholds for the recovery of sparse solutions via l1 minimization. In Proceedings of the Conference on Information Sciences and Systems, 2006.Google ScholarCross Ref
- D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289--1306, 2006. Google ScholarDigital Library
- C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, TCC, volume 3876 of Lecture Notes in Computer Science, pages 265--284. Springer, 2006. Google ScholarDigital Library
- C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In M.K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 528--544. Springer, 2004.Google Scholar
- J. Feldman. Decoding error-correcting codes via linear programming. Master's thesis, Massachusetts Institute of Technology, 2003. Google ScholarDigital Library
- J. Feldman and D. Karger. Decoding turbo-like codes via linear programming. Journal of Computer and System Sciences, 68(4):733--752, 2004. Google ScholarDigital Library
- J. Feldman, T. Malkin, C. Stein, R. Servedio, and M. Wainwright. LP decoding corrects a constant fraction of errors (an expanded version). In ISIT, pages 68--. IEEE, 2004. Google ScholarDigital Library
- J. Feldman and C. Stein. LP decoding achieves capacity. In SODA, pages 460--469. SIAM, 2005. Google ScholarDigital Library
- L. Goldstein. l1 bounds in normal approximation. Annals of Probability, 2006. To Appear.Google Scholar
- M. Ledoux. The Concentration of Measure Phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, 2001.Google Scholar
- M. Talagrand. Concentration of measure and isoperimetric inequalities in product space. Publ. Math. I.H.E.S., 81:73--205, 1995.Google ScholarCross Ref
Index Terms
- The price of privacy and the limits of LP decoding
Recommendations
Dequantizing compressed sensing with non-Gaussian constraints
ICIP'09: Proceedings of the 16th IEEE international conference on Image processingIn this paper, following the Compressed Sensing (CS) paradigm, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis ...
Block-sparse signals: uncertainty relations and efficient recovery
We consider efficient methods for the recovery of block-sparse signals--i.e., sparse signals that have nonzero entries occurring in clusters--from an underdetermined system of linear equations. An uncertainty relation for block-sparse signals is derived,...
Message passing algorithms and improved LP decoding
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingLinear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance --coming close to that of iterative decoding ...
Comments