Finite Sample Guarantees for PCA in Non-Isotropic and Data-Dependent Noise
This work obtains novel finite sample guarantees for Principal Component Analysis (PCA). These hold even when the corrupting noise is non-isotropic, and a part (or all of it) is data-dependent. Because of the latter, in general, the noise and the true data are correlated. The results in this work are a significant improvement over those given in our earlier work where this "correlated-PCA" problem was first studied. In fact, in certain regimes, our results imply that the sample complexity required to achieve subspace recovery error that is a constant fraction of the noise level is near-optimal. Useful corollaries of our result include guarantees for PCA in sparse data-dependent noise and for PCA with missing data. An important application of the former is in proving correctness of the subspace update step of a popular online algorithm for dynamic robust PCA.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Learning Polyhedral Conformal Sets for Robust Optimization
Robust optimization (RO) provides a principled framework for decision-making under uncertainty, but its performance critically depends on the choice of the uncertainty set. While large sets ensure reliability, they often…
PAC-Bayes Learning Bounds for Sample-Dependent Priors
We present a series of new PAC-Bayes learning guarantees for randomized algorithms with sample-dependent priors. Our most general bounds make no assumption on the priors and are given in terms of certain covering numbers…
SensitivityTriangular Flows for Generative Modeling: Statistical Consistency, Smoothness Classes, and Fast Rates
Triangular flows, also known as Kn\"{o}the-Rosenblatt measure couplings, comprise an important building block of normalizing flow models for generative modeling and density estimation, including popular autoregressive fl…
Density EstimationCovariance estimation using Markov chain Monte Carlo
We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when $\pi$ satisfies a Poincar\'e inequality and the chain possesses a sp…
Anisotropic mesh adaptation for region-based segmentation accounting for image spatial information
A finite element-based image segmentation strategy enhanced by an anisotropic mesh adaptation procedure is presented. The methodology relies on a split Bregman algorithm for the minimisation of a region-based energy func…
Image SegmentationSemantic Segmentation