Streaming principal component analysis from incomplete data
From MaRDI portal
Abstract: Linear subspace models are pervasive in computational sciences and particularly used for large datasets which are often incomplete due to privacy issues or sampling constraints. Therefore, a critical problem is developing an efficient algorithm for detecting low-dimensional linear structure from incomplete data efficiently, in terms of both computational complexity and storage. In this paper we propose a streaming subspace estimation algorithm called Subspace Navigation via Interpolation from Partial Entries (SNIPE) that efficiently processes blocks of incomplete data to estimate the underlying subspace model. In every iteration, SNIPE finds the subspace that best fits the new data block but remains close to the previous estimate. We show that SNIPE is a streaming solver for the underlying nonconvex matrix completion problem, that it converges globally to a stationary point of this program regardless of initialization, and that the convergence is locally linear with high probability. We also find that SNIPE shows state-of-the-art performance in our numerical simulations.
Recommendations
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Nearly optimal stochastic approximation for online principal subspace estimation
- scientific article; zbMATH DE number 2045498
- Robust PCA and subspace tracking from incomplete observations using \(\ell _0\)-surrogates
- A subspace-approximating algorithm for matrix completion
Cites work
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- High-dimensional covariance matrix estimation with missing observations
- How close is the sample covariance matrix to the actual covariance matrix?
- scientific article; zbMATH DE number 1090982 (Why is no real title available?)
- scientific article; zbMATH DE number 2045498 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Incoherence-Optimal Matrix Completion
- Local convergence of an algorithm for subspace identification from partial data
- MC2: a two-phase algorithm for leveraged matrix completion
- Normalized iterative hard thresholding for matrix completion
- On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix
- Perturbation bounds in connection with singular value decomposition
- PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares From Partial Observations
- Probability. Theory and examples.
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
- Subspace learning with partial information
- The elements of statistical learning. Data mining, inference, and prediction
- Updating the singular value decomposition
- User-friendly tail bounds for sums of random matrices
- Weighted Matrix Completion and Recovery With Prior Subspace Information
Cited in
(3)
This page was built for publication: Streaming principal component analysis from incomplete data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214169)
