Low-Rank Tensor Completion by Alternating Algorithms

Completion From Observed Entries

A tensor may be only partly recorded: some combinations of its indices have measured values, while others are unavailable. Completion uses a structural assumption—here, low tensor rank—to estimate the unobserved entries. The crucial point is that the fit must be assessed on the entries that were actually observed. Filling missing cells with zeros and fitting an ordinary tensor approximation instead treats those zeros as data and generally solves a different problem.

We use a rank-$R$ CP model. It represents the entry with indices $i_1,\ldots,i_K$ as a sum of $R$ products of mode-specific factor entries. The factors are estimated from the observed entries, not from a fully observed array.

Definition: Let $\mathcal{Y}$ be a $K$-way tensor of size $I_1\times\cdots\times I_K$, and let $\Omega$ be the set of observed index tuples. A rank-$R$ CP completion model has factor matrices $A^{(k)}\in\mathbb{R}^{I_k\times R}$ and fitted entries $$ \widehat y_{i_1\cdots i_K} = \sum_{r=1}^{R}\prod_{k=1}^{K}a^{(k)}_{i_k r}. $$ The unregularized observed-entry least-squares objective is $$ J(A^{(1)},\ldots,A^{(K)}) = \frac12\sum_{(i_1,\ldots,i_K)\in\Omega} \left(y_{i_1\cdots i_K}-\widehat y_{i_1\cdots i_K}\right)^2. $$

A common regularized objective adds a quadratic penalty to discourage large factor entries:

J_\lambda = \frac12\sum_{\boldsymbol{i}\in\Omega}(y_{\boldsymbol{i}}-\widehat y_{\boldsymbol{i}})^2 + \frac{\lambda}{2}\sum_{k=1}^{K}\|A^{(k)}\|_F^2, \qquad \lambda>0.

Here $\boldsymbol{i}$ denotes the full index tuple. The penalty is part of the fitting criterion, so it can shrink estimates and change the fitted completion. It does not, by itself, establish that the missing entries are identifiable from the observations.

Alternating Least-Squares Updates

Alternating least squares (ALS) optimizes one factor matrix at a time, holding the other matrices fixed. For a particular mode $k$ and row $i_k$, each observed entry involving that row is linear in the $R$ entries of that row. Define its design vector by

z_{(i_1,\ldots,i_K),r} = \prod_{\ell\ne k}a^{(\ell)}_{i_\ell r}, \qquad r=1,\ldots,R.

Collect these design vectors as rows of a matrix $Z$, and collect the corresponding observed values as a vector $y$. If $a$ is row $i_k$ of $A^{(k)}$, the contributions of this row to the predictions are $Za$. The unregularized conditional problem is therefore ordinary least squares, $\min_a \frac12\|y-Za\|_2^2$. Its normal equations are $Z^\mathsf{T}Za=Z^\mathsf{T}y$; if $Z^\mathsf{T}Z$ is singular, a unique row update need not exist.

Theorem: For the regularized objective $J_\lambda$, the conditional minimizer for one row of one factor matrix is $$ a=(Z^\mathsf{T}Z+\lambda I_R)^{-1}Z^\mathsf{T}y. $$ This update is uniquely defined for every $Z$ when $\lambda>0$. It does not follow that the resulting matrix is well-conditioned for every choice of $Z$ and $\lambda$.

Proof. With all other factors fixed, the terms involving this row are $\frac12\|y-Za\|_2^2+\frac{\lambda}{2}\|a\|_2^2$, plus terms constant in $a$. Differentiating with respect to $a$ gives $Z^\mathsf{T}(Za-y)+\lambda a=0$. Thus $(Z^\mathsf{T}Z+\lambda I_R)a=Z^\mathsf{T}y$. For any nonzero $v\in\mathbb{R}^R$, $$ v^\mathsf{T}(Z^\mathsf{T}Z+\lambda I_R)v = \|Zv\|_2^2+\lambda\|v\|_2^2>0. $$ So the matrix is positive definite and invertible, proving the formula and uniqueness. Positive definiteness does not imply a small condition number: for example, if $Z=[10^{10},\,0]$ and $\lambda=1$, then $Z^\mathsf{T}Z+\lambda I_2=\operatorname{diag}(10^{20}+1,1)$, whose condition number is approximately $10^{20}$. The ridge term can improve conditioning, but whether it does so enough depends on both the design and $\lambda$. $\square$

