Analysis of singular subspaces under random perturbations

• URL: http://arxiv.org/abs/2403.09170v2
• Date: Wed, 20 Mar 2024 02:22:24 GMT
• Title: Analysis of singular subspaces under random perturbations
• Authors: Ke Wang,
• Abstract summary: We extend the Davis-Kahan-Wedin theorem in a fully generalized manner, applicable to any unitarily invariant matrix norm. We explore the practical implications of these findings, in the context of the Gaussian mixture model and the submatrix localization problem.
• Score: 3.6626323701161665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a comprehensive analysis of singular vector and singular subspace perturbations in the context of the signal plus random Gaussian noise matrix model. Assuming a low-rank signal matrix, we extend the Davis-Kahan-Wedin theorem in a fully generalized manner, applicable to any unitarily invariant matrix norm, extending previous results of O'Rourke, Vu and the author. We also obtain the fine-grained results, which encompass the $\ell_\infty$ analysis of singular vectors, the $\ell_{2, \infty}$ analysis of singular subspaces, as well as the exploration of linear and bilinear functions related to the singular vectors. Moreover, we explore the practical implications of these findings, in the context of the Gaussian mixture model and the submatrix localization problem.

Related papers

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Asymptotic Gaussian Fluctuations of Eigenvectors in Spectral Clustering [24.558241146742205]
  It is shown that the signal $+$ noise structure of a general spike random matrix model is transferred to the eigenvectors of the corresponding Gram kernel matrix. This CLT-like result was the last missing piece to precisely predict the classification performance of spectral clustering.
  arXiv  Detail & Related papers  (2024-02-19T17:25:12Z)
• Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem [0.0]
  We derive simple and explicit formulas for the optimal estimator in the cases of Nuclear and Spectral norms. We analytically derive the generalization error in multiple random matrix ensembles, and compare with Ridge regression.
  arXiv  Detail & Related papers  (2023-11-18T14:45:06Z)
• Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clustering [7.342677574855651]
  The singular subspaces perturbation theory is of fundamental importance in probability and statistics. We consider two arbitrary matrices where one is a leave-one-column-out submatrix of the other one. It is well-suited for mixture models and results in a sharper and finer statistical analysis than classical perturbation bounds such as Wedin's Theorem.
  arXiv  Detail & Related papers  (2022-05-30T05:07:09Z)
• An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings [21.727073594338297]
  This study is motivated by applications in machine learning and statistics. We establish the weak limit of the empirical distribution of these random matrices in a scaling regime. Our results can be characterized as the free additive convolution between a Marchenko-Pastur law and a semicircle law.
  arXiv  Detail & Related papers  (2022-05-12T18:50:21Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  This paper studies asymmetric order-$d$ spiked tensor models with Gaussian noise. We show that the analysis of the considered model boils down to the analysis of an equivalent spiked symmetric textitblock-wise random matrix.
  arXiv  Detail & Related papers  (2021-12-23T04:05:01Z)
• 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)
• Hessian Eigenspectra of More Realistic Nonlinear Models [73.31363313577941]
  We make a emphprecise characterization of the Hessian eigenspectra for a broad family of nonlinear models. Our analysis takes a step forward to identify the origin of many striking features observed in more complex machine learning models.
  arXiv  Detail & Related papers  (2021-03-02T06:59:52Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula) [23.15629681360836]
  We prove an analytical formula for the reconstruction performance of convex generalized linear models. We show that an analytical continuation may be carried out to extend the result to convex (non-strongly) problems. We illustrate our claim with numerical examples on mainstream learning methods.
  arXiv  Detail & Related papers  (2020-06-11T16:26:35Z)

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.