High-Performance Privacy-Preserving Matrix Completion for Trajectory Recovery

• URL: http://arxiv.org/abs/2405.05789v1
• Date: Thu, 9 May 2024 14:12:41 GMT
• Title: High-Performance Privacy-Preserving Matrix Completion for Trajectory Recovery
• Authors: Jiahao Guo, An-Bao Xu,
• Abstract summary: We propose a high-performance method for privacy-preserving matrix completion. The results of numerical experiments reveal that the proposed method is faster than other algorithms.
• Score: 0.897780713904412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matrix completion has important applications in trajectory recovery and mobile social networks. However, sending raw data containing personal, sensitive information to cloud computing nodes may lead to privacy exposure issue.The privacy-preserving matrix completion is a useful approach to perform matrix completion while preserving privacy. In this paper, we propose a high-performance method for privacy-preserving matrix completion. First,we use a lightweight encryption scheme to encrypt the raw data and then perform matrix completion using alternating direction method of multipliers (ADMM). Then,the complemented matrix is decrypted and compared with the original matrix to calculate the error. This method has faster speed with higher accuracy. The results of numerical experiments reveal that the proposed method is faster than other algorithms.

Related papers

• Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption [0.0]
  Plaintext-ciphertext matrix multiplication is an indispensable tool in privacy-preserving computations. We propose an efficient PC-MM from unpacked additively homomorphic encryption schemes. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths.
  arXiv  Detail & Related papers  (2025-04-20T05:28:46Z)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems. We show that under standard cryptographic assumptions, we can design algorithms that are determinantally faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• Encrypted system identification as-a-service via reliable encrypted matrix inversion [0.0]
  Encrypted computation opens up promising avenues across a plethora of application domains. In particular, Arithmetic homomorphic encryption is a natural fit for cloud-based computational services. This paper presents an encrypted system identification service enabled by a reliable encrypted solution to at least squares problems.
  arXiv  Detail & Related papers  (2024-10-27T20:00:04Z)
• Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms [19.543681023903456]
  We formulate Minimum Bayes Risk (MBR) decoding as a matrix completion problem. We exploit this by only computing a random subset of the scores and efficiently recover the missing entries in the matrix. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations.
  arXiv  Detail & Related papers  (2024-06-05T00:54:03Z)
• HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption [4.164336621664897]
  HETAL is an efficient Homomorphic Encryption based Transfer Learning algorithm. We propose an encrypted matrix multiplication algorithm, which is 1.8 to 323 times faster than prior methods. Experiments show total training times of 567-3442 seconds, which is less than an hour.
  arXiv  Detail & Related papers  (2024-03-21T03:47:26Z)
• Fast Dual-Regularized Autoencoder for Sparse Biological Data [65.268245109828]
  We develop a shallow autoencoder for the dual neighborhood-regularized matrix completion problem. We demonstrate the speed and accuracy advantage of our approach over the existing state-of-the-art in predicting drug-target interactions and drug-disease associations.
  arXiv  Detail & Related papers  (2024-01-30T01:28:48Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Partial Matrix Completion [29.68420094716923]
  This work establishes a new framework of partial matrix completion. The goal is to identify a large subset of the entries that can be completed with high confidence. We propose an efficient algorithm with the following provable guarantees.
  arXiv  Detail & Related papers  (2022-08-25T12:47:20Z)
• Survey of Matrix Completion Algorithms [3.42658286826597]
  Matrix completion problem has been investigated under many different conditions since Netflix announced the Netflix Prize problem. We are going to visit some of the matrix completion methods, mainly in the direction of passive and adaptive directions.
  arXiv  Detail & Related papers  (2022-04-01T05:44:47Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)
• Projection & Probability-Driven Black-Box Attack [205.9923346080908]
  Existing black-box attacks suffer from the need for excessive queries in the high-dimensional space. We propose Projection & Probability-driven Black-box Attack (PPBA) to tackle this problem. Our method requires at most 24% fewer queries with a higher attack success rate compared with state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-05-08T03:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.