Source-linked AI summary
Low-Rank Matrix and Tensor Completion via Adaptive Sampling
Akshay Krishnamurthy, Aarti Singh
TL;DR
Low-rank matrix and tensor completion traditionally relies on assumptions about how information is distributed across entries, motivating methods that can exploit informative measurements. This paper develops adaptive sampling algorithms that learn useful columns and relaxes row-space incoherence requirements. It establishes exact and noisy recovery guarantees with sample complexities scaling as Ω(nr^3/2 log r), Ω(nr^(T−1/2)T^2 log r), and Ω(nr^3/2 polylog(n)), while leaving tighter rank dependence as an open question.
Problem
Low-rank matrix and tensor completion needs methods that can recover objects when the row space is highly coherent rather than satisfying usual incoherence assumptions.
Method
The paper uses adaptive sampling to identify informative columns for learning the column space, including a noisy matrix algorithm that samples according to projection outside a candidate column space.
Results
The paper proves exact matrix and tensor recovery guarantees and noisy matrix approximation guarantees with sample complexities Ω(nr^3/2 log r), Ω(nr^(T−1/2)T^2 log r), and Ω(nr^3/2 polylog(n)), respectively.
Takeaways & Limitations
The results demonstrate that sequential active algorithms can reduce time and measurement overhead relative to passive algorithms for matrix and tensor completion.
Takeaways & Limitations
The paper leaves open whether the rank dependence can be reduced from r^3/2 to linear and whether nuclear-norm guarantees can be generalized to tensor completion.
Abstract
from arXiv · showhide
We study low rank matrix and tensor completion and propose novel algorithms that employ adaptive sampling schemes to obtain strong performance guarantees. Our algorithms exploit adaptivity to identify entries that are highly informative for learning the column space of the matrix (tensor) and consequently, our results hold even when the row space is highly coherent, in contrast with previous analyses. In the absence of noise, we show that one can exactly recover a $n \times n$ matrix of rank $r$ from merely $Ω(n r^{3/2}\log(r))$ matrix entries. We also show that one can recover an order $T$ tensor using $Ω(n r^{T-1/2}T^2 \log(r))$ entries. For noisy recovery, our algorithm consistently estimates a low rank matrix corrupted with noise using $Ω(n r^{3/2} \textrm{polylog}(n))$ entries. We complement our study with simulations that verify our theory and demonstrate the scalability of our algorithms.
1 Introduction
The paper develops adaptive low-rank completion algorithms motivated by applications where measurements can reveal entire columns. These methods target informative columns to relax row-space incoherence requirements while retaining strong sample-complexity guarantees.
- Motivation: Adaptive sensing is motivated by applications including recommender systems, network tomography, and gene expression analysis, where measurements can be chosen strategically.Network operators can measure full latency columns, while gene-expression studies combine single-entry and whole-column measurements to reduce total cost.
- Approach: The algorithms select a small subset of informative matrix or tensor columns to reconstruct or approximate the underlying object.Adaptivity focuses measurements on columns that are especially useful for learning the column space.
- Contribution: Adaptive sampling removes usual row-space incoherence assumptions while achieving competitive or better sample-complexity bounds.The guarantees concern three low-rank completion problems involving exact and noisy recovery.
- Results: Ω(nr^3/2 log r) adaptively chosen samples suffice for exact rank-r matrix recovery, improving on the passive Ω(nr^2 log^2 n) bound.This is also presented as the first guarantee for matrix completion with coherent row space.
- Results: Ω(nr^(T−1/2)T^2 log r) adaptively chosen samples suffice for recovering an order-T rank-r tensor.The paper also gives a necessary condition under random sampling and establishes exact tensor-completion sample-complexity bounds.
- Results: Ω(nr^3/2 polylog(n)) samples support noisy rank-r matrix approximation without requiring an incoherent row space.Unlike the noiseless streaming algorithm, this noisy procedure cannot process the matrix sequentially.
2 Related Work
Prior work establishes strong passive matrix-completion guarantees under incoherence, while tensor completion has fewer noiseless sample-complexity results. The paper connects adaptive completion to adaptive sensing, matrix approximation, column subset selection, and subspace methods.
- Matrix completion: Passive matrix-completion analyses require incoherence parameters for the row and column spaces and obtain near-optimal random-sampling guarantees.The cited results include sufficient and necessary sample bounds for exact recovery under random sampling.
- Matrix completion: Noisy matrix-completion results likewise quantify how much information a single observation reveals through an incoherence-like parameter.This places the paper’s adaptive approach within a literature focused on informative measurements.
- Tensor completion: Tensor completion is less studied, and prior cited methods do not provide noiseless sample-complexity bounds.The literature also faces computational difficulty because many tensor decompositions are NP-hard to compute.
- Adaptive sensing: Adaptive sparse-vector sensing provides precedent for gains from adaptive sampling, but low-rank completion additionally requires learning an unknown eigenbasis.This distinction couples completion with basis learning.
- Matrix approximation: Nystrom methods and entrywise subsampling address missing-data matrix approximation, with sample-complexity bounds matching those developed here.The cited Nystrom analysis focused on positive-semidefinite matrices.
- Column subset selection: Column subset selection approximates a matrix using a few columns, and the noisy-completion procedure adapts an existing CSS algorithm.Volume sampling and leverage-score sampling are noted as difficult to apply directly to missing-data settings.
- Subspace methods: The techniques also relate to subspace detection and subspace tracking, including prior guarantees for detecting a subspace from partially observed vectors.The paper states that it improves on one subspace-detection result while establishing its completion guarantees.
3 Definitions and Preliminaries
The preliminaries define matrix and tensor representations, subspaces, projections, subsampling, and coherence. The key assumption retains incoherence for the column space while allowing the row space to be coherent.
- Matrix notation: A rank-r matrix M is represented through its singular value decomposition M = UΣV^T, with c1, …, cn2 denoting its columns.These objects establish the notation used for the matrix-completion algorithms.
- Tensor notation: Tensor rank is defined through outer-product representations, while mode-t subtensors are formed by fixing one coordinate of the t-th mode.For an order-3 tensor, these subtensors are frontal slices.
- Subspaces and projections: A d-dimensional subspace is represented by orthonormal basis vectors or a matrix whose columns are those basis vectors.The same framework is extended to tensor subspaces using vectorization.
- Subspaces and projections: The orthogonal projection onto a subspace U is defined as P_Uv = U(U^TU)^−1U^Tv.Subsampling notation indexes vectors and matrix rows lexicographically, and restricted basis matrices need not have orthonormal columns.
- Tensor preliminaries: Tensor projections and subsampling extend the vector definitions using vectorization and the tensor inner product.Tensor subspaces are written as matrices whose columns are vectorized basis elements.
- Coherence assumption: Previous analyses bound both row- and column-space coherence, whereas this paper retains incoherence only for the column space.Adaptive sampling cannot eliminate all assumptions because a rank-one matrix supported on one entry requires observing the entire matrix to identify.
4 Exact Completion Problems
The paper develops adaptive exact-completion algorithms that recursively identify informative columns or subtensors, avoiding incoherence assumptions on the row space. It establishes sample-complexity guarantees for matrices and tensors, compares them with passive sampling, and identifies remaining gaps in tensor rank dependence.
- Adaptive algorithms: Adaptive algorithms build the matrix or tensor column space by testing partially observed columns or subtensors and fully observing informative ones.For matrices, the candidate column space is expanded when a tested column lies outside it; the tensor procedure applies this recursively to mode-T subtensors.
- Comparisons: The adaptive matrix guarantee improves over prior bounds when the rank is small relative to dimension and avoids the Nystrom method’s incoherence requirement on both spaces.Against the cited leverage-sampling result, the improvement applies when √r log r ≤ log^2 n.
- Adaptive algorithms: A subspace-detection result for subsampled vectors is the key proof ingredient enabling the stated sample-complexity bounds.The result improves prior dependence on incoherence parameters and supports testing membership using few samples.
- Lower bounds: Passive tensor sampling has a necessary condition for exact recovery, whereas the adaptive procedure improves on passive procedures in its dependence on tensor dimensions.The lower bound also recovers the known matrix-completion lower bound when T = 2.
5 Noisy Matrix Completion
The noisy matrix completion algorithm adaptively builds a candidate column space by sampling columns according to their unexplained projections, then reconstructs columns from the learned subspace. Under incoherence of the true column space, it provides consistent estimation with a sample complexity scaling as r^{3/2} up to polylogarithmic factors.
- Algorithm: The CSS-based algorithm samples columns with probability proportional to their projection onto the candidate subspace’s orthogonal complement.It observes selected columns fully and adds them to the candidate subspace in successive rounds.
- Algorithm: After learning the subspace, the algorithm estimates each column by projecting its observed entries onto the learned column space.The resulting estimates are concatenated to form the completed matrix.
- Assumptions: The analysis assumes a rank-r signal plus independent Gaussian noise and requires incoherence of the signal’s column space.The incoherence assumption supports estimating column norms and the adaptive sampling probabilities from missing data.
- Guarantee: Ω((n1 + n2)r^{3/2}µ(U)polylog(n1n2)) observations suffice for computing the noisy reconstruction.The theorem considers the subspace obtained after logarithmically many rounds.
- Guarantee: For normalized signal energy and Gaussian noise variance σ2/(n1n2), the theorem gives a constant c⋆ governing the consistency condition.The supplied theorem passage states the normalization and existence of c⋆ but does not include the displayed condition’s remainder.
- Comparison: Compared with prior semidefinite-program results, the method tolerates highly coherent row spaces, although those results can apply with fewer observations in some regimes.For small rank, the paper reports better noise tolerance, while the competing method may use fewer observations.
6 Simulations
Simulations test the noiseless algorithm’s scaling with matrix size and rank, compare it with SVT, evaluate noisy recovery under row-space coherence, and demonstrate large-scale computational performance. The experiments broadly support the claimed sampling and scalability behavior.
- Noiseless matrix completion: For fixed rank and incoherent column space, success curves indicate that the noiseless algorithm can use a decreasing fraction of entries per column as n increases.Curves plotted against total samples per column coincide, supporting linear dependence on n.
- Noiseless matrix completion: SVT does not show the same linear dependence on n and exhibits the logarithmic dependence expected for passive completion.The paper reports empirically better performance for the proposed algorithm in this comparison.
- Rank dependence: For 500 × 500 matrices, success improves when the sampling probability is rescaled by r^-1, matching the paper’s conjectured rank dependence more closely than r^-3/2.The r^-1 curves line up empirically, while the r^-3/2 rescaling is the theorem-based comparison.
- Scalability: The proposed algorithm recovers a 10000 × 10000 rank-100 matrix in less than 5 minutes, compared with close to 2 hours for SVT.These timings are cited as an example of the computational comparison with SVT.
- Noisy matrix completion: With matched observation counts, the noisy algorithm’s performance is unaffected as row-space coherence increases, whereas the competing semidefinite program deteriorates.Figure 2 plots reconstruction error against row-space coherence for both methods.
7 Conclusions and Open Problems
The paper concludes that sequential active sampling can improve time and measurement overhead for matrix and tensor completion. It leaves tighter rank dependence and tensor analogues of nuclear-norm methods as open problems.
- Conclusion: Sequential active algorithms can offer significant improvements in time and measurement overhead over passive algorithms for matrix and tensor completion.The authors present this as the central conclusion of the work.
- Open problems: The rank dependence remains an open question, particularly whether the current r^{3/2} dependence can be reduced to linear.Simulations suggest that such an improvement may be possible.
- Open problems: A theoretical generalization of nuclear norm minimization to tensor completion is another direction identified for future work.The authors seek guarantees on sample complexity for such a tensor method.
A Proof of Corollary 3
The proof identifies unseen directions in the column space using projected subsampled columns, then uses successful tests and invertibility to recover the column space and reconstruct all columns. The resulting procedure has the stated exact-recovery guarantee with controlled failure probability and runtime.
- Subspace identification: If a column lies outside the current candidate subspace, at least 36r^{3/2}µ0 log(2r/δ) samples distinguish it with probability at least 1 − 4δ.Columns already in the candidate subspace produce zero projected residual deterministically.
- Subspace identification: The algorithm stops further sampling columns whose projected residual is zero and verifies their exact recoverability through an invertibility condition.The relevant Gram matrix is invertible except with the stated failure probability.
- Failure probability: Because rank(M) ≤ r, at most r columns require nonzero projection tests, so a union bound makes all tests succeed with probability at least 1 − 4rδ.This yields the exact candidate subspace at the end of the algorithm.
- Reconstruction: Once the column space is recovered, each column is reconstructed through a determined linear system based on observed entries.The proof represents columns in the recovered subspace and solves for their coefficients.
- Runtime: The dominant per-column work is projection and reconstruction, yielding total runtime O(n1n2r) apart from lower-order recomputation and Gram–Schmidt costs.The proof separately accounts for O(r^3m) recomputation and O(n1r^2) orthogonalization.
B Proof of Theorem 2
The tensor proof inductively controls recovery failure and sample complexity across tensor orders, then derives the resulting computational cost.
- Failure probability: The proof bounds tensor-recovery failure inductively across subtensors and projection tests.Projection tests identify informative subtensors with probability at least 1 − 4δ, while recursion accumulates lower-order recovery failures.
- Failure probability: τ1 = 0 because any one-mode tensor is completely observed.
- Sample complexity: mT is computed inductively from the base case m1 = n1 and per-order sampling requirements.The proof explicitly introduces mT as the number of samples needed to complete an order-T tensor.
- Computational cost: The total running time aggregates projection, reconstruction, and matrix-inversion costs over recursively completed subtensors.At most r order-(T − 1) subtensors are completed, and the inversion cost is dominated by the other terms.
- Computational cost: The computational bound follows after substituting mi = ˜O(r^2(i−1)), which makes the second-sum terms ˜O(r^(T+t+1)).The resulting sum is ˜O(r^(2T+1)).
C Proof of Theorem 6
The proof establishes noisy matrix recovery by analyzing adaptive subspace sampling, controlling incoherence and projection errors, and summing the resulting sample requirements.
- Noisy matrix recovery: Theorem 8 analyzes a rank-r matrix A corrupted by Gaussian noise and defines Mr as the best rank-r approximation to M.
- Sample complexity: The total sample complexity combines the adaptive rounds with Ω(L^2r/(δϵ)) completely observed columns and has failure probability at most 7δ.
- Adaptive sampling: Adaptive sampling estimates informative columns using sampling probabilities derived from residual projections onto the current subspace complement.The method samples columns according to an estimated distribution and bounds the resulting projection error.
- Adaptive sampling: The analysis chains single-round sampling guarantees across L rounds using induction and a union bound.Each round is assigned failure probability δ/L, yielding total failure probability at most δ for the chained argument.
- Incoherence control: Bernstein-based concentration controls the incoherence of projected columns and algorithmic subspaces throughout execution.The bounds scale as O(rµ(U) log(n1n2L/δ)) for projected columns and O(µ(U) log(n1L/δ)) for subspaces.
- Recovery guarantee: The algorithm reconstructs columns from partial observations using an invertible projected system, adding 2δ to the total failure probability.The resulting approximation error is bounded by a constant-factor term, with the relevant expression below 5/4 under the chosen sample size.
D Proof of Theorem 5
The proof uses block-diagonal constructions to establish a necessary sampling condition and develops incoherence bounds for tensor subspaces and Gaussian perturbations.
- Proof strategy: The matrix proof works in the Bernoulli sampling model and adapts the Candes–Tao argument before extending it to tensors.
- Matrix construction: The constructed block-diagonal matrices have incoherent column and row spaces with parameter µ0.The row-space incoherence follows from a calculation analogous to that for the column space.
- Necessary condition: Unique identification requires at least one observed entry from every row of every diagonal block.Otherwise, an unobserved coordinate can vary while preserving the observed entries, rank, and incoherence constraints.
- Tensor construction: The tensor construction extends the block-diagonal argument, with each tensor-block row containing a product of the other mode sizes in entries.This changes the unsampled-row probability and yields the tensor necessary condition.
- Incoherence analysis: The proof bounds incoherence for tensor-product subspaces by combining the incoherence of their constituent mode subspaces.It also analyzes projected Gaussian components and tracks incoherence across algorithmic rounds.
F.1 Proof of Theorem 4
Theorem 4 improves concentration guarantees for sampling from an incoherent subspace by replacing weaker dependence on coherence with Bernstein-based bounds.
- Concentration improvement: The proof improves prior results by using Bernstein’s inequality in the concentration arguments.The stated improvement carries into the sample-complexity guarantees.
- Concentration improvement: The revised bound changes the dependence between m and µ(v) from µ(v)^2/m to µ(v)/m.
- Probability control: The analysis applies Bernstein’s inequality and a union bound to obtain probability at least 1 − δ for the sampling estimate.
- Recovery role: The projection matrices must remain invertible under missing observations so columns can be reconstructed from partial samples.
- Recovery role: The theorem’s bounds require γ < 1, with the corresponding upper and lower bounds derived from the same subspace decomposition.