Why Low Rank Does Not Ensure Recovery
In a multi-omics study, some subjects may lack whole modalities, leaving blocks of a subjects-by-features matrix unobserved. A low-rank model can make the missing entries predictable when the observed entries constrain the matrix sufficiently. But the statement “the matrix has low rank” is not, by itself, enough: there may be multiple low-rank matrices that agree on every observed entry and differ on the missing ones. In that case, no completion algorithm can determine which matrix generated the observations without additional information.
The distinction is between a computational problem and an information problem. An algorithm may fail to find a completion even when one is uniquely determined; conversely, an algorithm may return a plausible completion when the observations allow many possibilities. Identifiability asks the prior question: do the observed entries and stated assumptions determine the target at all?
The definition concerns the full matrix, not just a particular prediction or a particular factorization. It also describes an idealized exact-data setting. In noisy settings, one instead asks whether the observations contain enough information to estimate the target with useful precision under an appropriate noise model; exact uniqueness alone does not guarantee a stable estimate.
Necessary Checks and a Local Justification
A rank-\(r\) matrix has \(r(n+p-r)\) free dimensions when its rank is exactly \(r\). One way to see the count is to write \(X=UV^\mathsf{T}\), where \(U\) has \(n r\) entries and \(V\) has \(p r\) entries. The factorization has an \(r^2\)-dimensional redundancy: replacing \(U,V\) by \(UA,VA^{-\mathsf{T}}\) does not change \(X\). Subtracting that redundancy gives \(nr+pr-r^2=r(n+p-r)\).
This count gives a necessary, not sufficient, condition for generic identification: there must be at least \(r(n+p-r)\) observed entries. If there are fewer, the observations cannot usually constrain all degrees of freedom. If there are at least that many, uniqueness still does not follow, because the observations might repeat the same constraint or leave part of the matrix untouched.
A more precise local check comes from perturbing the matrix. At \(X=UV^\mathsf{T}\), small changes in the factors produce the first-order matrix change \(\Delta X=\Delta U V^\mathsf{T}+U\Delta V^\mathsf{T}\). A local ambiguity exists if a nonzero change in the matrix of this form is zero at every observed position. Changes in the factors that leave the product unchanged are not genuine matrix changes; these are the factorization redundancy noted above.
Thus, after disregarding changes to the factors that leave \(X\) unchanged, the observed-entry map must have no nonzero allowable first-order change in its null space for regular local identification. This test explains why the placement of observations matters in addition to their number. It is a local test: passing it does not in general rule out a separate, distant completion. The exact global criterion remains the definition—there must be no other rank-at-most-\(r\) matrix agreeing with the observations.
Three Ways Observations Can Fail to Identify the Matrix
Worked Example: A Feature Is Never Observed
Consider a hypothetical three-subject, three-feature matrix with rank at most one. Suppose the observed first two columns are \((1,2,3)^\mathsf{T}\) and \((2,4,6)^\mathsf{T}\), while no entry of the third feature is observed. These observed columns are proportional, as required by a rank-one model.
For any real number \(c\), the matrix \(\begin{pmatrix}1&2&c\\2&4&2c\\3&6&3c\end{pmatrix}\) has rank at most one: its second and third columns are respectively two and \(c\) times its first column. Every value of \(c\) gives exactly the same observed entries.
For example, \(c=1\) makes the missing third column \((1,2,3)^\mathsf{T}\), while \(c=4\) makes it \((4,8,12)^\mathsf{T}\). Both completions satisfy the rank constraint. Therefore, the third feature is not identified, even though the observed entries are perfectly compatible with rank one.
A completely unobserved feature is an especially direct failure: the data contain no measurement of its scale. A low-rank relationship can constrain its pattern across subjects, but here it cannot determine the multiplier \(c\). Other assumptions or measurements could restrict that multiplier, but they would add information beyond the observed entries and rank bound.
Worked Example: A Disconnected Availability Pattern
Suppose a hypothetical \(2\times2\) matrix has rank at most one and only its diagonal entries are observed: \(X_{11}=2\) and \(X_{22}=3\). Write the matrix as \(\begin{pmatrix}2&a\\b&3\end{pmatrix}\). A \(2\times2\) matrix has rank at most one exactly when its determinant is zero, so
The observations do not specify \(a\) and \(b\) separately. For \(a=1\), \(b=6\), the completed matrix is \(\begin{pmatrix}2&1\\6&3\end{pmatrix}\). For \(a=2\), \(b=3\), it is \(\begin{pmatrix}2&2\\3&3\end{pmatrix}\). Both have determinant zero and reproduce the observed diagonal, yet they disagree on both missing entries.
The availability pattern has two disconnected pieces: one observed entry links the first row and first column, and the other links the second row and second column, but there are no shared observations joining those pieces. The rank constraint relates the missing entries through their product but does not determine either one individually. Connectivity can be a useful necessary check in simple settings, but for rank greater than one it is not, by itself, a sufficient condition for identification.
Worked Example: Enough Entries, but Not Enough Diversity
Consider a hypothetical \(3\times3\) matrix with rank at most two. Suppose its first two rows are fully observed as \((1,1,1)\) and \((2,0,2)\); in the third row only columns 1 and 3 are observed, both with value 5. There are eight observed entries. The rank-two dimension count is \(2(3+3-2)=8\), so the count does not reveal a shortage.
The first two rows are linearly independent, so any third row that keeps the full matrix rank at most two must be a linear combination \(c(1,1,1)+d(2,0,2)\). Its first and third entries are both \(c+2d\), while its second entry is \(c\). The observed third-row values give only the single equation \(c+2d=5\), repeated at two positions.
For \(c=1,d=2\), the third row is \((5,1,5)\); for \(c=3,d=1\), it is \((5,3,5)\). Each resulting matrix has rank two, agrees with all eight observed values, and has a different missing entry. The repeated constraints arise because the first and third columns of the first two rows carry the same information about \(c\) and \(d\). The observations are numerous enough by the count, but not diverse enough to distinguish the possible matrices.
Assumptions, Diagnostics, and Alternatives
An identifiability claim is always conditional on its model. For the exact criterion above, the observed values must be treated as exact, the entries must belong to one common matrix, and the rank bound \(r\) must be specified. If rank is not known, different rank choices define different sets of allowable completions. In practical data, measurement noise, preprocessing, and biological departures from low rank complicate this idealization; a unique exact completion under an assumed rank does not establish that the assumed rank describes the data well.
Useful diagnostics focus on information structure before interpreting a computed completion:
- Check feature and subject coverage. A completely unobserved row or column cannot generally be recovered from the entries and rank bound alone. A subject or feature with very few observed entries may also remain weakly constrained.
- Inspect availability connections. Disconnected groups of subjects and features can have independent factor scales or orientations. The overlap graph from shared subjects is a useful summary, but connectivity does not guarantee identification for higher rank.
- Check the number and placement of observations. Compare the count with \(r(n+p-r)\), then ask whether observations constrain distinct directions rather than repeatedly constraining the same combinations.
- Look for unstable solutions. Very different completions with nearly identical agreement on observed entries indicate weak information or sensitivity. Optimization convergence is not evidence of unique recovery.
These checks diagnose different failure modes. A missing entire feature is a direct absence of information. Disconnection is a structural separation in which blocks may not be tied together. Insufficient diversity can occur even with connected patterns and a seemingly adequate entry count. In real applications, proving global uniqueness for a specific pattern can be harder than these checks; they should be treated as warnings and necessary conditions, not as a universal recipe for a proof.
There are several responses to nonidentifiability, but they change what information or target is being used. Collecting measurements that connect the unsupported features or groups directly adds observations. A scientifically justified structural model or external data can constrain otherwise free values, but the resulting completion is identified only conditional on those added assumptions. Alternatively, report that some entries are not identified rather than presenting one algorithm’s selected solution as uniquely determined. Regularization can favor one solution among many; it does not, on its own, make the data identify that solution.
This distinction also separates matrix completion from some common alternatives. Direct measurement avoids inferring the missing entry, while a model using external covariates may predict it by borrowing information not contained in the observed matrix. Neither should be described as recovery from low rank alone. The missingness mechanism is a separate issue: even a uniquely determined matrix under a mathematical rank model does not automatically establish that conclusions about the study population are unbiased.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- A \(4\times5\) matrix is assumed to have rank at most two. How many free dimensions does a generic rank-two matrix have, and what does the count imply if only 12 entries are observed?
- Why does a uniquely determined matrix not imply a uniquely determined pair of factors \(U,V\) in \(X=UV^\mathsf{T}\)?
- In the \(2\times2\) diagonal example, what equation links the missing entries, and why does it fail to identify them separately?
- Can eight observations identify every rank-two \(3\times3\) matrix completion? Explain using the diversity example.
Solutions. (1) The dimension is \(r(n+p-r)=2(4+5-2)=14\). Twelve observations are fewer than 14, so generic identification is not possible; special matrices or extra constraints do not turn the count into a general guarantee. (2) For any invertible \(A\), \(UA\) and \(VA^{-\mathsf{T}}\) have the same product, so factor values can vary while the matrix stays fixed. (3) The determinant condition gives \(ab=6\). Many pairs satisfy it, including \((a,b)=(1,6)\) and \((2,3)\), so the missing entries are not separately determined. (4) No. The example has eight observations, matching the dimension count, but two observations impose the same constraint on the third-row coefficients; the missing entry can be 1 or 3 in valid rank-two completions.