When a row has no observed entries, its data contribution has no rows in $Z$. With $\lambda>0$, its conditional minimizer is $a=0$; without regularization, the objective does not determine that row. In computation, each mode update builds the appropriate observed-entry designs and solves these conditional problems, then cycles through the modes.

Worked Example: One Unregularized CP Row Update

Consider a rank-one three-way model, with the other factor rows fixed at $b_1=1,\ b_2=2$ and $c_1=1,\ c_2=3$. Update $a_1$ using three observed entries in the slice with first index 1: $y_{111}=2,\ y_{121}=1,\ y_{112}=3$. Their design values are respectively $b_1c_1=1,\ b_2c_1=2,\ b_1c_2=3$. Thus $Z=(1,2,3)^\mathsf{T}$ and $y=(2,1,3)^\mathsf{T}$, giving $$ \widehat a_1 = \frac{Z^\mathsf{T}y}{Z^\mathsf{T}Z} = \frac{1(2)+2(1)+3(3)}{1^2+2^2+3^2} = \frac{13}{14}. $$

The fitted values at those entries are $13/14,\ 13/7,\ 39/14$. The residuals, in the same order, are $15/14,\ -6/7,\ 3/14$. The residual sum of squares is $$ \left(\frac{15}{14}\right)^2+\left(-\frac67\right)^2+\left(\frac3{14}\right)^2 = \frac{225+144+9}{196} = \frac{189}{98}. $$ The normal-equation check is $1(15/14)+2(-6/7)+3(3/14)=0$, as required for a least-squares solution.

Worked Example: A Ridge Row Update

Take two design rows $Z=\begin{pmatrix}1&0\\1&2\end{pmatrix}$, observations $y=(2,1)^\mathsf{T}$, and $\lambda=1$. Then $$ Z^\mathsf{T}Z= \begin{pmatrix}2&2\\2&4\end{pmatrix}, \qquad Z^\mathsf{T}y= \begin{pmatrix}3\\2\end{pmatrix}. $$ Adding the ridge term gives $\begin{pmatrix}3&2\\2&5\end{pmatrix}a=\begin{pmatrix}3\\2\end{pmatrix}$. Its determinant is $15-4=11$, so $$ a = \frac1{11} \begin{pmatrix}5&-2\\-2&3\end{pmatrix} \begin{pmatrix}3\\2\end{pmatrix} = \begin{pmatrix}11/11\\0/11\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix}. $$ This is the unique conditional minimizer. The calculation illustrates the update, not a guarantee that ridge always improves the condition number by a specified amount.

What ALS Guarantees—and What It Does Not

An exact update minimizes the objective over the block currently being changed. This gives a basic descent property, but does not establish that ALS finds a global minimizer or that its factors converge to a unique solution. CP factors have scale and permutation ambiguities, and the observed-entry objective is generally nonconvex.

Result: Suppose each ALS block update is an exact minimizer of the same objective $J_\lambda$. Then the objective value does not increase at any update. If $J_\lambda$ is bounded below, the sequence of objective values converges to a finite limit. This statement alone does not imply convergence of the factor matrices or global optimality.

Proof. At an update, the current factors are feasible candidates for the block minimization. The block minimizer therefore has objective no larger than the value immediately before the update. Repeating this argument shows that the objective values form a nonincreasing sequence. Since they are bounded below, their infimum is finite. A nonincreasing real sequence bounded below converges to its infimum. This proves the claim about objective values; it makes no claim about factor convergence or the location of a global minimum. $\square$

The ridge penalty makes each row-update matrix invertible, as shown above. It may improve conditioning and limit large factor entries, but the conditioning depends on the design and penalty size. Also, the CP representation can trade scale among modes: multiplying one component's entries in one factor by a constant and dividing another factor's entries by the same constant preserves its fitted tensor. A penalty on all factors selects among such representations by penalizing their sizes; it does not remove the nonconvexity of the completion problem.

Sampling Patterns, Identifiability, and Incoherence

The observation set $\Omega$ determines which combinations of entries constrain the fitted tensor. A large number of observations is not sufficient if they are concentrated in a way that leaves some rows, slices, or interactions unconstrained. In addition, low rank alone may not make an unseen entry recoverable: different low-rank tensors can agree on every observed entry.

Worked Example: A Pattern With Nonunique Completions

Suppose a $2\times2$ matrix is observed only in its first row, with $y_{11}=1$ and $y_{12}=2$. For every real number $t$, the matrix $$ M(t)= \begin{pmatrix} 1&2\\ t&2t \end{pmatrix} $$ has rank one (including rank zero when $t=0$) and matches both observations. Its missing entries vary with $t$. Thus the observed values and a rank-at-most-one constraint do not identify a unique completion. No algorithm can infer the correct $t$ from these observations alone without additional assumptions or information.

