This paper tackles the challenge of filling in missing entries in large-scale matrices and tensors—a problem central to recommendation systems, network tomography, and genomics. By moving away from passive, random sampling and embracing adaptive sampling, the authors provide new algorithms that are both faster and more robust than the current state-of-the-art.
TL;DR
The authors introduce adaptive sampling algorithms for matrix and tensor completion that achieve exact recovery with fewer samples than traditional methods. Crucially, their approach works even when data is "spiky" (highly coherent) in one dimension, and it offers the first theoretical sample complexity bounds for exact tensor completion.
What Problem Does This Paper Address?
Matrix completion is the task of recovering an entire low-rank matrix from a small subset of its entries (think Netflix predicting movie ratings for all users based on just a few). Standard approaches rely on passive sampling, where entries are chosen at random.
However, passive sampling has a major weakness: it requires "incoherence." Incoherence assumes that the information in the matrix is spread out evenly across all rows and columns. If a matrix is "coherent"—meaning a few rows or columns contain most of the information—random sampling will likely miss the important parts, leading to recovery failure.
This paper asks: If we can choose which entries to reveal based on what we have already learned, can we recover "spiky" matrices more efficiently?
Methods
The authors propose a Sequential/Recursive Completion strategy. The core idea is to build up a "candidate subspace" of the columns.
- Subspace Detection: The algorithm maintains a running estimate of the column space. For each new column (or subtensor), it uses a small number of samples to test if that column already "fits" within the known subspace.
- Adaptive Selection: If a column does not fit the current subspace, the algorithm "samples" that column more heavily (or entirely) to learn the new information it contains and updates the candidate subspace.
- Recursive Tensor Completion: For tensors (multi-dimensional arrays), the algorithm applies this logic recursively. To complete an order-$T$ tensor, it treats it as a collection of order-$(T-1)$ tensors and solves them step-by-step.
- Noisy Matrix Completion: For data with noise, they adapt a "Column Subset Selection" (CSS) algorithm. Instead of processing sequentially, it works in rounds, sampling columns with a probability proportional to how poorly they are represented by the current estimated subspace.
Key Insights and Ideas
- Relaxing Assumptions: The biggest "aha" moment is that adaptivity allows you to completely ignore row-space incoherence. As long as the column space is somewhat spread out, you can find the "important" rows by being smart about your sampling, even if they are very rare.
- Linear Scaling for Tensors: Tensor completion is notoriously difficult (often NP-hard). The authors show that with adaptive sampling, the number of samples needed scales linearly with the dimension $n$, avoiding the "curse of dimensionality" that plagues many tensor methods.
- Efficiency via Subspace Testing: By using a small number of entries to "test" a column before deciding to sample it fully, the algorithm avoids wasting measurements on redundant data.
Key Results
The paper primarily uses synthetic simulations to validate its theoretical bounds across varying matrix sizes ($1000 \times 1000$ to $10000 \times 10000$) and ranks ($r = 10, 50, 100$).
- Sample Complexity: For an $n \times n$ matrix of rank $r$, they achieve exact recovery using $\Omega(nr^{3/2} \log r)$ entries. This is a significant improvement over the best-known passive sampling bounds in certain regimes.
- Speed: In practical tests, the algorithm recovered a $10,000 \times 10,000$ matrix of rank 100 in less than 5 minutes (283 seconds). For comparison, the standard Singular Value Thresholding (SVT) algorithm took nearly 2 hours on the same hardware.
- Robustness to Coherence: In simulations where the row space was made increasingly "spiky," standard semidefinite programming (SDP) methods saw their error rates skyrocket. The authors' adaptive CSS method maintained a near-zero error rate regardless of row-space coherence.
Limitations and Future Work
- Rank Dependence: While the algorithm scales well with $n$, the $r^{3/2}$ dependence on the rank might be pessimistic. The authors' own simulations suggest that the true dependence might be closer to linear ($r$), and they suggest this as a path for future theoretical refinement.
- Column Space Incoherence: While they removed the requirement for row-space incoherence, the algorithm still requires the column space to be incoherent. It is impossible to recover a matrix that is spiky in both dimensions without looking at every single entry.
- Generalization: The authors suggest that future work could explore whether these adaptive strategies can be integrated into the popular nuclear norm minimization framework to provide even stronger theoretical guarantees.
Summary updated