Research map / Learning theory and algorithms / Matrix and tensor methods
Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a noise-dependent residual threshold for deciding whether to add a fully observed column to the basis | Adaptive life-long matrix completion · Bounded deterministic noise | per-column ℓ2 recovery error: \mathcal{O}\left(\frac{m}{d}\sqrt{k\epsilon_{noise}}\right) | Helped |
| Use zero-threshold residual testing and remove dictionary vectors whose representation coefficient is always zero | Adaptive life-long matrix completion · Sparse random noise | total sample complexity: \mathcal{O}\left(\mu_0nr\log (r/\delta)\right) | Helped |
| Use sparse linear-combination testing for columns from a mixture of subspaces | Adaptive life-long matrix completion · Mixture of subspaces | total sample complexity: c\mu_\tau \tau^2 n\log\left(r/\delta\right) | Helped |
| Replace prior adaptive sampling with the proposed adaptive sampling method | Noiseless life-long matrix completion · Noiseless matrix completion | total sample complexity: \mathcal{O}\left(\mu_0nr\log^2 (r/\delta)\right) -> \mathcal{O}\left(\mu_0nr\log (r/\delta)\right) | Helped |
| Replace prior passive sampling with the proposed adaptive sampling method | Noiseless life-long matrix completion · Noiseless matrix completion | total sample complexity: \mathcal{O}\left(\mu_0nr\log^2 (n/\delta)\right) -> \mathcal{O}\left(\mu_0nr\log (r/\delta)\right) | Helped |
| Use sparse-subspace structure rather than a single-subspace representation | Adaptive life-long matrix completion · Mixture of subspaces | total sample complexity: \mathcal{O}(\mu_0 nr\log(r/\delta)) -> c\mu_\tau \tau^2 n\log\left(r/\delta\right) | Helped |
Closest papers by meaning
- Generalization Bounds for Inductive Matrix Completion in Low-Noise Settings (AAAI 2023 · similarity 0.90)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.90)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.89)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.88)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.88)
- A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.