On the Power of Adaptivity in Matrix Completion and Approximation

Abstract

We consider the related tasks of matrix completion and matrix approximation from missing data and propose adaptive sampling procedures for both problems. We show that adaptive sampling allows one to eliminate standard incoherence assumptions on the matrix row space that are necessary for passive sampling procedures. For exact recovery of a low-rank matrix, our algorithm judiciously selects a few columns to observe in full and, with few additional measurements, projects the remaining columns onto their span. This algorithm exactly recovers an $n\times n$ rank $r$ matrix using $O(nr{\mu }_0{\log }^2(r))$ observations, where ${\mu }_0$ is a coherence parameter on the column space of the matrix. In addition to completely eliminating any row space assumptions that have pervaded the literature, this algorithm enjoys a better sample complexity than any existing matrix completion algorithm. To certify that this improvement is due to adaptive sampling, we establish that row space coherence is necessary for passive sampling algorithms to achieve non-trivial sample complexity bounds. For constructing a low-rank approximation to a high-rank input matrix, we propose a simple algorithm that thresholds the singular values of a zero-filled version of the input matrix. The algorithm computes an approximation that is nearly as good as the best rank-$r$ approximation using $O(nr\mu {\log }^2(n))$ samples, where $\mu$ is a slightly different coherence parameter on the matrix columns. Again we eliminate assumptions on the row space.

References in corpus (6)

• A Simpler Approach to Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Incoherence-Optimal Matrix Completion
• Near-Optimal Column-Based Matrix Reconstruction
• The spectral norm error of the naive Nystrom extension
• Adaptive Sensing for Estimation of Structured Sparse Signals

Cited by in corpus (9)

• Adaptive Sampling of RF Fingerprints for Fine-grained Indoor Localization
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Matrix Completion from Non-Uniformly Sampled Entries
• Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• NoisyCUR: An algorithm for two-cost budgeted matrix completion