A useful concept for describing whether a low-rank signal is concentrated on a few coordinates is incoherence. For a matrix of rank $r$ with left and right singular-vector matrices $U\in\mathbb{R}^{m\times r}$ and $V\in\mathbb{R}^{n\times r}$, define their subspace coherence by $$ \mu(U)=\frac{m}{r}\max_{1\le i\le m}\|U^\mathsf{T}e_i\|_2^2, \qquad \mu(V)=\frac{n}{r}\max_{1\le j\le n}\|V^\mathsf{T}e_j\|_2^2. $$ Here $e_i$ is a coordinate basis vector. Since the columns of $U$ are orthonormal, the average of the row leverage values $\|U^\mathsf{T}e_i\|_2^2$ is $r/m$, so $\mu(U)\ge1$; similarly $\mu(V)\ge1$. A small coherence means that neither singular subspace is concentrated on only a few rows or columns. Tensor models have corresponding concerns: factor rows or mode subspaces should not place nearly all the signal on a few indices. For a CP fit, examining the factor-row magnitudes can help diagnose concentration, although factor-wise checks alone are not a universal recovery theorem.

Incoherence matters because a uniformly sampled observation pattern is more likely to reveal a spread-out signal than one concentrated at a rarely sampled coordinate. But incoherence does not repair every pattern: deterministic holes can still prevent identification, as in the example. Recovery guarantees in particular settings require assumptions about the rank, the sampling mechanism, the number of observations, and the signal's coherence. They should not be inferred merely from a low training error or a large count of observed entries.

Worked Example: Coherence of a Rank-One Matrix

Let $M=uv^\mathsf{T}$ be a $4\times3$ rank-one matrix with unit vectors $u=(1,1,1,1)^\mathsf{T}/2$ and $v=(1,1,1)^\mathsf{T}/\sqrt3$. The left singular subspace is spanned by $u$, so each squared row projection is $u_i^2=1/4$, and $$ \mu(U)=\frac41\max_i\frac14=1. $$ Likewise, each squared right projection is $1/3$, giving $\mu(V)=\frac31\max_j\frac13=1$. These values are minimal and indicate spread across the coordinates. In contrast, if $u=(1,0,0,0)^\mathsf{T}$, then $\mu(U)=4$: all of the left singular direction lies in the first row. If that row is unobserved, observations elsewhere cannot reveal its contribution. The coherence calculation diagnoses concentration; it does not by itself specify an algorithm or guarantee recovery.

Practical Checks Before Trusting a Completion

Completion algorithms are useful when the structural model and the observation design work together. Before interpreting a fitted tensor, inspect which entries, rows, and mode-wise combinations are represented in $\Omega$; check whether the fitted factors are highly concentrated; and compare observed-entry fit across ranks and regularization strengths. Hold out some observed entries when possible to assess prediction on entries not used for fitting. A small training residual is not evidence that unobserved entries are uniquely determined.

Confusing missingness with a measured zero. Zero-filling changes the objective by adding artificial observations. Sum residuals only over $\Omega$.
Equating an invertible update with a well-conditioned one. Ridge gives a positive-definite row system for $\lambda>0$, but its condition number still depends on $Z$ and $\lambda$.
Assuming low rank ensures unique completion. The observation pattern can leave multiple low-rank tensors consistent with the data.
Reading descent as a global guarantee. Exact ALS updates do not increase the objective, but the objective is nonconvex and descent alone does not prove global optimality or factor convergence.

Key takeaway: Low-rank tensor completion fits the observed entries using a structural model. Alternating updates provide tractable conditional least-squares problems; reliable interpretation still depends on the observation pattern, the signal's concentration, and the limitations of nonconvex optimization.

Check Your Understanding

Answer these questions by referring to the objective, update equations, and sampling assumptions.

Why is it generally incorrect to replace every missing entry by zero before fitting an observed-entry least-squares model?
For a ridge row update, explain why $Z^\mathsf{T}Z+\lambda I_R$ is invertible when $\lambda>0$, and why this does not guarantee good conditioning.
What does exact block minimization guarantee about the ALS objective values, and what does it not guarantee about the factor matrices?
In the first-row-only matrix example, why can no method determine the missing second row from the observations and a rank-at-most-one assumption alone?
What does a coherence value near its minimum indicate about a singular subspace, and why is low coherence not enough to fix a structurally inadequate observation pattern?