A Framework for Private Matrix Analysis

• URL: http://arxiv.org/abs/2009.02668v1
• Date: Sun, 6 Sep 2020 08:01:59 GMT
• Title: A Framework for Private Matrix Analysis
• Authors: Jalaj Upadhyay, Sarvagya Upadhyay
• Abstract summary: We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis.
• Score: 20.407204637672887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.

Related papers

• Efficient Estimation of Unique Components in Independent Component Analysis by Matrix Representation [1.0282274843007793]
  Independent component analysis (ICA) is a widely used method in various applications of signal processing and feature extraction. In this paper, the unique estimation of ICA is highly accelerated by reformulating the algorithm in matrix representation. Experimental results on artificial datasets and EEG data verified the efficiency of the proposed method.
  arXiv  Detail & Related papers  (2024-08-30T09:01:04Z)
• Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions [7.697455644733554]
  We rank the problem of robust completion matrix (RMC) We consider a simple yet efficient algorithm for the analysis. To the best sampling result, this is the first rank-out analysis method.
  arXiv  Detail & Related papers  (2024-07-28T09:47:36Z)
• The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity [4.523133864190258]
  This paper establishes the analytical expression of the Hessian matrix of the mapping from a (fixed size) collection of $n$ points in the $d$-dimensional decision space to the scalar hypervolume indicator value. The Hessian matrix plays a crucial role in second-order methods, such as the Newton-Raphson optimization method, and it can be used for the verification of local optimal sets.
  arXiv  Detail & Related papers  (2022-11-08T11:24:18Z)
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
  Eigenvector perturbation analysis plays a vital role in various statistical data science applications. We develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural "plug-in" estimator, we develop de-biased estimators.
  arXiv  Detail & Related papers  (2021-04-07T17:55:10Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a by-product online tensorial algorithm that estimates for each independent component.
  arXiv  Detail & Related papers  (2020-12-28T18:52:37Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• A New Basis for Sparse Principal Component Analysis [5.258928416164104]
  Previous versions of sparse principal component analysis presumed that the eigen-basis (a $p times k$ matrix) is approximately sparse. We propose a method that presumes the $p times k$ matrix becomes approximately sparse after a $k times k$ rotation. We show that for the same level of sparsity, the proposed sparse PCA method is more stable and can explain more variance compared to alternative methods.
  arXiv  Detail & Related papers  (2020-07-01T16:32:22Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Information-Theoretic Limits for the Matrix Tensor Product [8.206394018475708]
  This paper studies a high-dimensional inference problem involving the matrix tensor product of random matrices. On the technical side, this paper introduces some new techniques for the analysis of high-dimensional matrix-preserving signals.
  arXiv  Detail & Related papers  (2020-05-22T17:03:48Z)

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.