Source-linked AI summary
Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
Amit Singer, Mihai Cucuringu
TL;DR
Low-rank matrix completion asks when missing entries are uniquely determined from a partial observation pattern. The paper transfers rigidity-theoretic ideas, replacing distances with inner products and introducing completion and stress matrices for randomized local and global uniqueness tests. It concludes that these tools enable fast property testing without actually completing the matrix, while exact combinatorial characterizations remain unavailable in higher dimensions.
Problem
The paper addresses how to determine uniqueness of low-rank matrix completions for partial, potentially non-random observation patterns.
Method
It adapts rigidity theory by using completion and stress matrices, with randomized rank-based algorithms for local and global completion testing.
Results
The resulting algorithms test whether a unique rank-d completion is possible without attempting to recover the missing entries.
Takeaways & Limitations
Rigidity-theoretic tools provide fast tests for generic local and global completion properties of partially observed matrices.
Takeaways & Limitations
Exact combinatorial characterizations of local and global completion for rank-d matrices with d ≥3 remain unavailable.
Abstract
from arXiv · showhide
The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision and control. Most recent work had been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic point of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to an efficient randomized algorithm for testing both local and global unique completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix.
1. Introduction.
Low-rank matrix completion asks whether missing entries can be uniquely inferred under a rank constraint, especially for structured, non-random observation patterns. The paper adapts rigidity-theoretic ideas to develop randomized tests for unique completion without actually filling the matrix.
- Motivation: Low-rank completion arises in collaborative filtering, computer vision, data analysis, machine learning, and control through factor-model data.The motivating example is inferring unrated movie preferences from a partially observed user-rating matrix.
- Motivation: Structured missing-entry patterns require testing whether a rank-d completion is unique before applying existing completion algorithms.This addresses cases where prior results for random patterns do not directly apply.
- Contribution: The proposed randomized algorithm determines whether a specified-rank unique completion is possible rather than computing the missing entries.It builds on rigidity theory and distinguishes local from global completion.
- Contribution: The completion matrix plays the role of the rigidity matrix, linking its rank to infinitesimal completion and enabling efficient rank tests for large sparse instances.Iterative methods such as LSQR can determine the rank when the completion matrix is large and sparse.
2. Rigidity theory: basic definitions and results.
Rigidity theory studies when partial distances uniquely determine a point configuration, using infinitesimal motions and matrix-rank conditions to characterize local and global rigidity. Its framework includes genericity, combinatorial criteria, randomized rank tests, and stress-matrix certificates.
- Basic definitions: The rigidity matrix encodes infinitesimal motions preserving observed distances as a linear system, while trivial motions arise from translations and orthogonal transformations.Infinitesimal rigidity holds when all solutions are trivial; local rigidity instead excludes continuous distance-preserving deformations nearby.
- Generic rigidity: For generic frameworks, local rigidity is a graph property and can be tested by randomizing point coordinates and checking the rigidity-matrix rank.The randomized rank agrees with the rank at the unknown generic realization with probability one.
- Combinatorial rigidity: In two dimensions, Laman’s theorem characterizes generic minimal rigidity using 2n −3 edges and the corresponding sparsity condition on every subgraph.The pebble-game algorithm tests this characterization in at most O(n^2) steps.
- Global rigidity: Generic global rigidity requires vertex (d + 1)-connectivity and redundant rigidity, but these necessary conditions are not sufficient in every dimension.They are sufficient on the line and in the plane, whereas K5,5 in 3D provides a counterexample.
- Global rigidity: Stress matrices provide the central global-rigidity certificate: generic global rigidity is equivalent, apart from simplices, to an equilibrium stress matrix of rank n −(d + 1).The two cited theorems give the sufficient and necessary directions of this characterization.
3. Gram matrices.
The Gram-matrix case models observed inner products as a graph-constrained completion problem and adapts rigidity theory to test local and global uniqueness. A sparse completion matrix captures infinitesimal motions, while randomized rank and stress computations yield scalable tests.
- 3. Gram matrices.: The observed entries define a graph, including possible self-loops for known diagonal elements, and the goal is unique rank-d completion of the Gram matrix.A Gram matrix has entries J_ij = p_i · p_j and can be represented as J = P^T P.
- 3.1. The completion matrix and local completion.: The completion matrix C_G(p) encodes linearized inner-product-preserving motions, with sparsity determined by the graph and values determined by the realization.It has m rows, dn columns, and 2d nonzero elements per row.
- 3.1. The completion matrix and local completion.: A null space larger than d(d − 1)/2 signals non-trivial infinitesimal motions and therefore failure of generic local completion.Randomizing the realization gives, with probability one, the same relevant completion-matrix rank as the true realization.
- 3.1. The completion matrix and local completion.: The local-completion test randomizes a realization, constructs C_G(p), and checks for non-trivial infinitesimal motions using rank or iterative linear-algebra methods.The rank threshold is dn − d(d − 1)/2; sparse factorizations and LSQR support larger problems than full SVD.
- 3.1. The completion matrix and local completion.: Iterative testing can fail when arbitrarily small singular values interact with a preset tolerance, although such values were rare in moderate-size experiments.The authors identify preconditioner design as a direction for future work.
- 3.2. Global completion and stress matrices.: Global completion testing builds a stress matrix from a completion stress vector and checks whether its null space exceeds the trivial dimension.The stress-matrix approach underlies a randomized scalable algorithm for global completion.
4. General rectangular low rank matrices.
For general rectangular low-rank matrices, observed inner products form a bipartite graph and infinitesimal deformations are analyzed with a sparse completion matrix. Local tests use a d^2-dimensional trivial-motion threshold, while global tests use completion stresses and a stress-matrix null-space criterion.
- 4. General rectangular low rank matrices.: A rank-d rectangular matrix factors as X = UV^T, and its observed entries define a bipartite graph because only cross-factor inner products are observed.The decomposition is invariant under invertible changes of coordinates in R^d.
- 4. General rectangular low rank matrices.: The rectangular completion matrix has m rows, d(n1 + n2) columns, and only 2d nonzero elements per row, encoding observed inner-product constraints.Differentiating the observed products yields equations for the unknown velocities of the two factor sets.
- 4. General rectangular low rank matrices.: Local completion requires a null space of dimension d^2; a larger null space indicates non-trivial deformations preserving all observed entries.The d^2 trivial motions arise from invertible linear transformations acting oppositely on the two factors.
- 4. General rectangular low rank matrices.: The randomized local-completion algorithm constructs C_G(u,v) from a random realization and tests whether non-trivial infinitesimal motions exist.The procedure parallels the Gram-matrix algorithm and declares local completion when no such motion is found.
- 4. General rectangular low rank matrices.: Global completion first verifies local completion, then constructs a random left-null-space stress and rearranges it into a symmetric completion stress matrix.The stress matrix has a null space of dimension at least 2d; a larger null space indicates failure of global completion.
5. Combinatorial approach for local and global completion.
The paper derives combinatorial conditions for local and global low-rank completion, with exact characterizations in one dimension and necessary conditions in higher dimensions.
- Exact combinatorial characterizations for rank-d completion when d≥3 are considered out of reach, so the paper restricts attention to rank-1 and rank-2 cases and necessary conditions for higher dimensions.The authors emphasize that higher-dimensional results provide necessary conditions rather than complete characterizations.
- Gram matrix completion: A locally completable Gram rank-d matrix contains a spanning graph with dn−d(d−1)/2 edges and no n′-vertex subgraph exceeding dn′−d(d−1)/2 edges.The edge bound follows from independence of the completion constraints and applies to every submatrix with d≤n′≤n.
- Rank-1 Gram completion: In one dimension, a minimally Gram locally completable graph is exactly a collection of components, each consisting of a tree plus one edge forming an odd cycle.Even cycles create a linear dependence among the completion equations, while odd cycles yield only the trivial infinitesimal motion.
- Rank-1 Gram completion: In one dimension, a minimally Gram globally completable graph is exactly a single tree plus one edge forming an odd cycle.Global completion additionally requires connectivity, and the odd-cycle structure determines magnitudes and signs up to overall negation.
- Rank-1 rectangular completion: For general rectangular rank-1 matrices, forests characterize minimal local completion, whereas trees characterize minimal global completion.The rectangular case uses bipartite graphs and has different degrees-of-freedom counts from the Gram case.
- Scope and limitations: The one-dimensional completion conditions are weaker than rigidity conditions, while rank-2 combinatorial characterizations are posed as an open direction.The paper contrasts completion with one-dimensional rigidity and speculates about sparse-graph characterizations for rank-2 matrices.
6. Numerical Simulations.
The simulations estimate local and global completion thresholds for random rank-d Gram and rectangular matrices, using logistic regression to study their asymptotic behavior. They also examine algorithm running times and completion behavior at multiples of the estimated threshold.
- Threshold estimation: The simulations estimate threshold values β∗ by defining completable probability through f(n,d,β∗)=1/2 and fitting logistic regressions to sampled binary outcomes.The procedure uses exhaustive searches for small matrices and logistic regression for larger sizes.
- Asymptotic analysis: The estimated thresholds are compared with Candès–Recht and Keshavan–Oh–Montanari bounds, whose asymptotic forms are β∗∼C(d)n^-0.8 log n and β∗∼C(d)n^-1 log n, respectively.Linear regressions model log β∗ using log n and log log n for rank-2 Gram completion and summarize other ranks separately.
- Threshold results: Global completion curves for dimension d coincide with local completion curves for dimension d+1 in both Gram and rectangular cases.Figure 6.1 compares threshold β∗ against n for d=2, 3, 4.
- Completion behavior: At β=0.75β∗, matrices are not locally completable, whereas at β=2β∗ they are locally and globally completable in the reported experiments.For global completion, the first-column settings are locally but not globally completable.
- Running time: The iterative LSQR method often runs faster as the number of revealed entries increases because it converges in fewer iterations.The running-time tables report local completion for rank-2 rectangular matrices across values of m.
7. Summary and Discussion.
The paper connects rank-d matrix completion with rigidity theory by replacing distances with inner products and develops completion and stress matrices for testing generic local and global completion. It concludes that rigidity results offer useful insights, while noting that some translations remain outside the paper’s scope.
- Summary and Discussion: The completion problem is tightly related to rigidity theory in R^d, with inner products replacing distances.This connection transfers rigidity-theoretic ideas to low-rank matrix completion.
- Summary and Discussion: Completion and stress matrices enable fast determination of generic local and global completion properties without attempting to fill in the missing entries.The algorithms determine whether a unique completion is possible rather than producing the completion itself.
- Limitations: Some rigidity-theory results, including a generalization of Laman’s theorem, were not developed in the paper because of the field’s size and differences between rigidity and completion.The authors identify these results as outside the current paper.