Tensor completion and sampling
Separate missing-data fitting from recovery guarantees and prove an exact anchored rank-one completion under nonzero observations.
On this page
The question for today
What you’ll understand
- Formulate observed-entry least squares without filling unknown entries with zeros.
- Identify sampling and nonconcentration assumptions needed for meaningful recovery claims.
- Recover an anchored rank-one tensor and exhibit an observation-pattern ambiguity.
Compression approximates a tensor whose entries are available. Completion tries to determine unobserved entries from a structural assumption and a sampling pattern. A low-rank model alone does not make this possible: whole factors may remain unseen, or almost all tensor mass may occupy an unobserved coordinate. We will formulate the observed-data objective, distinguish the assumptions used by recovery theory, and prove a small exact completion result where the algebra and required observations are completely explicit.
Only observed coordinates contribute to the data fit
Let Ω be a known set of observed index tuples, and let PΩ retain those entries while setting other coordinates to zero. A standard real least-squares model minimizes one-half the squared Frobenius norm of PΩ(X − Y) over a chosen tensor format, perhaps with penalties. Here Y is only required to supply the observed values. Unknown entries are excluded from the loss; assigning them numerical zeros and fitting them would change the observations.
The rank notion must be specified. A CP term bound, Tucker mode-rank tuple, and TT bond tuple constrain different feasible sets and can have different optimization behavior. Even a globally optimal observed fit need not determine one full tensor. Weighted CP optimization is an effective method for incomplete data, but successful numerical experiments under one missingness pattern do not constitute an assumption-free exact recovery theorem.
Observation geometry matters as much as sample count
If an entire mode slice is unobserved, the corresponding factor row can vary without affecting a rank-one observed fit. A tensor concentrated at one unobserved coordinate is another obstruction: both it and the zero tensor can match all observed zeros. These examples explain why recovery theorems impose conditions preventing concentration, often called incoherence, together with a specified random or sufficiently informative deterministic observation model.
Independent uniform Bernoulli observation means each coordinate is included with the same probability, independently of both other coordinates and the tensor values. It is different from missingness driven by signal magnitude or a sensor that loses an entire channel. Sample-complexity claims also depend on mode dimensions, ranks, noise assumptions, target accuracy, and sometimes algorithm initialization. We do not state a universal tensor recovery threshold here; the anchored example instead provides a fully proved special case.
Four anchors with a nonzero pivot determine one tiny rank-one tensor
For a two-by-two-by-two rank-one tensor, suppose the observed anchors are T₁₁₁ = a ≠ 0, T₂₁₁ = b, T₁₂₁ = c, and T₁₁₂ = d. The nonzero first anchor permits a gauge with first two factors (1, b/a) and (1, c/a), and third factor (a, d). Multiplying them determines every unobserved entry. In particular the opposite corner is bcd/a². This is uniqueness of the completed tensor within the stated rank-one class, not uniqueness of unnormalized factors.
The nonzero anchor and its pattern are essential to this division argument. If the second third-mode slice has no observation, its scale remains free even when the first slice is completely known. Under independent Bernoulli observation, a large expected count does not guarantee these particular anchors appear. One can compute the probability of that sufficient anchor event, but it is not the probability of recovery by every method because other observation patterns may also determine the tensor.
Work it through
Complete a rank-one cube from its anchors
Assume exact rank one and observed anchors T₁₁₁ = 2, T₂₁₁ = 6, T₁₂₁ = 4, T₁₁₂ = 10. Recover the remaining four entries and explain uniqueness.
The nonzero anchor permits factors u = (1, 3), v = (1, 2), and w = (2, 10). Their four anchor products are two, six, four, and ten, matching every observation.
The unobserved products are T₂₂₁ = 3×2×2 = 12, T₂₁₂ = 3×1×10 = 30, T₁₂₂ = 1×2×10 = 20, and T₂₂₂ = 3×2×10 = 60.
Any rank-one tensor matching the nonzero first anchor can be rescaled into the same factor gauge. The three observed anchor ratios fix the remaining factor coordinates, so all four missing entries are forced within this exact rank-one model.
The completed missing values are 12, 30, 20, and 60. Uniqueness uses the model, the anchor pattern, and the nonzero anchor together.
The living notebook
Explore the model
Interactive lab · probability
A sample count does not reveal its coordinate pattern
Pause and Reset, then set both success probability p = 0.5 and trials n = 8. Interpret successes as independently observed entries of a two-by-two-by-two tensor. Predict mean count 4, variance 2, and zero-observation probability 1/256. The four specified anchors are all observed with probability (1/2)⁴ = 1/16, which the count alone cannot identify. The chart gives exact count probabilities, not coordinate masks or a tensor recovery experiment.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forObserving four entries on average is weaker than observing a pattern that algebraically determines the missing values.
Pause & reason
Check your understanding
Your turn
Try it yourself
Take rank-one anchors a = 1, b = 2, c = 3, and d = 4. Compute T₂₂₂. Then remove the observation d and explain whether the first third-mode slice alone determines that corner.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Use the anchor formula when d is observed. Without it, let the second entry of w vary while retaining w₁ = 1.
Compare with the solution
With all four anchors, T₂₂₂ = 2×3×4/1² = 24. If d is unobserved and the first slice is known, choose u = (1, 2), v = (1, 3), and w = (1, t) for any real t. Every such rank-one tensor has exactly the same first slice, but its opposite corner is 6t. Thus first-slice observations do not determine that entry; additional rank-one structure does not remove the unseen third-mode scale. This ambiguity concerns the completed tensor itself, rather than merely equivalent factor gauges.
Keep the idea
Take it with you
- Completion fits observed coordinates, with missing entries excluded rather than treated as measured zeros.
- Rank, observation geometry, concentration, and noise assumptions jointly govern recovery claims.
- An exact anchored example proves a special recovery result while exposing why a missing slice can destroy uniqueness.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.