Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics

• URL: http://arxiv.org/abs/2203.10262v1
• Date: Sat, 19 Mar 2022 07:26:45 GMT
• Title: Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics
• Authors: Yichi Zhang and Minh Tang
• Abstract summary: We study the statistical properties of RSVD under a general "signal-plus-noise" framework. We derive nearly-optimal performance guarantees for RSVD when applied to three statistical inference problems.
• Score: 8.90202564665576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized singular value decomposition (RSVD) is a class of computationally efficient algorithms for computing the truncated SVD of large data matrices. Given a $n \times n$ symmetric matrix $\mathbf{M}$, the prototypical RSVD algorithm outputs an approximation of the $k$ leading singular vectors of $\mathbf{M}$ by computing the SVD of $\mathbf{M}^{g} \mathbf{G}$; here $g \geq 1$ is an integer and $\mathbf{G} \in \mathbb{R}^{n \times k}$ is a random Gaussian sketching matrix. In this paper we study the statistical properties of RSVD under a general "signal-plus-noise" framework, i.e., the observed matrix $\hat{\mathbf{M}}$ is assumed to be an additive perturbation of some true but unknown signal matrix $\mathbf{M}$. We first derive upper bounds for the $\ell_2$ (spectral norm) and $\ell_{2\to\infty}$ (maximum row-wise $\ell_2$ norm) distances between the approximate singular vectors of $\hat{\mathbf{M}}$ and the true singular vectors of the signal matrix $\mathbf{M}$. These upper bounds depend on the signal-to-noise ratio (SNR) and the number of power iterations $g$. A phase transition phenomenon is observed in which a smaller SNR requires larger values of $g$ to guarantee convergence of the $\ell_2$ and $\ell_{2\to\infty}$ distances. We also show that the thresholds for $g$ where these phase transitions occur are sharp whenever the noise matrices satisfy a certain trace growth condition. Finally, we derive normal approximations for the row-wise fluctuations of the approximate singular vectors and the entrywise fluctuations of the approximate matrix. We illustrate our theoretical results by deriving nearly-optimal performance guarantees for RSVD when applied to three statistical inference problems, namely, community detection, matrix completion, and principal component analysis with missing data.

Related papers

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• On the computational and statistical complexity of over-parameterized matrix sensing [30.785670369640872]
  We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method. By decomposing the factorized matrix $mathbfF$ into separate column spaces, we show that $|mathbfF_t - mathbfF_t - mathbfX*|_F2$ converges to a statistical error.
  arXiv  Detail & Related papers  (2021-01-27T04:23:49Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Phase retrieval in high dimensions: Statistical and computational phase transitions [27.437775143419987]
  We consider the problem of reconstructing a $mathbfXstar$ from $m$ (possibly noisy) observations. In particular, the information-theoretic transition to perfect recovery for full-rank matrices appears at $alpha=1$ and $alpha=2$. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval.
  arXiv  Detail & Related papers  (2020-06-09T13:03:29Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

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.