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
- A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
We propose a framework for the analysis of the low-rank approximation error in Frobenius norm for centered and non-standard matrices.
Under minimal assumptions, we derive accurate bounds in expectation and probability.
Our bounds have clear interpretations that enable us to derive properties and motivate practical choices.
arXiv Detail & Related papers (2024-05-08T04:51:56Z) - 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) - An $\ell_p$ theory of PCA and spectral clustering [23.90245234027558]
Principal Component Analysis is a powerful tool in statistics and machine learning.
In this paper, we develop an $ell_p$ theory for a hollowed version of PCA in Hilbert spaces.
For contextual community detection, the $ell_p$ theory leads to a simple spectral algorithm that achieves the information threshold for exact recovery.
arXiv Detail & Related papers (2020-06-24T21:30:28Z) - 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.