1

Deterministic and Probabilistic Conditions for Finite
Completability of Low-Tucker-Rank Tensor

arXiv:1612.01597v2 [cs.NA] 28 Feb 2018

Morteza Ashraphijuo, Vaneet Aggarwal and Xiaodong Wang

Abstract
We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for
finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic
necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which
allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional
geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a
set of polynomials defined based on the sampling pattern, which is closely related to finite completability of the
sampled tensor, where finite completability simply means that the number of possible completions of the sampled
tensor is finite. Probabilistic conditions are then studied and a lower bound on the sampling probability is given,
which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold
with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a
sufficient condition on the sampling pattern that ensures there exists exactly one completion of the sampled tensor.

Index Terms
Low-rank tensor completion, finite completion, unique completion, Grassmannian manifold, Tucker manifold, extended Hall’s theorem.

The deterministic analysis part of this work is presented in part in ISIT 2017, Aachen, Germany [1].
Morteza Ashraphijuo and Xiaodong Wang are with the Department of Electrical Engineering, Columbia University, NY, email:
{ashraphijuo,wangx}@ee.columbia.edu. Vaneet Aggarwal is with the School of IE, Purdue University, West Lafayette, IN, email:
vaneet@purdue.edu.

2

I. I NTRODUCTION
Tensors are generalizations of vectors and matrices: a vector is a first-order tensor and a matrix is a
second-order tensor. Most data around us are better represented with multiple dimensions to capture the
correlations across different attributes. For example, a colored image can be considered as a third-order
tensor, two of the dimensions (rows and columns) being spatial, and the third being spectral (color); while
a colored video sequence can be considered as a fourth-order tensor, with time being the fourth dimension
besides spatial and spectral dimensions. Similarly, a colored 3-D MRI image across time can be considered
as a fifth-order tensor. In many applications, part of the data may be missing. This paper investigates the
fundamental conditions on the locations of the non-missing entries such that the multi-dimensional data
can be recovered in finite and/or unique choices. In particular, we investigate deterministic and probabilistic
conditions on the sampling pattern for finite or unique solution to a low-rank tensor completion problem
given the sampled tensor and some of its Tucker rank components, i.e., ranks of some of its matricizations.
There are numerous applications of low-rank data completion in various areas including image or signal
processing [2, 3], data mining [4], network coding [5], compressed sensing [6–8], reconstructing the visual
data [9–11], seismic data processing [12–14], RF fingerprinting [15, 16], and reconstruction of cellular
data [17].
The majority of the literature on matrix and tensor completion are concerned with developing various
optimization-based algorithms under some assumptions such as incoherence [18], etc., to construct a
completion. In particular, low-rank matrix completion has been widely studied and many algorithms based
on convex relaxation of rank [19–21] and alternating minimization [18, 22], etc., have been proposed. Also,
a generalization of the low-rank matrix completion, which is completion from several low-rank sources
has attracted attention recently [23–26]. For the tensor completion problem various solutions have been
proposed that are based on convex relaxation of rank constraints [8, 12, 27–30], alternating minimization
[10, 11, 14] and other heuristics [16, 31–33].
In the existing literature on optimization-based matrix or tensor completions, in addition to meeting the
lower bound on the sampling probability, conditions such as incoherence [18, 33, 34], which constrains the
values of the matrix or tensor entries, are required to obtain a completion with high probability. On the other
hand, fundamental completability conditions that are independent of the specific completion algorithms
have also been investigated. In [35, 36] deterministic conditions on the locations of the sampled entries
(sampling pattern) have been studied through algebraic geometry approaches on Grassmannian manifold

3

that lead to finite and unique solutions to the matrix completion problem, where finite completability
simply means that the number of possible completions of the sampled tensor is finite. Specifically, in [35]
a deterministic sampling pattern is proposed that is necessary and sufficient for finite completability of
the sampled matrix of the given rank. Such an algorithm-independent condition can lead to a much lower
sampling rate than that is required by the optimization-based completion algorithms. For example, the
required number of samples per column in [18] is on the order of O(log(n)r2.5 log(kXkF )), where X
is the unknown matrix with n rows and of rank r, while the required number of samples per column
in [35] is on the order of O(max{log(n), r}). The analysis on Grassmannian manifold in [35] is not
capable of incorporating more than one rank constraint, and therefore this method is not efficient for
solving the same problem for a tensor given multiple rank components. In this paper, we propose a
geometric analysis on Tucker manifold to obtain deterministic and probabilistic conditions that lead to
finite or unique completability for low-rank tensors when multiple rank components are given. Moreover,
other related problems have been studied using algebraic geometry analysis, including high-rank matrix
completion [37], rank estimation [38], and subspace clustering with missing data [39–42].
This work is inspired by [35], where the analysis on Grassmannian manifold is proposed for a singleview matrix. Specifically, in [35] a novel approach is proposed to consider the rank factorization of a
matrix and to treat each observed entry as a polynomial in terms of the entries of the components of
the rank factorization. Then, under the genericity assumption, the algebraic independence among the
mentioned polynomials is studied. In this paper, we consider the low-Tucker-rank tensor and follow the
general approach that is similar to that in [35]. We mention some of the main differences: (i) geometry
of the manifold, (ii) the equivalence class for the core tensor and consequently (iii) the canonical core
tensor, (iv) structure of the polynomials, etc. are fundamentally different from those in [35]. Moreover,
(v) the idea of using more than one rank constraint simultaneously in the algebraic geometry approach
is also new. Hence, the manifold structure for the low-Tucker-rank tensor is fundamentally different from
the Grassmannian manifold and we need to develop almost every step anew.
Tucker decomposition is a well-known method to represent a tensor [43–45]. In this paper, we use this
decomposition to represent the sparsity of a tensor and use Tucker rank to model the low-rank structure
of the tensor. There are several other well-known decompositions of a tensor as well, including polyadic
decomposition [46, 47], tensor-train decomposition [48, 49], hierarchical Tucker representation [50, 51],
tubal rank decomposition [52] and others [53–55].

4

This paper focuses on the low-rank tensor completion problem, given a portion of the rank vector of
the tensor. Specifically, we investigate the following three problems:
•

Problem (i): Characterizing the necessary and sufficient conditions on the sampling pattern to have
finitely many tensor completions for the given rank.
To solve this fundamental problem, we propose a geometric analysis framework on Tucker manifold.
Specifically, we obtain a set of polynomials based on the location of the sampled entries in tensor
and use Bernstein’s theorem [56, 57] to identify the condition on the sampling pattern for ensuring
sufficient number of algebraically independent polynomials in the mentioned set. Given any nonempty
proper subset of the Tucker rank vector, this analysis leads to the necessary and sufficient condition
on the sampling patterns for finite completability of the tensor. Given the entire Tucker rank vector
this condition is sufficient for finite completability.

•

Problem (ii): Characterizing conditions on the sampling pattern to ensure that there is exactly one
completion for the given rank.
We use our proposed geometric analysis for finite completability of low-rank tensors to obtain a
sufficient conditions on the sampling patterns to ensure unique completability, which is milder than
the sufficient condition for unique completability obtained through matricization analysis and applying
the matrix method in [35].

•

Problem (iii): If the elements in the tensor are sampled independently with probability p, what are the
conditions on p such that the conditions in Problems (i) and (ii) are satisfied with high probability?
We bound the number of needed samples to ensure the proposed sampling patterns for finite and
unique tensor completability hold with high probability. Even though we follow a similar approach
to [35] for the matrix case, we develop a generalization of Hall’s theorem for bipartite graphs which
is needed to prove the correctness of the bounds for both the tensor and the matrix cases. Moreover,
it is seen that our proposed analysis on Tucker manifold leads to a much lower sampling rate than
the corresponding analysis on Grassmannian manifold for both finite and unique tensor completions.

The remainder of this paper is organized as follows. In Section II, some preliminaries and notations are
presented, and also an example is given that illustrates the advantage of tensor analysis over analyzing
matricizations of a tensor. In Section III, Problem (i) is studied and the sampling patterns that ensure finite
completions are found using tensor algebra. In Section IV, we study Problem (iii) for the case of finite
completion and the key to solving this problem is the proof of the generalized Hall’s theorem, which is an

5

independent result in graph theory. Section V considers Problem (ii) to give a sufficient condition on the
sampling pattern for unique completability. Further, Problem (iii) for unique completion is also studied.
Some numerical results are provided in Section VI to compare the sampling rates for finite and unique
completions based on our proposed tensor analysis versus the matricization method. Finally, Section VII
concludes the paper.
II. BACKGROUND
A. Preliminaries and Notations
In this paper, it is assumed that a dth -order tensor U ∈ Rn1 ×···×nd is chosen generically from the
manifold of n1 × . . . × nd tensors of the given Tucker rank (will be explained rigorously later). For

the sake of simplicity in notation, define N , Πdj=1 nj and N−i , nNi . Also, for any real number x, define x+ , max{0, x}. Let U(i) ∈ Rni ×N−i be the i-th matricization of the tensor U such
that U(~x) = U(i) (xi , M(i) (x1 , . . . , xi−1 , xi+1 , . . . , xd )), where M(i) is an arbitrary bijective mapping
M(i) : (x1 , . . . , xi−1 , xi+1 , . . . , xd ) → {1, 2, . . . , N−i } and U(~x) represents an entry of the tensor U with
coordinate ~x = (x1 , . . . , xd ).
0

0

Given U ∈ Rn1 ×···×nd and X ∈ Rni ×ni , U 0 , U ×i X ∈ Rn1 ×···×ni−1 ×ni ×ni+1 ×···×nd is defined as
0

U (x1 , · · · , xi−1 , ki , xi+1 , · · · , xd ) ,

ni
X

U(x1 , · · · , xi−1 , xi , xi+1 , · · · , xd )X(xi , ki ).

(1)

xi =1

Throughout this paper, we use Tucker rank as the rank of a tensor, which is defined as rank(U) =
(r1 , . . . , rd ) where ri = rank(U(i) ). The Tucker decomposition of a tensor U is given by
U = C ×di=1 Ti ,

(2)

where C ∈ Rr1 ×···×rd is the core tensor and Ti ∈ Rri ×ni are d orthogonal matrices. Then, (2) can be
written as
U(~x) =

r1
X
k1 =1

···

rd
X

C(k1 , . . . , kd )T1 (k1 , x1 ) . . . Td (kd , xd ).

(3)

kd =1

The space of fixed Tucker-rank tensors is a manifold and the dimension of this manifold is shown in
P
[45] to be di=1 (ni × ri − ri2 ) + Πdi=1 ri . Denote Ω as the binary sampling pattern tensor that is of the
same size as U and Ω(~x) = 1 if U(~x) is observed and Ω(~x) = 0 otherwise. For each subtensor U 0 of the
tensor U, define NΩ (U 0 ) as the number of observed entries in U 0 according to the sampling pattern Ω.

6

B. Problem Statement and A Motivating Example
We are interested in finding deterministic conditions on the sampling pattern tensor Ω under which there
are infinite, finite, or unique completions of the sampled tensor U that satisfy rank(U) = (r1 , r2 , . . . , rd ).
Moreover, we are interested in finding probabilistic sampling strategies that ensure the obtained conditions
for finite and unique completability hold, respectively, with high probability. The matrix version of this
problem has been treated in [35]. In this paper, we investigate this problem for general order tensors.
In this subsection, we intend to compare the following two approaches in an example to emphasize the
necessity of our analysis for general order tensors: (i) analyzing each matricization individually with the
rank constraint of the corresponding matricization, (ii) analyzing via Tucker decomposition. In particular,
we will show via an example that analyzing each of the matricizations separately is not enough to guarantee
finite completability when multiple rank components are given. On the other hand, we show that for the
same example Tucker decomposition ensures finite completability. Hence, this example illustrates that
matricization analysis does not take advantage of the full information of given Tucker rank and thus fails
to provide a necessary and sufficient condition for finite completability when more than one component
of the rank vector is given.
Consider a 3rd -order tensor U ∈ R2×2×2 with Tucker rank (1, 1, 1). First, we show that having any
4 entries of U, there are infinitely many completions of any matricization with the corresponding rank
constraint. Hence, along each dimension there exist a set of infinite completions given the corresponding
rank constraint. Note that the analysis on Grassmannian manifold in [35] is not capable of incorporating
more than one rank constraint. However, as we show it is possible that the intersection of the mentioned
three infinite sets is a finite set and that is why we need an analysis that is able to incorporate more than
one rank constraint. Without loss of generality, it suffices to show the claim only for its first matricization.
Therefore, the claim reduces to the following statement:
Statement: Having any 4 entries of a rank-1 matrix U ∈ R2×4 , there are infinitely many completions
for it.
In order to prove the above statement, we need to consider the following four possible scenarios:
(i) The 4 observed entries are in a row. In this case, clearly, there are infinitely many completions for
the other row as it can be any scalar multiplied by the first row.
(ii) The 4 observed entries are such that there is a column in which there is no observed entries. In this
case, there are infinitely many completions for this column as it can be any scalar multiplied by the

7

other columns.
(iii) The 4 observed entries are such that there is one observed entry in each column, and also each row
has exactly two observed entries. Assume that the two observed entries in the second row are the
pair (a, b). In this case, for every pair (ka, kb) as the value of the two non-observed entries of the
first row (where k is an arbitrary scalar) there is a unique completion for the rest of the entries. As
a result, there are infinitely many completions for this matrix.
(iv) The 4 observed entries are such that there is one observed entry in each column, and also the first
and second rows have 3 and 1 observed entries, respectively. In this case, for each value of the only
non-observed entry of the first row there is a unique completion. Therefore, there are infinitely many
completions for this matrix.
Assume that the entries U(1, 1, 1), U(2, 1, 1), U(1, 2, 1), and U(1, 1, 2) are observed. Now, we take
advantage of all elements of Tucker rank simultaneously, in order to show there are only finitely many
tensor completions. Using Tucker decomposition (2), and given the rank is (1, 1, 1), without loss of
generality, assume that the scalar C = 1 and T1 = (x, x0 ), T2 = (y, y 0 ) and T3 = (z, z 0 ), and then the
following equalities hold
U(1, 1, 1) = xyz,

U(2, 2, 1) = x0 y 0 z,

U(2, 1, 1) = x0 yz,

U(2, 1, 2) = x0 yz 0 ,

U(1, 2, 1) = xy 0 z,

U(1, 2, 2) = xy 0 z 0 ,

U(1, 1, 2) = xyz 0 ,

U(2, 2, 2) = x0 y 0 z 0 .

(4)

The unknown entries can be determined uniquely in terms of the 4 observed entires as
U(2, 1, 1)U(1, 2, 1)
,
U(1, 1, 1)
U(2, 1, 1)U(1, 1, 2)
U(2, 1, 2) = x0 yz 0 =
,
U(1, 1, 1)
U(1, 2, 1)U(1, 1, 2)
U(1, 2, 2) = xy 0 z 0 =
,
U(1, 1, 1)
U(2, 1, 1)U(1, 2, 1)U(1, 1, 2)
.
U(2, 2, 2) = x0 y 0 z 0 =
U(1, 1, 1)U(1, 1, 1)

U(2, 2, 1) = x0 y 0 z =

(5)

Therefore, considering the Tucker decomposition, there is only one (finite) completion(s) having this
particular 4 observed entries as above. Note that only given r2 = r3 = 1, it can be verified using Tucker

8

decomposition similarly that the completion is still unique.
III. D ETERMINISTIC C ONDITIONS FOR F INITE C OMPLETABILITY
This section characterizes the connection between the sampling pattern and the number of solutions of
a low-rank tensor completion. In Section III-A, we define a polynomial based on each observed entry.
Then, for a given subset of the rank components we transform the problem of finite completability of U
to the problem of finite completability of the core tensor in the Tucker decomposition of U. In Section
III-B, we propose a geometric analysis on Tucker manifold, by defining a structure for the core tensor
of the Tucker decomposition such that we can determine if two core tensors span the same space. In
Section III-C, we construct a constraint tensor based on the sampling pattern Ω. This tensor is useful
for analyzing the algebraic independency of a subset of polynomials among all defined polynomials. In
Section III-D, we show the relationship between the number of algebraically independent polynomials in
the mentioned set of polynomials and finite completability of the sampled tensor. Finally, Section III-E
characterizes finite completability in terms of the sampling pattern instead of the algebraic variety for the
defined set of polynomials.

A. Condition for Finite Completability Given the Core Tensor
Assume that the sampled tensor is U ∈ Rn1 ×n2 ×···×nd and rank components {rj+1 , . . . , rd } are given,
where j ∈ {1, 2, . . . , d − 1} is an arbitrary fixed number. Without loss of generality assume that rj+1 ≥
. . . ≥ rd throughout the paper. Define P0 as the Lebesgue measure on Rr1 ×r2 ×...×rd and Pi as the Lebesgue
measure on Rr1 ×n1 , i = 1, . . . , d. We assume that U is chosen generically from the manifold corresponding
to rank vector (r1 , . . . , rd ), or in other words, the entries of U are drawn independently with respect to
Lebesgue measure on the corresponding manifold. Hence, any statement that holds for U, it basically
holds for almost every (with probability one) tensor of the same size and Tucker-rank with respect to the
product measure P0 × P1 × . . . × Pd .
Let the dth -order tensor C ∈ Rn1 ×n2 ×···×nj ×rj+1 ×rj+2 ×···×rd be a core tensor of the sampled tensor U ∈
Rn1 ×n2 ×···×nd . Then, there exist full-rank matrices Ti ’s with Ti ∈ Rri ×ni such that
U = C ×di=j+1 Ti ,

(6)

9

or equivalently
U(~x) =

rj+1
X
kj+1 =1

···

rd
X

C(x1 , . . . , xj , kj+1 , . . . , kd )Tj+1 (kj+1 , xj+1 ) . . . Td (kd , xd ).

(7)

kd =1

For notational simplicity, define T = (Tj+1 , . . . , Td ). Figure 1 represents a Tucker decomposition for
a 3rd -order tensor given the second and third components of its rank vector.

n’’	
  
3	
  

r’’	
  

n	
  

n	
  
n’	
  

n”	
  
2	
  

r’	
  

r’’	
  

n’	
  
r’	
  
Fig. 1: Tucker decomposition with j = 1 and d = 3.
Here, we briefly mention some key points to highlight the fundamentals of our proposed analysis.
•

Note 1: As it can be seen from (7), any observed entry U(~x) results in an equation that involves
Πdi=j+1 ri entries of C and also ri entries of Ti , i = j +1, . . . , d. Considering the entries of core tensor
C and tuple T as variables (right-hand side of (7)), each observed entry results in a polynomial in
terms of these variables.

•

Note 2: For any observed entry U(~x), the tuple (x1 , . . . , xj ) specifies the coordinates of the Πdi=j+1 ri
entries of C that are involved in the corresponding polynomial.

•

Note 3: For any observed entry U(~x), the value of xi specifies the column of the ri entries of Ti
that are involved in the corresponding polynomial, i = j + 1, . . . , d.

•

Note 4: Given all observed entries {U(~x) : Ω(~x) = 1}, we are interested in finding the number
of possible solutions in terms of entries of (C, T) (infinite, finite or unique) via investigating the
algebraic independence among these polynomials.

•

Note 5: Note that it can be concluded from Bernstein’s theorem [56, Chapter 3] that in a system of
n polynomials in n variables with each consisting of a given set of monomials, the n polynomials
are algebraically independent with probability one with respect to the corresponding probability
measure, and therefore there exist only finitely many solutions. However, in the structure of the

10

polynomials in our model, the set of involved monomials are different for different set of polynomials,
and therefore to ensure algebraically independency we need to have for any selected subset of the
original n polynomials, the number of involved variables should be more than the number of selected
polynomials.
Given C, we are interested to find a subset of the mentioned polynomials that guarantees tuple T can be
determined finitely. The following definition will be used to determine the number of involved variables
in a set of polynomials.
Definition 1: For any i ∈ {j +1, . . . , d} and nonempty Si ⊆ {1, . . . , ni }, define U (Si ) as a set containing
the locations of the entries of |Si | rows (corresponding to the elements of Si ) of U(i) . Moreover, define
U (Sj+1 ,...,Sd ) = U (Sj+1 ) ∪. . .∪U (Sd ) . Let τ be a subset of the locations of the entries of U. Then, U (Sj+1 ,...,Sd )
is called the minimal hull of τ if any U (Si ) includes exactly only those rows of U(i) that include at least
one of the locations of the entries in τ .
Example 1. Consider a tensor U ∈ R4×4×4 with j = 1, r2 = 2 and r3 = 3. Then we have
U(~x) =

3
2 X
X

C(x1 , k2 , k3 )T2 (k2 , x2 )T3 (k3 , x3 ).

(8)

k2 =1 k3 =1

where C ∈ R4×2×3 , T2 ∈ R2×4 and T3 ∈ R3×4 . Define τ = {(1, 2, 2), (2, 2, 3), (3, 4, 2)}. Hence, Among
the four rows of the second matricization of U, i.e. U(2) , row numbers 2 and 4 include at least one entry
in τ (and row numbers 2 and 3 for U(3) ). Then, for S2 = {2, 4} S3 = {2, 3}, U (S2 ,S3 ) is the minimal hull
of τ . Note that due to the definition, the minimal hull is unique.
Remark 1. Consider any set of polynomials {p1 , . . . , pk } in form of (7). Given the core tensor C these
polynomials are in terms of entries of T and let τ be the set of corresponding entries to these polynomials
in U and U (Sj+1 ,...,Sd ) be the minimal hull of τ . Let S denote the set of all variables (entries of T) that
are involved in at least one of the polynomials {p1 , . . . , pk }. Recall that according to Note 3, if an entry
of Ti is involved in a polynomial, all entries of the column that includes that entry are also involved in
P
that polynomial. Therefore, |S|= di=j+1 |Si |ri .
Note that each observed entry results in a scalar equation of the form of (7). Given the core tensor C,
P
we need at least di=j+1 (ni ri ) polynomials to ensure the number of possible tuples T is not infinite since
P
P
the number of variables (entries of T) is di=j+1 (ni ri ) in total. On the other hand, the di=j+1 (ni ri )
mentioned polynomials should be algebraically independent to ensure the finiteness of tuples T since any

11

algebraically independent polynomial reduces the dimension of the set of solutions by one. To ensure this
P
independency, any subset of t polynomials of the set of polynomials corresponding to the di=j+1 (ni ri )
observed entries, should involve at least t variables. The following assumption will be used frequently as
we show it satisfies the mentioned property.
Assumption Aj : Anywhere that this assumption is stated, there exist

Pd

(ni ri ) observed entries such
P
includes at most di=j+1 |Si |ri

i=j+1

that for any nonempty Si ⊆ {1, . . . , ni } for i ∈ {j + 1, . . . , d}, U (Sj+1 ,...,Sd )
P
of the mentioned di=j+1 (ni ri ) observed entries.

Example 2. Consider a tensor U ∈ R3×3×3 with j = 1, r2 = 1 and r3 = 2. Define the following two sets
P
of observed entries each including di=j+1 (ni ri ) = 9 entries
I1 = {(1, 1, 1), (1, 2, 1), (1, 1, 3), (2, 1, 1), (2, 2, 1), (2, 2, 3), (2, 3, 1), (2, 3, 2), (3, 1, 1)},
I2 = {(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 1, 3), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (3, 3, 3)}.
First, we can show that I1 does not satisfy Assumption A1 . For S2 = {1, 2} and S3 = {1} we have
{(1, 1, 1), (1, 2, 1), (2, 1, 1), (2, 2, 1), (3, 1, 1)} ⊂ U (S2 ,S3 ) .
Hence, U (S2 ,S3 ) includes 5 entries belonging to I1 and

Pd

i=j+1 |Si |ri

= 4 < 5. Therefore, I1 does not

satisfy Assumption A1 since there exists (S2 , S3 ) that violates the mentioned condition.
Second, it is easy to verify that I2 satisfies Assumption A1 by checking all possible pairs (S2 , S3 ).
Remark 2. Assume that each column of U(1) includes at least one observed entry, and also

Pd

i=j+1

(ni ri ) <

nj+1 . . . nd , for some j ∈ {1, . . . , d − 1}. Then, for any tuple (x2 , x3 , . . . , xd ) that xi ∈ {1, . . . , ni }, there
exists at least one observed entry among the set
{(1, x2 , x3 , . . . , xd ), (2, x2 , x3 , . . . , xd ), . . . , (n1 , x2 , x3 , . . . , xd )}.
Hence, there exist

Pd

i=j+1

(9)

(ni ri ) observed entries that satisfy Assumption Aj . This is because all possible

tuples (xj+1 , . . . , xd ) are available to be selected. For example, assuming that each column of U(1) includes
P
P
at least one observed entry and di=2 (ni ri ) < n2 . . . nd , we can choose di=2 (ni ri ) < n2 . . . nd = N−1
observed entries in different columns of U(1) to satisfy Assumption A1 , by choosing either zero or one
observed entry in each column.
Given the core tensor, the following lemma characterizes the necessary and sufficient condition on

12

observed entries that leads to finite completability.
Lemma 1. Assume that in (6) the core tensor C ∈ Rn1 ×···×nj ×rj+1 ×···×rd is given and Ti ∈ Rri ×ni are
variables. Then, for almost every U with probability one, there are at most finitely many possible tuples
T that satisfy (6) if and only if Assumption Aj holds.
(ni ri ) observed entries results in

Pd

(ni ri ) scalar polynomials in terms of entries

of T as in (6)-(7). We claim that any subset of these

Pd

(ni ri ) polynomials with t members involves

Proof. The

Pd

i=j+1

i=j+1
i=j+1

at least t variables in total. Then, by Note 5, the sufficiency holds.
In order to prove the necessity, by contradiction, assume that there exists a subset of polynomials
{p1 , . . . , pt } that involves at most t − 1 variables in total. Let τ be the subset of entries of U that result
in polynomials {p1 , . . . , pt } and denote the minimal hull of τ by U (Sj+1 ,...,Sd ) . Observe that according to
P
Remark 1, di=j+1 |Si |ri ≤ t−1. On the other hand, Assumption Aj results that the number of polynomials
P
P
in {p1 , . . . , pt } is at most di=j+1 |Si |ri , i.e., t ≤ di=j+1 |Si |ri . Hence, we have a contradiction, which
completes the proof of the lemma.
Remark 3. Assumption Aj results that given a core tensor there are finitely many tuples T such that (6)
holds. Consequently, in what follows without loss of generality, we analyze the finite completability of
core tensor C for one particular tuple T among all finitely many tuples.
Pd

(ni ri ) entries of the sampled tensor U are used to determine T, in what follows we will
P
use the polynomials corresponding to the set of the rest NΩ (U) − di=j+1 (ni ri ) observed entries, denoted
Since

i=j+1

by P(Ω), to obtain C. Note that since T is already solved in terms of C, each polynomial in P(Ω) is in
terms of elements of C.

B. Geometry of Tucker Manifold
We need to define the following equivalence class in order to characterize a condition on the sampling
pattern to study the algebraic independency of the polynomials in P(Ω). This equivalence class leads to
a geometric structure for core tensors which specifies exactly one core tensor among all core tensors that
span the same space.
Definition 1. Define an equivalence class for all core tensors C ∈ Rn1 ×n2 ×···×nj ×rj+1 ×···×rd of the sampled
tensor U such that two core tensors C1 and C2 belong to the same class if and only if there exist full rank

13

matrices Di ∈ Rri ×ri , i = j + 1, . . . , d, such that
C2 = C1 ×di=j+1 Di .

(10)

A subtensor Y ∈ Rn1 ×n2 ×···×nj ×1×···×1 of U can be represented by a core tensor C if there exist vectors
θi ∈ Rri ×1 , i = j + 1, . . . , d, such that
Y = C ×di=j+1 θi .

(11)

According to Definition 1, it is easy to verify that two core tensors are in the same class if and only if
one of them can represent each subtensor in Rn1 ×n2 ×···×nj ×1×···×1 of the other one.
e (i) ∈ RNi ×N̄i as the
Definition 2. Let Ni = n1 n2 . . . ni , N̄i = ni+1 ni+2 . . . nd and define the matrix U
¯ (x , . . . , x )), where M̄
e (i) (M̄(i) (x1 , . . . , xi ), M̄
i-th unfolding of the tensor U, such that U(~x) = U
d
(i) i+1
(i)
¯ are two bijective mappings M̄ : (x , . . . , x ) → {1, 2, . . . , N } and M̄
¯ : (x , . . . , x ) →
and M̄
1
i
i
i+1
d
(i)
(i)
(i)
{1, 2, . . . , N̄i }.
We make the following assumption which will be referred to, when it is needed.
P
Assumption Bj : n1 n2 . . . nj ≥ di=j+1 ri .
Consider an arbitrary entry C(~x) of core tensor C. Note that the tuple (xj+1 , . . . , xd ) specifies the column
e (j) . Furthermore, xi specifies the row number of this entry in C(i) . Consequently,
number of this entry in C
e (j) indexed by (xj+1 , . . . , xd ) belongs to the xth row of C(i) for i ≥ j + 1.
each column of C
i
We are interested in providing a structure on the core tensor C such that exactly one core tensor in any
e (j) (j-th unfolding of C).
class satisfies it. We present this structure on C
e (j) such that (i) Pi ∈ Rri ×ri ,
Definition 3. Consider any (d − j) disjoint submatrices1 (Pj+1 , . . . , Pd ) of C
P
e (j) corresponding to rows of these submatrices are disjoint, (iii)
i = j+1, . . . , d, (ii) the di=j+1 ri rows of C
e (j) corresponding to columns of Pi belong to ri disjoint rows of C(i) , i = j + 1, . . . , d.
the ri columns of C
Then, C is said to have a proper structure if Pi = Iri , i = j + 1, . . . , d.
e (j) should
Assumption Bj ensures the existence of a proper structure since the number of rows in C
P
be at least di=j+1 ri . Note that given a proper structure there exists one core tensor in each class that
satisfies it. Moreover, we can permute the rows of Pi ’s and obtain another proper structure. Consider the
1

Specified by a subset of rows and a subset of columns (not necessarily consecutive).

14

following specific structure. Define
ri ×ri
0
,
Pcan
i (x1 , xi ) = C(x1 , 1, . . . , 1, xi , 1, . . . , 1) ∈ R
| {z }
| {z }
i−2

where x01 = x1 −

Pi−1

s=j+1 rs ,

1+

i = j + 1, . . . , d,

(12)

d−i

Pi−1

s=j+1 rs

≤ x1 ≤

Pi

s=j+1 rs

and 1 ≤ xi ≤ ri . It is easily verified all

three properties in Definition 3 are satisfied by Pcan
i , i = j + 1, . . . , d.
Definition 4. (Canonical core tensor) We call C a canonical core tensor if for i ≥ j + 1 we have
= Iri , where Iri is the ri × ri identity matrix.
Pcan
i
Example 3. Assume U ∈ R7×3×4 , j = 1, r2 = 2 and r3 = 3. For simplicity in representing the canonical
¯ (in Definition 2) that result in the structure of
core tensor, we consider bijective mappings M̄(i) and M̄
(i)
e (1) shown in Figure 2(a). Observe that any permutation of rows of C
e (1) results in a proper structure, e.g.,
C
e (1) that satisfy property (iii) in Definition
Figure 2(b). However, only those permutations of columns of C
3 result in a proper structure.
1
0

0
1
1
0
0

0
1
0

0
0
1

(a) Example of canonical core
tensor.

1

0

0

1

1

0

0

0
0

1
0

0
1

(b) A proper structure.

e (1) .
Fig. 2: Two proper structures in C

Note that (10) leads to the fact that the dimension of all core tensors C that span different spaces


  Pd
2
(without any polynomial restrictions in P(Ω)) is equal to Πji=1 ni Πdi=j+1 ri −
r
i=j+1 i , as the
P

d
2
total number of entries of Di ’s is equal to
i=j+1 ri . Moreover, observe that a core tensor with a
P

d
2
proper structure has
r
known entries, and therefore the number of unknown entries is equal
i=j+1 i
P



d
j
d
2
to Πi=1 ni Πi=j+1 ri −
i=j+1 ri .
Remark 4. In order to prove there are finitely many completions for tensor U, it suffices to prove that
there are finitely many canonical core tensors that fit in U.
Suppose C has a proper structure. Let gj+1 (x) denote the maximum number of known entries among

15

e (j) . As will be seen in Section III-C, gj+1 (x) plays an important role in expressing the
any x rows of C
maximum number of algebraically independent polynomials in a subset of P(Ω). Note that in exactly
e (j) there are exactly ri known entries, i.e., entries of Pi , i = j + 1, . . . , d. Also, there are
ri rows of C
Pd
e
i=j+1 ri rows that include known entries in C(j) , i.e., rows of Pi , i = j + 1, . . . , d.
Recall the assumption rj+1 ≥ . . . ≥ rd . Therefore, as long as x ≤ rj+1 , the maximum number of known
e (j) to cover any x rows of Pj+1 . On the other hand,
entries is gj+1 (x) = rj+1 x by selecting the x rows of C
2
if rj+1 ≤ x ≤ rj+1 + rj+2 , the maximum number of known entries is gj+1 (x) = rj+1
+ rj+2 (x − rj+1 ) by

e (j) to cover all rows of Pj+1 and any (x − rj+1 ) rows of Pj+2 . Then, in general
selecting the x rows of C
we have
gj+1 (x) =

d
X
i=j+1

min




ri , x −



i−1
X
i0 =j+1

ri0

!+ 


ri .

(13)



C. Constraint Tensor
In the following, we propose a procedure to construct a (j + 1)th -order binary tensor Ω̆ based on Ω
such that P(Ω̆) = P(Ω). Using Ω̆, we are able to recognize the observed entries that have been used to
obtain the tuple T, and we can easily verify if two polynomials in P(Ω) are in terms of the same set
of variables. Then, in Section III-D, we characterize the relationship between the maximum number of
algebraically independent polynomials in P(Ω̆) and Ω̆.
For any subtensor Y ∈ Rn1 ×n2 ×···×nj ×1×···×1 of the tensor U, there exist row vectors θi ∈ Rri ×1 ,
i = j + 1, . . . , d, such that (11) holds or equivalently
Y(x1 , . . . , xj , ~1d−j ) =

rj+1
X
kj+1 =1

···

rd
X

C(x1 , . . . , xj , kj+1 , . . . , kd )θj+1 (kj+1 , 1) . . . θd (kd , 1),

(14)

kd =1

where ~1d−j is an all-1 (d − j)-dimensional row vector.
For each subtensor Y of the sampled tensor U, let NΩ (Y T ) denote the number of sampled entries in Y
that have been used to obtain the tuple T. Then, Y contributes NΩ (Y) − NΩ (Y T ) polynomial equations
P
in terms of the entries of the core tensor C among all NΩ (U) − di=j+1 (ni ri ) polynomials in P(Ω).
The sampled tensor U includes nj+1 nj+2 · · · nd subtensors that belong to Rn1 ×n2 ×···×nj ×1×···×1 and
we label these subtensors by Y(tj+1 ,...,td ) where (tj+1 , . . . , td ) represents the coordinate of the subtensor.
d−j
z }| {
Define a binary valued tensor Y̆(tj+1 ,···,td ) ∈ Rn1 ×n2 ×···×nj ×1 × . . . × 1 ×k , where k = NΩ (Y(tj+1 ,...,td ) ) −
NΩ (Y(tTj+1 ,...,td ) ) and its entries are described as the following. We can look at Y̆(tj+1 ,···,td ) as k tensors

16

each belongs to Rn1 ×n2 ×···×nj ×1×···×1 . For each of the mentioned k tensors in Y̆(tj+1 ,···,td ) we set the entries
corresponding to the NΩ (Y(tTj+1 ,...,td ) ) observed entries that are used to obtain T in (6) equal to 1. For each
of the other k observed entries, we pick one of the k tensors of Y̆(tj+1 ,···,td ) and set its corresponding entry
(the same location as that specific observed entry) equal to 1 and set the rest of the entries equal to 0.
For the sake of simplicity in notation, we treat tensors Y̆(tj+1 ,···,td ) as a member of Rn1 ×n2 ×···×nj ×k
d−j
z }| {
instead of Rn1 ×n2 ×···×nj ×1 × · · · × 1 ×k . Now, by putting together all nj+1 nj+2 · · · nd tensors in dimension
P
(j + 1), we construct a binary valued tensor Ω̆ ∈ Rn1 ×n2 ×···×nj ×Kj , where Kj = NΩ (U) − di=j+1 (ni ri )
and call it the constraint tensor. In order to shed some light on the above procedure we give an illustrative
example in the following.
Example 4. Consider an example in which d = 3, j = 2, r3 = 2 and U ∈ R3×2×2 . Assume that
Ω(x, y, z) = 1 if (x, y, z) ∈ S and Ω(x, y, z) = 0 otherwise, where
S = {(1, 1, 1), (1, 2, 1), (2, 2, 1), (3, 1, 1), (1, 1, 2), (2, 1, 2), (3, 2, 2)},
T
T
) = 2 and the entries that
) = NΩ (Y(2)
represents the set of observed entries. Also, assume that NΩ (Y(1)

we use to obtain T are (1, 1, 1), (1, 2, 1), (1, 1, 2) and (3, 2, 2). Hence, Y̆(1) ∈ R3×2×1×2 , Y̆(2) ∈ R3×2×1×1 ,
and therefore the constraint tensor Ω̆ belongs to R3×2×3 .
Note that Y̆(1) (1, 1, 1, 1) = Y̆(1) (1, 1, 1, 2) = Y̆(1) (1, 2, 1, 1) = Y̆(1) (1, 2, 1, 2) = 1, and also for the two
other observed entires we have Y̆(1) (2, 2, 1, 1) = 1 and Y̆(1) (3, 1, 1, 2) = 1 and the rest of the entries of
Y̆(1) are equal to zero. Moreover, Y̆(2) (1, 1, 1, 1) = Y̆(2) (2, 1, 1, 1) = Y̆(2) (3, 2, 1, 1) = 1 and the rest of the
entries of Y̆(2) are equal to zero.
Then, Ω̆(x, y, z) = 1 if (x, y, z) ∈ S 0 and Ω̆(x, y, z) = 0 otherwise, where
S̆ = {(1, 1, 1), (1, 2, 1), (2, 2, 1), (1, 1, 2), (1, 2, 2), (3, 1, 2), (1, 1, 3), (3, 2, 3), (2, 1, 3)}.

Note that each subtensor of Ω̆ that belongs to Rn1 ×...×nj ×1 represents one of the polynomials in P(Ω)
besides showing the polynomials that have been used to obtain T. More specifically, consider a subtensor
of Ω̆ that belongs to Rn1 ×...×nj ×1 with l + 1 nonzero entries. Observe that exactly l of them correspond
to the observed entries that have been used to obtain T. Hence, this subtensor represents a polynomial
after replacing entries of T by the expressions in terms of entries of C, i.e., a polynomial in P(Ω).

17

e (j) . Hence, if the
Recall that the tuple (xj+1 , . . . , xd ) specifies the column number of entry C(~x) in C
i-th column of Ω̆(j+1) is nonzero, then there exists a polynomial in P(Ω) that involves all entries of core
e (j) .
tensor corresponding to the entries of the i-th row of C
D. Algebraic Independence
In this subsection, we derive the required number of algebraically independent polynomials in P(Ω) for
finite completability. Then, a sampling pattern on the constraint tensor is proposed to obtain the maximum
number of algebraically independent polynomials in P(Ω̆).
The following lemma determines the required number of algebraically independent polynomials in P(Ω)
that is needed to ensure finite completability of the core tensor.
Lemma 2. Assume that Assumptions Aj and Bj hold. For almost every U, there exist only finitely many

 d
 Pd
j
2
completions of U if and only if there exist Πi=1 ni Πi=j+1 ri −
algebraically independent
i=j+1 ri
polynomials in P(Ω).
Proof. Assume that C ∈ Rn1 ×n2 ×···×nj ×rj+1 ×···×rd is a core tensor for the sampled tensor U. Since assumption Aj holds, Lemma 1 results that there exist finitely many tuples T such that (6) holds. However, according to Remark 3, it suffices to assume T is fixed and then prove the statement. Let P(Ω) = {p1 , . . . , pm }
and define Si as the set of all core tensors that satisfy polynomial restrictions {p1 , . . . , pi }, i = 0, . . . , m
(S0 is the set of all core tensors without any polynomial restriction).
Observe that each algebraically independent polynomial reduces the dimension (degree of freedom) of
the set of solutions by one. In other words, dim(Si ) = dim(Si−1 ) if the maximum number of algebraically
independent polynomials in sets {p1 , . . . , pi } and {p1 , . . . , pi−1 } are the same and dim(Si ) = dim(Si−1 )−1
otherwise. Moreover, with probability one, |Sm | is finite if and only if there are dim(C) = dim(S0 )
algebraically independent polynomial restrictions on the entries of the core tensor C, i.e., |Sm | is finite if
and only if dim(Sm ) = 0 [35]. Hence, there are finitely many completions of the sampled tensor U if and


 Pd
2
only if there exist dim(C) = Πji=1 ni Πdi=j+1 ri −
r
algebraically independent polynomials
i=j+1 i
in P(Ω).
As a result of Lemma 2, we can certify finite completability based on the maximum number of
algebraically independent polynomials in P(Ω) = P(Ω̆).

18

Definition 5. Let Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t be a subtensor of the constraint tensor Ω̆. Let mi (Ω̆0 ) denote the
number of nonzero columns of Ω̆0(i) . Also, let P(Ω̆0 ) denote the set of polynomials that correspond to
nonzero entries of Ω̆0 .
Recall Note 2 regarding the number of involved entries of core tensor in a set of polynomials. However,
as mentioned earlier, some of the entries of C are known, i.e., (Pj+1 , . . . , Pd ). Therefore, in order to find
the number of variables (unknown entries of C) in a set of polynomials, we should subtract the number
of known entries in the corresponding pattern from the total number of involved entries.
For any subtensor Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t of the constraint tensor, the next theorem states an upper bound
on the number of algebraically independent polynomials in the set P(Ω̆0 ). Recall that P(Ω̆0 ) includes
exactly t polynomials.
Theorem 1. Assume that Assumption Bj holds. For any subtensor Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t of the constraint
tensor, the maximum number of algebraically independent polynomials in P(Ω̆0 ) is no more than

Πdi=j+1 ri mj+1 (Ω̆0 ) − gj+1 (mj+1 (Ω̆0 )),

(15)

where gj+1 (·) is given in (13).
Proof. Observe that the number of algebraically independent polynomials in a subset of polynomials of
P(Ω̆0 ) is at most equal to the total number of variables that are involved in the corresponding polynomials.
According to (7), for each observed entry U(~x), we have a polynomial in terms of Πdi=j+1 ri entries of
the core tensor C corresponding to the first j coordinates of the location of the observed entry. Therefore,
the number of such variables in P(Ω̆0 ) will be Πdi=j+1 ri times the number of different tuples (x1 , . . . , xj )
among the corresponding observed entries. The number of nonzero columns of Ω̆0(j+1) is exactly equal
to the number such tuples. Therefore, the number of involved entries of C (known and unknown) in

polynomials in P(Ω̆0 ) is equal to Πdi=j+1 ri mj+1 (Ω̆0 )
Pd
2
e
On the other hand, among the
i=j+1 ri known entries corresponding to (Pj+1 , . . . , Pd ) in C(j) ,
gj+1 (mj+1 (Ω̆0 )) of them are involved in polynomials of P(Ω̆0 ). This is because entries of the i-th row of
e (j) are involved in a polynomials if and only if the i-th column of Ω̆0
C
(j+1) includes at least one nonzero
entry. Hence, the number of variables that are involved in the set of polynomials P(Ω̆0 ) is given by
(15) for a particular proper structure and proof is complete as (15) is an upper bound for the number of
algebraically independent polynomials.

19

We are also interested in finding a condition on Ω̆0 which results that P(Ω̆0 ) is minimally algebraically
dependent, i.e., the polynomials in P(Ω̆0 ) are algebraically dependent but polynomials in every of its
proper subset are algebraically independent. This can help obtain the maximum number of algebraically
independent polynomials in P(Ω̆0 ) as Theorem 1 only provides an upper bound. The next lemma will be
used in Theorem 2 in order to find a condition on Ω̆0 which results that the set of polynomials in P(Ω̆0 )
is minimally algebraically dependent. The following lemma is a re-statement of Lemma 7 in [58].
Lemma 3. Assume that Assumption Bj holds. Suppose that Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t is a subtensor of the
constraint tensor such that P(Ω̆0 ) is minimally algebraically dependent. Then, for almost every U, the
number of variables that are involved in the set of polynomials P(Ω̆0 ) is t − 1.
Finally, the next theorem provides a relationship between the exact number of algebraically independent
polynomials in P(Ω̆) and a geometric property on Ω̆.
Theorem 2. Assume that Assumption Bj holds. The polynomials in the set P(Ω̆) are algebraically depen
dent if and only if Πdi=j+1 ri mj+1 (Ω̆0 ) − gj+1 (mj+1 (Ω̆0 )) < t for some subtensor Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t
of the constraint tensor Ω̆.
Proof. If the polynomials in set P(Ω̆) are algebraically dependent, then there exists a subset of the
polynomials that are minimally algebraically dependent. According to Lemma 3, if Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t
is the corresponding subtensor to this minimally algebraically dependent set of polynomials, the number of variables that are involved in P(Ω̆0 ) = {p1 , , p2 . . . , pt } is equal to t − 1. On the other hand,

Πdi=j+1 ri mj+1 (Ω̆0 ) − gj+1 (mj+1 (Ω̆0 )) is the minimum possible number of involved variables in P(Ω̆0 )
since gj+1 (mj+1 (Ω̆0 )) is the maximum number of known entries of core tensor that are involved in P(Ω̆0 ).

Therefore, Πdi=j+1 ri mj+1 (Ω̆0 ) − gj+1 (mj+1 (Ω̆0 )) ≤ t − 1.

In order to prove the other side of the statement, assume that Πdi=j+1 ri mj+1 (Ω̆0 )−gj+1 (mj+1 (Ω̆0 )) < t
for some subtensor Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t of the constraint tensor Ω̆. Recall that t is the number of

polynomials in P(Ω̆0 ). On the other hand, according to Theorem 1, Πdi=j+1 ri mj+1 (Ω̆0 )−gj+1 (mj+1 (Ω̆0 ))
is the maximum number of algebraically independent polynomials, and therefore the polynomials in P(Ω̆0 )
are not algebraically independent and it completes the proof.

20

E. Finite Completability Using Analysis on Tucker Manifold
Theorem 2 together with Lemma 2 can lead to a necessary and sufficient condition on the constraint
tensor Ω̆ in order to ensure that there are finitely many completions for the sampled tensor U, as stated
by the next theorem.
Theorem 3. Assume that Assumptions Aj and Bj hold. Then, for almost every U, there are only finitely
many tensors that fit in the sampled tensor U, and have tensor rank components ri for i = j + 1, . . . , d
if and only if the following two conditions hold:
(i) there exists a subtensor Ω̆0 ∈ Rn1 ×n2 ×···×nj ×n of the constraint tensor such that n = Πji=1 ni
P

d
2
i=j+1 ri , and




Πdi=j+1 ri −

(ii) for any t ∈ {1, . . . , n} and any subtensor Ω̆00 ∈ Rn1 ×n2 ×···×nj ×t of the tensor Ω̆0 (in condition (i)),
the following inequality holds

Πdi=j+1 ri mj+1 (Ω̆00 ) − gj+1 (mj+1 (Ω̆00 )) ≥ t.

(16)

Proof. According to Lemma 2, for almost every U, there are finitely many completions of U if and only

 Pd

2
algebraically independent polynomials in P(Ω̆). On the
r
if there exist Πji=1 ni Πdi=j+1 ri −
i=j+1 i
other hand, according to Theorem 2 we conclude that a set of polynomials are algebraically independent
if and only if condition (ii) in the statement of the theorem holds. Hence, for almost every U, there are
finitely many completions of U if and only if conditions (i) and (ii) hold.
There are a few observations based on Theorem 3:
•

In theorem 3, we characterize all of the sampling patterns that ensure there are only finitely many
completions such that if only one single sample from that pattern is missed, then there are infinitely
many completions.

•

If we use the Grassmannian analysis on each dimension individually, we will only obtain a sufficient
condition on the sampling patterns for finite completability, given multiple rank constraints. However,
our proposed analysis on Tucker manifold results in a necessary and sufficient condition on the
sampling patterns for finite completability when multiple rank components are given. Hence, our
proposed analysis on Tucker manifold in general requires much less number of of samples to ensure
finite completability in comparison with the analysis on Grassmannian manifold when more than one
rank component is given.

21

•

It is also important to observe the advantage of the proposed method as we decrease the value
of j since we are incorporating more rank components. Intuitively, for the case of j = 1, the
polynomials obtained in (6) involve much more variables in comparison with the low-order analysis
on Grassmannian manifold, i.e., j = d − 1. Therefore, the case of j = 1 requires much less number
of samples in order to have sufficient number of algebraically independent polynomials for finite
completability.

•

Note that our analysis is not valid when j = 0 (given all rank components) since the defined proper
structure does not have meaning any more as zero unfolding does not exist, and therefore we are not
able to characterize the necessary and sufficient condition on sampling pattern for finite completability.
However, if all rank components are given we can simply ignore one of them and characterize the
necessary and sufficient condition for j = 1 which results in a sufficient condition for j = 0.

If the number of completions given (rj+1 , . . . , rd ) is finite, it can be concluded that the number of
completions given (rj , . . . , rd ) is finite as well. Therefore, this property should be verifiable through the
geometric property (16) proposed in Theorem 3. In the following lemma, using the pigeonhole principle,
we show this result without analyzing the algebraic variety.
Lemma 4. Assume that Assumptions Aj , Bj , Aj−1 and Bj−1 hold. Suppose that the sampling pattern is
such that the properties (i) and (ii) in the statement of Theorem 3 hold for j. Then, the properties (i) and
(ii) in the statement of Theorem 3 hold for j − 1.
Proof. The proof is given in Appendix A.
IV. P ROBABILISTIC C ONDITIONS FOR F INITE C OMPLETABILITY
In this section, two different lower bounds on the sampling probability are proposed and analyzed to
ensure finite completability. The first bound is obtained by applying [35, Theorem 3] and the second
bound is obtained through the proposed geometric approach in Theorem 3. We will observe later that our
proposed analysis on Tucker manifold leads to a better lower bound through numerical analysis.
Here we briefly outline the key steps of the second approach. Lemmas 6 and 7 each provides a lower
bound on the sampling probability that results in a geometric property for Ω, i.e., inequalities (20) and
(27), respectively. Then, Theorem 5 takes advantage of the above lemmas to propose a bound on the
sampling probability to guarantee property (16) for Ω. Finally, Lemma 8 shows that (16) also holds for

22

the constraint tensor Ω̆. In order to show Lemma 8 we develop a generalization of Hall’s Theorem on
bipartite graphs in Theorem 6.
We use the approach similar to [35, Lemma 9] in order to apply Theorem 3 and obtain a lower bound
on the sampling probability to ensure that there are only finitely many completions. According to our
earlier discussion, Theorem 3 for the case of j = 1 results in the mildest condition on the sampling
patterns for ensuring finite completability. In other words, setting j = 1 in Theorem 3 results in a tighter
lower bound.

A. Lower Bound on Sampling Probability based on Analysis on Grassmannian Manifold
We first state a lemma, whose corollary (Corollary 1) is used extensively in this section in order to find
a lower bound on the sampling probability to guarantee a lower bound on the number of sampled entries
with high probability.
Lemma 5. Consider a vector with ni entries and assume each entry is observed with probability p and
ni
1
independently from the other entries. Then, with probability at least 1 − exp(− 2c
2 ) at least (p − c )ni

entries are observed.
Proof. Azuma’s inequality states that for a martingale {Xk : k = 0, 1, 2, ...} that |Xk − Xk−1 |≤ 1 holds,
 2
 2
−t
and
P
(E[X
]
−
X
>
t)
≤
exp
[59]. Therefore, using
we have P (Xn − E[Xn ] > t) ≤ exp −t
n
n
2n
2n
Azuma’s inequality and the fact that sampling has Bernoulli distribution with parameter p, it can be seen
2

t
) the number of observed entries is less than ni p − t. Now, by
that with probability at most exp(− 2n
i

setting t equal to

ni
c

the proof is complete.

Corollary 1. Consider a vector with ni entries where each entry is observed with probability p inde

√
ni
2ri
1
0
√
pendently from the other entries. If p > p = ni + 4 , with probability at least 1 − exp(− 2 ) ,
ni
en
12 log(  i )
1
, with probability at least
more than 2ri entries are observed. Similarly, if p > p00 =
+ √
4
ni
ni


√
n
1 − exp(− 2 i ) , more than 12 log( en i ) entries are observed.
Proof. Both parts follow by setting c =

√
4

ni in Lemma 5.

The following theorem uses the matrix result for single rank constraint and provides a sufficient condition
on the sampling pattern for finite completabilitily of tensor. We will assume that
ri ≤

ni
,
6

N−i ≥ ri (ni − ri )

for i = 1, 2, . . . , d.

(17)

23

Theorem 4. Consider a randomly sampled tensor U with Tucker rank (r1 , · · · , rd ). Suppose that the
inequalities in (17) hold. Moreover, assume that the sampling probability satisfies




1
2ri 12 log( en i )
,
+√
.
p > min max
4
1≤i≤d
ni
ni
ni

(18)

Then, there are only finitely many completions of the sampled tensor U with the given rank vector with
probability at least (1 − 2).



eni 
2ri 12 log(  )
1
Proof. Denote ` = arg min1≤i≤d max ni ,
+ √
. By (18) and using Corollary 1, with
4
ni
ni
probability almost one the number of observed entries at each column of U(`) is at least max{2r` , 12 log( en ` )}.
Then, with (17) and using [35, Theorem 3], it follows that there are finitely many matrix completions
for the observed entries of U(`) with rank r` . As a result, there are finitely many tensors with the `-th
component of rank being r` that agree with the observed entries. The proof is complete since the set of
tensors that are a completion with the rank vector (r1 , . . . , rd ) is a subset of the set of tensors whose
finiteness is shown above.

B. Lower Bound on Sampling Probability based on Analysis on Tucker Manifold
We are interested in taking advantage of Theorem 3 to obtain another lower bound on the sampling
probability for finite completability. We assume j = 1, and therefore the constraint tensor Ω̆ is a secondorder tensor, i.e., an n1 × K1 matrix.
Lemma 6. Consider an arbitrary set Ω0(1) of n1 − 1 columns of Ω(1) (first matricization of Ω). Assume
that each column of Ω(1) includes at least l nonzero entries, where
 
k
l > 6 log (n1 ) + 2 log
+ 4.


(19)

Then, with probability at least 1 − k , every subset Ω00(1) of columns of Ω0(1) satisfies
m2 (Ω00(1) ) − 1 ≥ t,

(20)

where t is the number of columns of Ω00(1) and m2 (Ω00(1) ) is the number of nonzero rows of Ω00(1) (observe
that second matricization of a matrix is its transpose).
Proof. The proof is similar to the proof of [35, Lemma 9] with some delicate modifications to improve

24

the result for this case. Note that (19) can be rewritten as

n1 k
+ 4 log(n1 ) + 4
l > 2 log



n1 e2 k
> log
+ 2.



(21)
(22)

Define E as the event that for some submatrix Ω00(1) ∈ Rn1 ×t of the matrix Ω0(1) (20) does not hold. We
are interested in finding an upper bound on the probability of E. Then, from the proof of [35, Lemma 9]
and by setting r = 1 in inequalities (12) and (13) in [35], we have
n1

P (E) <

2  ln1
2 
X
n1
n
n=l

n

n1

n1

2 
l(n1 −n)
2 
X
n1
n1 − n
+
.
n1 − n
n1
n=1

(23)

Note that
 
 q
s
s(s − 1) . . . (s − q + 1)
sq
se
=
≤
≤
,
q
q!
q!
q
where the last inequality holds since eq =

qi
i=0 i!

P∞

≤

qq
.
q!

(24)

Applying (24) to each term of the first summation

of (23) we obtain
 (l−2)n
 2  ln1
n
n1
n
n

2n
,
<e
≤ e2 2−l+2 <
n
n1
n1
n1 k

(25)

where the last inequality follows from (22). This directly results that the first summation in (23) is less
than


.
2k

Moreover, again by applying (24) to each term of the second summation in (23) we obtain


n1
n1 − n

2 

n1 − n
n1

l(n1 −n)

 2 
l(n1 −n)

 ln1
n1
n1 − n
n1 − n 2
2n
=
< (n1 e)
n
n1
n1

n
ln
l

≤(n1 e)2n e− 2 = e2 log n1 +2− 2 <
,
n1 k

(26)

where the last inequality follows from (21). This directly results that the second summation in (23) is less
than


2k

and that completes the proof.

Lemma 7. Consider an arbitrary set Ω0(1) of n1 columns of Ω(1) (first matricization of Ω). Assume that

each column of Ω(1) includes at least l nonzero entries, where l > 6 log (n1 ) + 2 log 2k + 4. Then, with

25


,
2k

probability at least 1 −

every subset Ω00(1) of columns of Ω0(1) satisfies
m2 (Ω00(1) ) ≥ t,

(27)

where t is the number of columns of Ω00(1) and m2 (Ω00(1) ) is the number of nonzero rows of Ω00(1) .
Proof. By setting r = 0 in inequalities (12) and (13) in [35], we have
n1

P (E) <

2  l(n1 +1)
2 
X
n1
n
n=l

n

n1

n1

2 
l(n1 −n+1)
2 
X
n1
n1 − n
+
.
n1 − n
n1
n=1

Since n < n1 it then follows that P (E) < RHS of (28) < RHS of (23) <


,
2k

(28)

where the last inequality

follows from Lemma 6.
The next theorem gives a lower bound on the number of needed samples to ensure finite completability
for tensor U. More specifically, we show under some mild assumptions if (29) holds, all conditions and
assumptions in the statement of Theorem 3 hold with high probability, and therefore the tensor is finitely
completable.
Theorem 5. Assume that

Pd

i=2

(ni ri ) < n2 . . . nd ,

Pd

2
i=2 ri

≤ Πdi=2 ri , Πdi=2 ni ≥ n1 Πdi=2 ri −

Pd

2
i=2 ri ,

and

Assumption B1 hold. Furthermore, assume that each column of U(1) includes at least l observed entries,
where
(
l > 6 log (n1 ) + 2 max log

2

Pd

2
i=2 ri



!
, log

2Πdi=2 ri

−2


Pd

2
i=2 ri

!)
+ 4.

(29)

Then, with probability at least 1 − , there exist only finitely many completions, given the rank components
r2 , . . . , rd .
Proof. Since each column of Ω(1) includes at least one nonzero entry, there exist

Pd

i=2

ni ri entries in

different columns such that they satisfy Assumption A1 (as mentioned in Remark 2). Also, Ω(1) has
P
Πdi=2 ni columns and by assumption Πdi=2 ni ≥ n1 Πdi=2 ri − di=2 ri2 , therefore there exist Πdi=2 ri disjoint
P
sets S1 , . . . , SΠdi=2 ri such that each S` consists of n1 − 1 columns of Ω(1) for 1 ≤ ` ≤ di=2 ri2 and each
P
S` consists of n1 columns of Ω(1) for di=2 ri2 + 1 ≤ ` ≤ Πdi=2 ri .
 Pd 2 
Pd 2
2 i=2 ri
+
4.
Using
Lemma
6,
with
k
=
2
Note that by (29), we have l > 6 log (n1 ) + 2 log
i=2 ri ,

Pd 2
for each 1 ≤ ` ≤ i=2 ri , with probability at least 1 − 2 Pd r2 , (20) holds for every subset of columns of
i=2 i
P

S` . Hence, with probability at least 1− 2 , (20) holds for every subset of columns of S` for 1 ≤ ` ≤ di=2 ri2 ,

26

simultaneously. According to Remark 7 and Lemma 8 below and by setting r = 1, as a subset of columns
S` of Ω(1) satisfies (20), there exist a subset of columns S̆` of the constraint matrix Ω̆ (corresponding
Pd
P
r2
columns to the columns of S` ) that satisfies (20) as well, for 1 ≤ ` ≤ di=2 ri2 . Denote S̆ (0) = ∪`=1i=2 i S̆` .
Consider any subset of columns of S̆ (0) and denote it by S̆ 0 . Let S̆`0 denote the columns of S̆ 0 that
0
belong in S̆` and, without loss of generality, assume that |S̆10 |≥ · · · ≥ |S̆P
d

2
i=2 ri

|, where |S̆`0 | denotes the

number of columns of S̆`0 . As a result, we obtain
Pd

2

i=2 ri
X

|S̆ 0 |=

d
X

|S̆`0 |≤

!

d
X

|S̆10 |≤

ri2

i=2

`=1

!
ri2 (m2 (S̆10 ) − 1) ≤

i=2

d
X

!
ri2 (m2 (S̆ 0 ) − 1),

(30)

i=2

and consequently
d
X

0

|S̆ |≤

!
0

ri2

m2 (S̆ ) −

i=2

d
X

ri2 ,

∀ S̆ 0 ⊆ S̆ (0) .

(31)

i=2

 d

P
2Πi=2 ri −2 di=2 ri2
+ 4. Using Lemma 7, with
Moreover, by (29), we have l > 6 log (n1 ) + 2 log

P
P
k = 2Πdi=2 ri − 2 di=2 ri2 , for each di=2 ri2 + 1 ≤ ` ≤ Πdi=2 ri , with probability at least 1 − 2Πd r −2 Pd r2 ,
i=2 i

i=2 i


,
2

(27) holds for every subset of columns of S` . As a result, with probability at least 1 − (27) holds for
P
every subset of columns of S` for di=2 ri2 + 1 ≤ ` ≤ Πdi=2 ri , simultaneously. According to Remark 7 and
Lemma 8 below and by setting r = 0, as a subset of columns S` of Ω(1) satisfies (27), the corresponding
P
subset of columns S̆` of the constraint matrix Ω̆ satisfies (27) as well, di=2 ri2 + 1 ≤ ` ≤ Πdi=2 ri . Denote
Πd

r

i
Pd
S̆ (1) = ∪`=i=2

2
i=2 ri +1

S̆` . Similarly, we have
|S̆ 0 |≤

Πdi=2 ri −

d
X

!
ri2 m2 (S̆ 0 ),

∀ S̆ 0 ⊆ S̆ (1) .

(32)

i=2
0

0

For any subset of columns Ω̆00 of Ω̆0 = S̆ (0) ∪ S̆ (1) we define S̆ (0) and S̆ (1) as the set of columns of Ω̆00
PΠdi=2 ri
P
that belong to S̆ (0) and S̆ (1) , respectively. Observe that as Ω̆0 has exactly i=1
|Si |= n1 Πdi=2 ri − di=2 ri2
columns, condition (i) of Theorem 3 for j = 1 is satisfied. Then, by (31), (32) and the assumption that
Pd 2
d
00
00
i=2 ri ≤ Πi=2 ri , we have (recall |Ω̆ | denotes the number of columns of Ω̆ here)
|Ω̆00 |=|S̆

(0)0

|+|S̆

(1)0

|≤

d
X

!
ri2 m2 (S̆

i=2

≤

Πdi=2 ri



00

m2 (Ω̆ ) −

d
X

(0)0

)−

d
X
i=2

ri2 +

Πdi=2 ri −

d
X

!
0

ri2 m2 (S̆ (1) )

(33)

i=2


ri2 ≤ Πdi=2 ri m2 (Ω̆00 ) − g2 (m2 (Ω̆00 )).

i=2

Therefore, any subset of columns of Ω̆0 satisfies (16) (condition (ii) of Theorem 3 for j = 1), with

27

probability at least 1 − . Then, according to Theorem 3, with probability at least 1 − , there are only
finitely many completions that fit in the sampled tensor U, given the rank components r2 , . . . , rd .
Remark 5. In the case that only a subset of rank components are given, e.g, rj+1 , . . . , rd , we can treat the
first j dimensions of the tensor as one single dimension, and therefore the above result is still applicable.
e (j) (j-th unfolding) includes at least l observed entries, where
In particular, assume that each column of U
(recall Nj = n1 . . . nj )
(
l > 6 log (Nj ) + 2 max log
Given that

Pd

2

Pd

2
i=j+1 ri



!
, log

2Πdi=j+1 ri − 2


d
d
d
2
i=j+1 ri ≤ Πi=j+1 ri , Πi=j+1 ni ≥ Nj Πi=j+1 ri −

Pd

2
i=j+1 ri ,

Pd

2
i=j+1 ri

!)
+ 4.

(34)

and Assumption Bj hold, with

probability at least 1−, there exist only finitely many completions, given the rank components rj+1 , . . . , rd .

Remark 6. Assume that there exist only finitely many completions, given the rank components rj+1 , . . . , rd ,
where j ≥ 1. Then, there exist only finitely many completions of rank (r1 , . . . , rd ).
As in the proof of Theorem 5 we referred to Lemma 8, we need to show that if a subset of columns of
Ω(1) satisfies (20) or (27), the same property holds for a corresponding subset of columns of the constraint
matrix Ω̆.
Remark 7. Recall that for each column of Ω(1) that has k + r nonzero entries and r of them have been
used to obtain T, there exist k columns in the constraint matrix Ω̆, each with exactly r +1 nonzero entries.
P
Recall that as we showed after stating Assumption Aj , we can choose di=2 ni ri nonzero entries of
Ω(1) to obtain T, i.e., to satisfy Assumption A1 such that in each column of Ω(1) either we choose one or
zero nonzero entry. In that case, each column of Ω̆ includes 0 + 1 or 1 + 1 nonzero entries. As a result,
in the proof of Theorem 5, we only need Lemma 8 for r = 0 and r = 1. However the general statement
is needed to complete a proof in [35], as we explain in Remark 9.
Consequently, the matrix Ω̆0 defined in Lemma 8 for r = 0 and r = 1 corresponds to the columns of
the constraint matrix Ω̆.
Lemma 8. Let r be a given nonnegative integer. Assume that there exists an n1 × (n1 − r) matrix Ω0
composed of n1 − r columns of Ω(1) such that each column of Ω0 includes at least r + 1 nonzero entries

28

and satisfies the following property:2
•

Denote an n1 × t matrix (for any 1 ≤ t ≤ n1 − r) composed of any t columns of Ω0 by Ω00 . Then
m2 (Ω00 ) − r ≥ t,

(35)

where m2 (Ω00 ) is the number of nonzero rows of Ω00 .
Then, there exists an n1 × (n1 − r) matrix Ω̆0 such that: each column has exactly r + 1 entries equal to
one, and if Ω̆0 (x, y) = 1 then we have Ω0 (x, y) = 1. Moreover, Ω̆0 satisfies the above-mentioned property.
Proof. Let Ω0 denote a n1 × (n1 − r) matrix that consists of n1 − r columns of Ω(1) and satisfies the
mentioned property in the statement of the lemma. Note that the given property in the statement of the
lemma is equivalent to the following statement
•

The matrix obtained by choosing any subset of the columns of Ω0 includes at least r + t nonzero
rows, where t is the number of the selected columns of Ω0 .

Consider a bipartite graph G with the two sets of nodes T1 with n1 − r nodes corresponding to the
columns and T2 with n1 nodes corresponding to the rows. We add an edge between the i-th node of T1
and the i0 -th node of T2 if and only if the (i, i0 )-th entry of Ω0 is equal to one. For a set of nodes S, let
N (S) denote the set of their neighbors. Note that according to the assumption, any subset of the columns
of Ω0 includes at least r + t nonzero rows (r + t edges in the defined graph), where t is the number of
the selected columns of Ωτ . Therefore, every subset of nodes of T1 has the following property
N (S) ≥ |S|+r.

(36)

The statement of the lemma is equivalent to proving that there exists a spanning subgraph G 0 of G such
that every node of T1 is of degree r + 1, and also for each subset of nodes of T1 , (36) holds in G 0 .
First consider the scenario that r = 0. Then, according to Hall’s theorem [60], there is a perfect matching
(since inequality (36) holds). Observe that a perfect matching in the described graph is exactly equivalent
to what we are looking for when r = 0. For other values of r > 0, the proof is a direct result of Theorem
6 which is a generalization of the Hall’s theorem. An example of such spanning subgraph for a graph
with n1 = 6 and r = 1 is shown in Figure 3. In Figure 3(a) a bipartite graph is given such that (36) holds
for r = 1. Figure 3(b) gives an spanning subgraph of the given graph in Figure 3(a) such that degree of
each node in T1 is equal to 2 and still (36) holds for r = 1.
2

This property is exactly property (ii) in [35].

29

(a) The original graph.

(b) The spanning subgraph.

Fig. 3: An example of the corresponding bipartite graph with r = 1 and n1 = 6.

Theorem 6. (Generalized Hall’s Theorem) Consider a bipartite graph G with two sets of nodes, T1 with
x nodes and T2 with x + r nodes, where x, r ∈ N. Suppose that for each subset S of T1 the following
inequality holds
|N (S)|≥ |S|+r.

(37)

Then, there exists a spanning subgraph G 0 of G such that every node of T1 is of degree r + 1, and also
for each subset of nodes of T1 , the inequality (37) holds in G 0 as well.
Proof. The proof is given in Appendix B.
Corollary 2. Assume that

Pd

2
i=j+1 ri

≤ Πdi=j+1 ri , Πdi=j+1 ni ≥ Nj Πdi=j+1 ri −

Pd

2
i=j+1 ri ,

and Assumption

Bj hold. Furthermore, assume that we observe each entry of U with probability p, where
( Pd
)!
!
P
2 i=j+1 ri2 2Πdi=j+1 ri − 2 di=j+1 ri2
1
1
p>
6 log (Nj ) + 2 log max
,
+4 + p
.
4
Nj


Nj

(38)

Then, with probability at least 1 − 2, there are only finitely many completions for U, given the rank
components rj+1 , . . . , rd .
Proof. The proof is straightforward given Theorem 5 and Corollary 1.
Remark 8. In Theorem 4 which is obtained by applying the analysis in [35], the number of needed
samples per column of the i-th matricization to guarantee finite completability with high probability is on the order of O(max{log(ni ), ri }). Therefore, the number of needed samples in total is on
the order of O(N−i max{log(ni ), ri }). On the other hand, in Theorem 5 for the case of d > 2 (or-

30

der of the tensor is at least 3), the number of needed samples per column for the i-th unfolding becomes O(max{log(Ni ), log(ri+1 . . . rd )}), and the number of needed samples in total is on the order of
O( NNi max{log(Ni ), log(ri+1 . . . rd )}), if ri+1 . . . rd <

N
.
Ni 2

As an example, consider the case that ni = n, i = 1, . . . , d. Also, assume that ri = r, i = j + 1, . . . , d,
√
where r ≤ n. The matricization analysis requires O(nd−1 max{log(n), r}) samples for any j. However,
according to Theorem 5, if j =

d
3

2d

d

it requires O(n 3 log(n 3 )) samples for finite completability. Note that

under the assumption rj+1 . . . rd < NNj 2 , i.e., rd−j < nd−2j , j =
√
r = n since increasing j violates the assumption.

d
3

results in the best possible bound as

Remark 9. We note that the proof in [35, Theorem 3] is incomplete and Lemma 8 is needed to complete
that proof.
First, observe that sampling pattern matrix Ω represents the observed entries and it has at least l nonzero
elements per column. On the other hand, Ω̆ represents the constraint matrix defined in [35] and it has
exactly (r + 1) nonzero elements per column, where r is the given rank.
Secondly, observe that in [35, Lemma 1] each Ω̂τ is a subset of the constraint matrix Ω̆ (not a subset
of Ω).
Finally, in the proof and statement of [35, Lemma 9] the authors consider a subset of Ω. However, in
the proof of [35, Theorem 3] they refer to [35, Lemma 1], which considers the columns as the subsets of
Ω̆. Now, considering Ω̆ instead of Ω in [35, Lemma 9], the equation below the equation (11) in [35] does
not hold. This is because the assumption right below equation (11) in [35] that Ω̆ has at least l nonzero
elements per column is incorrect (this is a property of Ω but not necessarily Ω̆).
As a result, a part of the proof in [35, Theorem 3] is missing which is Lemma 8 in this paper.
V. D ETERMINISTIC AND P ROBABILISTIC G UARANTEES FOR U NIQUE C OMPLETABILITY
In this section, we first provide an example with exactly two completions to emphasize that finite
completability does not necessarily result in unique completability. Then, we provide the conditions on
the sampling pattern to guarantee unique completability.
Example 5. Assume that the sampled matrix U ∈ R5×4 is given as the incomplete matrix on the left
below:

31

1

1

−4

2

0

1

1

− 12

−1
2
4

4

−2

3
2

⇒

1

− 21
32

1

− 21

1

−2

1

− 21

−4

2

−1

3
4

−4

2

−1

−10

0

1

- 24
5

2

0

1

- 12

2

1

− 41
32

4

− 47

1

−8

4

− 25
2

−8

4

−2

3
2

39
− 21

4

−2

3
2

and

Moreover, assume that rank(U) = 2. In Appendix C, it is shown that there exist exactly two completions
of U as given by the two complete matrices on the right.
The following assumptions is a stronger version of Assumption Aj to ensure that there exists only one
tuple T given the core tensor.
Assumption A+
j : Anywhere that this assumption is stated, there exist

Pd

such that for any Si ⊆ {1, . . . , ni } for i ∈ {j + 1, . . . , d}, U (Sj+1 ,...,Sd )
P
of the mentioned di=j+1 (ni (ri + 1)) observed entries.

(ni (ri + 1)) observed entries
P
includes at most di=j+1 |Si |(ri + 1)
i=j+1

Remark 10. In Lemma 1 we showed that Assumption Aj results that tuple T can be determined finitely.
Pd
Note that Assumption A+
j implies Assumption Aj and therefore using only
i=j+1 (ni ri ) of the observed
entries tuple T can be determined finitely. Moreover, observe that the rest of the sampled entries result
in a set of polynomials that involve any of variables at least once and according to Note 5, tuple T can
be determined uniquely, with probability one.
The following lemma is a re-statement of Lemma 25 in [58] (also an adaptation of Lemma 7 in [35])
and gives the conditions under which a subset of entries of the core tensor C can be determined uniquely.
Lemma 9. Assume that Assumption Bj holds. Suppose that Ω̆0 ∈ Rn1 ×n2 ×···×nj ×t is a subtensor of the
constraint tensor such that P(Ω̆0 ) is minimally algebraically dependent. Then, for almost every U, all
variables that are involved in the set of polynomials P(Ω̆0 ) can be uniquely determined.
Proof. According to Lemma 3, the number of involved variables in polynomials in P(Ω̆0 ) = {p1 , p2 , . . . , pt }
is t − 1 and are denoted by {x1 , . . . , xt−1 }. Moreover, as mentioned in the proof of Lemma 3, P(Ω̆0 )\pi is
a set of algebraically independent polynomials and the number of involved variables is t − 1, i = 1, . . . , t.
Consider an arbitrary variable x1 that is involved in polynomials in P(Ω̆0 ) and without loss of generality,
assume that x1 is involved in p1 .
On the other hand, as mentioned all variables {x1 , . . . , xt−1 } are involved in algebraically independent
polynomials in P(Ω̆0 )\p1 . Hence, according to Note 5, tuple (x1 , . . . , xt−1 ) can be determined finitely.

32

Given that one of these finitely many tuples (x1 , . . . , xt−1 ) satisfy polynomial equation p1 , according to
Note 5, with probability one there does not exist another tuple (x1 , . . . , xt−1 ) among them that satisfies
polynomial equation p1 . This is because with probability zero a tuple satisfy a polynomial equation in
which the coefficients are chosen generically, and also the fact that the number of such tuples is finite.
The next theorem provides two conditions on the sampling pattern to ensure unique completability.
The first one is as the same as the condition proposed in Theorem 3 for finite completability. The second
condition takes advantage of finite completability and leads to the unique core tensor.
Theorem 7. Suppose that assumptions A+
j and Bj hold. Also, assume that there exist two disjoint
subtensors Ω̆0 ∈ Rn1 ×n2 ×···×nj ×n and Ω̆00 ∈ Rn1 ×n2 ×···×nj ×n0 of the constraint tensor such that n =
Pd

2
 d
 Pd

j
j
i=j+1 ri
2
c with the following conditions:
Πi=1 ni Πi=j+1 ri −
r
and
n
=
Π
n
−
b
0
i
d
i=1
i=j+1 i
Π
ri
i=j+1

00

n1 ×n2 ×···×nj ×t

(i) For any t ∈ {1, . . . , n} and any subtensor Ω̆ ∈ R

of the tensor Ω̆0 , the following

inequality holds

Πdi=j+1 ri mj+1 (Ω̆00 ) − gj+1 (mj+1 (Ω̆00 )) ≥ t.

(39)

0

(ii) For any t0 ∈ {1, . . . , n0 } and any subtensor Ω̆000 ∈ Rn1 ×n2 ×···×nj ×t of the tensor Ω̆00 , the following
inequality holds
Πdi=j+1 ri mj+1 (Ω̆000 ) − gj+1 (mj+1 (Ω̆000 )) ≥ Πdi=j+1 ri t0 −




d
X

!
+

ri2 (t0 − n0 + 1) .

(40)

i=j+1

Then, for almost every U with probability one, there exists exactly one tensor that fits in the sampled
tensor, and also rank(U(i) ) = ri , i = j + 1, . . . , d. Therefore there is a unique completion of the sampled
tensor with rank of (r1 , r2 , . . . , rd ).
Proof. As mentioned Assumption A+
j results that T can be determined uniquely. In order to complete the
proof it suffices to show the core tensor C can be determined uniquely as well. As defined earlier, P(Ω̆0 )
and P(Ω̆00 ) denote the set of polynomials obtained from the sampled entries corresponding to Ω̆0 and Ω̆00 ,
respectively. According to Theorem 3, P(Ω̆0 ) results in finite completability of the sampled tensor U, and
also n algebraically independent polynomials. Hence, adding any of the polynomials in P(Ω̆00 ) to P(Ω̆0 )
results in an algebraically dependent set of polynomials. Using n algebraically independent polynomials
in P(Ω̆0 ) and polynomials in P(Ω̆00 ), we show all entries of core tensor can be determined uniquely.
Let p0 denote an arbitrary polynomial in P(Ω̆00 ). Consider P 0 (p0 ) ⊂ P(Ω̆0 ) such that P 0 (p0 ) ∪ p0 is a

33

minimally algebraically dependent set of polynomials. Let tuple (x1 , . . . , xj ) denote the first j coordinates
of the corresponding observed entry to polynomial p0 . Then, according to Note 2, all Πdi=j+1 ri entries of
core tensor C with the first j coordinates as (x1 , . . . , xj ) are involved in polynomial p0 , and therefore they
can be determined uniquely, according to Lemma 9. However, a subset of these Πdi=j+1 ri entries of core
tensor may be the elements of the proper structure which are known entries.
0

Similarly, repeating this procedure for any subtensor Ω̆000 ∈ Rn1 ×n2 ×···×nj ×t of the tensor Ω̆00 results in


Πdi=j+1 ri t0 polynomials in terms of the Πdi=j+1 ri mj+1 (Ω̆000 ) − gj+1 (mj+1 (Ω̆000 )) unknown entries of the
core tensor. Observe that according to Note 5, these polynomials are algebraically independent if


Πdi=j+1 ri mj+1 (Ω̆000 ) − gj+1 (mj+1 (Ω̆000 )) ≥ Πdi=j+1 ri t0 ,

(41)



0
for any subtensor Ω̆000 ∈ Rn1 ×n2 ×···×nj ×t of the tensor Ω̆00 . In order to include dim(C) = Πji=1 ni Πdi=j+1 ri −

P
d
2
algebraically independent polynomials, Ω̆00 should include at least n0 columns otherwise
r
i=j+1 i

0
for any subtensor Ω̆000 ∈ Rn1 ×n2 ×···×nj ×t of the tensor Ω̆00 we have dim(C) > Πdi=j+1 ri t0 since t0 < n0 .
Therefore, inequality (40) results that all n variables (unknown entries) of the core tensor can be determined
uniquely.
We are also interested to obtain a lower bound on the sampling probability, which ensures the unique
completability. The following lemma leads to Lemma 11 that characterizes the number of required sampled
entries to ensure the unique completability with high probability.
Lemma 10. Consider an arbitrary set Ω0(1) of n1 columns of Ω(1) (first matricization of Ω). Assume that

each column of Ω(1) includes at least l nonzero entries, where l > 6 log (n1 ) + 2 log n1 k + 4. Then,
with probability at least 1 −


k

every proper subset Ω00(1) of columns of Ω0(1) satisfies
m2 (Ω00(1) ) − 1 ≥ t,

(42)

where t is the number of columns of Ω00(1) and m2 (Ω00(1) ) is the number of nonzero rows of Ω00(1) .
Proof. According to Lemma 6, every subset Ω00(1) of columns of Ω0(1) with n1 −1 columns satisfies property
(42) with probability at least 1 −


.
n1 k

There are exactly n1 subsets with n1 − 1 columns, and therefore

property (42) holds for all of them with probability at least 1 − k .
Lemma 11. Assume that

Pd

i=2

(ni ri ) < n2 . . . nd ,

Pd

2
i=2 ri

≤ Πdi=2 ri , Πdi=2 ni ≥ n1 (Πdi=2 ri + 1) −

Pd

2
i=2 ri ,

and Assumption B1 hold. Furthermore, assume that each column of U(1) includes at least l observed

34

entries, where
(

Pd

2
i=2 ri


l > 6 log (n1 ) + 2 max log

!
, log

Πdi=2 ri −


Pd

2
i=2 ri

!
, log

)
n 
1



+ 8.

(43)

Then, with probability at least 1 − , there exists only one completion of rank (r1 , · · · , rd ).
 Pd 2 
Pd 2
d
d
d
and
Proof. Observe that since Πi=2 ni ≥ n1 (Πi=2 ri + 1) − i=2 ri there exist n1 Πi=2 ri −
i=2 ri
n1 disjoint columns in Ω(1) denoted by Ω̆0 and Ω̆00 , respectively. In order to show unique completability,
it suffices to show Ω̆0 and Ω̆00 satisfy properties (i) and (ii) in the statement of Theorem 7, respectively,
with probability at least 1 − 2 .
Note that having (43), it is easy to see that (29) holds with  replaced by 2 . Therefore, according to
Theorem 5, Ω̆0 satisfies property (i) in the statement of Theorem 7 with probability at least 1 − 2 .
P
On the other hand, di=2 ri2 ≤ Πdi=2 ri and according to Lemma 10 (with k = 2), with probability at
least 1 − 2 , any subset of columns of Ω̆00 satisfies (42). For any proper subset of column Ω̆000 of Ω̆00 , we
have m2 (Ω̆000 ) − 1 ≥ t0 or equivalently (t0 is the number of columns of Ω̆000 )


Πdi=j+1 ri mj+1 (Ω̆000 ) − Πdi=2 ri ≥ Πdi=j+1 ri t0 ,
which results in (40) as gj+1 (mj+1 (Ω̆000 )) ≤

Pd

2
i=2 ri

(44)

≤ Πdi=2 ri and (t0 − n0 + 1)+ = 0. Hence, in order to

show property (ii) in the statement of Theorem 7 holds with probability at least 1 −


2

(which completes

the proof) we only need to show that (40) holds when Ω̆000 = Ω̆00 .
Note that mj+1 (Ω̆000 ) ≤ mj+1 (Ω̆00 ). Therefore, as m2 (Ω̆000 )−1 ≥ t0 holds for any proper subset of column
P
Ω̆000 of Ω̆00 , we have mj+1 (Ω̆00 ) ≥ n1 (by setting t0 = n1 −1). Then, (40) holds as gj+1 (mj+1 (Ω̆00 )) ≤ di=2 ri2
and (t0 − n0 + 1)+ = 1.
Finally, in the following, we use Corollary 1 and the above lemma to propose a lower bound on the
sampling probability to guarantee the unique completability with high probability.
Corollary 3. Assume that

Pd

2
i=j+1 ri

≤ Πdi=j+1 ri , Πdi=j+1 ni ≥ Nj (Πdi=j+1 ri + 1) −

Pd

2
i=j+1 ri ,

and

Assumption Bj hold. Furthermore, assume that we observe each entry of the tensor U with probability p,
where
p>

1
Nj

( Pd
6 log (Nj ) + 2 log max

2
d
i=j+1 ri Πi=j+1 ri −
,



Pd

2
i=j+1 ri Nj
,


)!

!
+8

1
+p
.
4
Nj

(45)

35

1

Probability of Sampling

Matricization Approach
0.9
Tensor Approach
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0

50

100

150

200

250

300

Rank
Fig. 4: Lower bounds on sampling probability for a 4th -order tensor.
Then, with probability at least 1 − 2, there exists only one completion for U, given the rank components
rj+1 , . . . , rd .
Proof. The proof is straightforward given Lemma 11 and Corollary 1.
VI. N UMERICAL C OMPARISONS
In order to show the advantage of our proposed method over matrix analysis, we compare the lower
bound on the sampling probability obtained by matricization analysis with the bound obtained by tensor
analysis.
In the first example, numerical comparisons are performed on a 4th -order tensor U ∈ R900×900×900×900 .
Figure 4 plots the bounds given in (18) (Grassmannian manifold) and (38) (Tucker manifold) for finite
completability, where r1 = · · · = r4 = r, and  = 0.0001. As the second example, we consider a 6th -order
tensor U ∈ R900×900×900×900×900×900 . Figure 5 plots the bounds given in (18) (Grassmannian manifold)
and (38) (Tucker manifold) for finite completability, where r3 = r4 = r5 = r4 = r, and  = 0.0001. In
this example, a significant reduction in the sampling probability is seen for the tensor model.
We have the following observations:
•

In Figure 4, the bound obtained through the analysis on Tucker manifold is less than the bound
obtained through the low-order analysis on Grassmannian manifold. This improvement significantly
increases as the value of the rank increases.

36

0.7

Probability of Sampling

Matricization Approach
0.6
Tensor Approach
0.5
0.4
0.3
0.2
0.1
0
0

50

100

150

Rank
Fig. 5: Lower bounds on sampling probability for a 6th -order tensor.
•

In Figure 4, the restriction r ≤

n
6

in the analysis on Grassmannian manifold makes the bound valid

only for r ≤ 150 (and that is why the corresponding curve is dotted for r > 150 in Figure 4). On
the other hand, the restriction r(d − 1) ≤ n in our proposed approach ensures the validity of the
P
bound for r ≤ 300. Similarly, in Figure 5, the restriction Πdi=j+1 ni ≥ Nj Πdi=j+1 ri − di=j+1 ri2 in the
analysis on Tucker manifold makes the bound valid only for r ≤ 30.
•

Since the bounds for finite completability (45) and unique completability (38) result in almost the
same curves in the above examples, we only plot bounds for finite completability in the figures. In
 
N
general, the main difference between (38) and (45) is an additional term log j in the second term
inside of maximum operator.
VII. C ONCLUSIONS

This paper aims to find fundamental conditions on the sampling pattern for finite completability of a
low-rank partially sampled tensor. To solve this problem, a novel geometric approach on Tucker manifold
is proposed. Specifically, a set of polynomials based on the location of the sampled entries are first defined,
and then using Bernstein’s theorem and analysis on Tucker manifold, a relationship between a geometric
pattern on the sampled entries and the number of algebraically independent polynomials among all of
the defined polynomials is characterized. Moreover, an extension to Hall’s theorem in graph theory is
provided which is key to obtaining probabilistic conditions for finite and unique completabilities. Using

37

these developed tools, we have addressed three problems in this paper: (i) Characterizing the necessary
and sufficient conditions on the sampling pattern to have finitely many tensor completions for the given
rank, (ii) Characterizing conditions on the sampling pattern to ensure that there is exactly one completion
for the given rank, (iii) Lower bounding the sampling probability such that the conditions in Problems (i)
and (ii) are satisfied with high probability.
Finally, through numerical examples it is seen that our proposed analysis on Tucker manifold for finite
tensor completability leads to a much lower sampling rate than the matricization approach that is based
on analysis on Grassmannian manifold.
A PPENDIX A
P ROOF OF L EMMA 4
As mentioned before, finiteness of the number of completions given (rj+1 , . . . , rd ) results finiteness of
the number of completions given (rj , . . . , rd ). We are interested to show this statement holds in Theorem
3, i.e, satisfying the properties (i) and (ii) for j in the statement of Theorem 3 results in satisfying the
properties (i) and (ii) for j − 1. Before we present this result, the following notation is introduced for the
simplicity.
Definition 6. Let set S be a set of d-tuples such that each element of S consists of d natural numbers
(x1 , . . . , xd ). Define fj (S) as the number of different tuples of the first j components of the elements of
S.
For example, let S = {(2, 2, 1), (2, 3, 3), (2, 2, 2), (1, 2, 1), (2, 3, 1)}. Then, according to the definition
f2 (S) = |{(2, 2), (2, 3), (1, 2)}|= 3.
Now, we are ready to provide the proof of lemma. It is easy to see that Lemma 4 is exactly equivalent
to the following statement:


Assume that we sample a tensor U ∈ Rn1 ×n2 ×···×nd . Suppose that there exist n = Πji=1 ni Πdi=j+1 ri −
P

d
2
r
of the sampled entries such that any subset of them (called S) with t observed entires (for
i=j+1 i
any 1 ≤ t ≤ n) satisfies the following inequality

Πdi=j+1 ri fj (S) − gj+1 (fj (S)) ≥ t.
Then, there exist n0 = Πj−1
i=1 ni



(46)

 Pd 2 
Πdi=j ri −
i=j ri of the sampled entries such that any subset of

38

them (called S 0 ) with t observed entires (for any 1 ≤ t ≤ n0 ) satisfies the following inequality

Πdi=j ri fj−1 (S 0 ) − gj (fj−1 (S 0 )) ≥ t.

(47)

Therefore, it suffices to show the above statement. For rj = 1, the statement can be easily verified, and
P
therefore we consider the case of rj > 1 in the rest of proof. Also recall the assumption nj > di=1 ri .
We partition all of the sampled entries into nj groups such that group i includes all of the sampled entries
that j-th component of their coordinate is equal to i. Let Si denote the i-th group. Observe that every
subset of the sampled entries of each group satisfies inequality (46). Moreover, according to pigeonhole
principle we know that between the defined nj groups there exist rj groups (without loss of generality
Prj
r
assume S1 , . . . , Srj ) such that i=1
|Si |≥ njj n.

 d
 rj Pd
r
2
r
≥ n0 , we only need to show that any subset of the
n
Since njj n = Πj−1
Π
r
−
i=j i
i=1 i
i=j+1 i
nj
elements of the groups S1 , . . . , Srj satisfies inequality (47). Consider an arbitrary subset of the elements
of groups S1 , . . . , Srj and denote it by S 0 . Assume that Si0 denotes the elements of S 0 that belong in Si
for 1 ≤ i ≤ rj . Recall that every subset of the sampled entries of each group satisfies inequality (46).
Moreover, due to the fact that in each group the j-th component of the coordinates are the same, for each
subset of the entries of a group Si we have fj (Si0 ) = fj−1 (Si0 ). As a result, we have

Πdi=j+1 ri fj−1 (Si0 ) − gj+1 (fj−1 (Si0 )) ≥ |Si0 |.

(48)

Without loss of generality, assume fj (S10 ) ≥ fj (S20 ) ≥ . . . ≥ fj (Sr0 j ). Also, observe that for each
1 ≤ i ≤ rj we have fj (Si0 ) ≤ fj (S 0 ). Therefore, by adding up the above inequalities for 1 ≤ i ≤ rj we
have

Πdi=j ri fj−1 (S10 ) − gj+1 (fj−1 (S10 ))rj ≥ |S 0 |.
For the case that 1 < rj <

Pd

2
i=j+1 ri

holds, we can see that rj

P

d
2
i=j+1 ri

(49)


≥

Pd

i=j

ri2 also holds,

and therefore using (49) we can obtain

Πdi=j ri fj−1 (S 0 ) − gj (fj−1 (S 0 )) ≥ |S 0 |,
which completes the proof. If rj ≥
entries proof can be completed.

Pd

2
i=j+1 ri

(50)

similarly using the above inequality and by ignoring rj2 of

39

A PPENDIX B
P ROOF OF T HEOREM 6
The proof of this theorem is based on strong induction on x. For x = 1 the theorem is easy to verify.
Assume that the statement of the theorem holds for 1 ≤ x ≤ x0 . Then, it suffices to show that the
statement also holds for the case that x = x0 + 1. There are two different scenarios that we need to show
the statement holds for separately.
Scenario 1. There exists a proper and nonempty subset of nodes S1 of T1 such that |N (S1 )|= |S1 |+r :
Consider the induced subgraph of G with the set of nodes S1 ∪ N (S1 ) and denote it by G1 . Induction
hypothesis results in a spanning subgraph G10 of G1 that satisfies the desired properties in the statement
of the theorem for the corresponding subgraph G1 .
Now, consider the induced subgraph of G with the set of nodes {T1 ∪T2 }\{S1 } and denote it by G2 . Since
|N (S1 )|= |S1 |+r, we conclude that for each subset of nodes of {T1 }\{S1 } we have |N (S)∩{T2 \N (S1 )}|≥
|S|. The reason is that if we choose a set of nodes including the members of S ⊂ {T1 }\{S1 } plus all nodes
in S1 and use the assumption in the statement of the theorem, it results that |N (S) ∩ {T2 \ N (S1 )}|≥ |S|.
Moreover, induction hypothesis results that there exists a spanning subgraph that satisfies the desired
properties in the statement of the theorem for the corresponding subgraph G2 . Now, Lemma 12 results
that there exists a spanning subgraph G20 of the graph G2 so that every node of T1 \ S1 is of degree r + 1,
and also for each subset of nodes of T1 \ S1 , the inequality (37) holds and in addition, G20 includes a
perfect matching between the nodes in T1 \ S1 and T2 \ N (S1 ).
Now, consider a spanning subgraph G 0 of the graph G that only includes all edges of G10 and G20 . We
can easily observe that every node of T1 is of degree r + 1. Moreover, for each subset of nodes of S1
the inequality (37) holds, and also for each subset of nodes of T1 \ S1 the inequality (37) holds. Now,
consider a subset of nodes S of T1 . It suffices to show the inequality (37) holds for S.
Define S 0 = S ∩ S1 and S 00 = S ∩ {T1 \ S1 }. Since for each subset of nodes of S1 the inequality (37)
holds, we have |N (S) ∩ N (S1 )|≥ |S 0 |+r. On the other hand, G 0 includes a perfect matching between
the nodes in T1 \ S1 and T2 \ N (S1 ), and therefore |N (S) ∩ {T2 \ N (S1 )}|≥ |S 00 |. As a result, |N (S)|≥
|S 0 |+r + |S 00 |= |S|+r and the proof is complete for this scenario.
Scenario 2: For any proper and nonempty subset of nodes of T1 we have |N (S)|≥ |S|+r + 1:
Consider an arbitrary node v1 and observe that |N (v1 )|≥ r + 1. Define S1 = T1 \ {v1 } and let G1 denote
the induced subgraph of G with set of nodes S1 ∪ T2 (which is all nodes of graph G except for the node

40

v1 ). Induction hypothesis results that there exists a spanning subgraph G10 of the graph G1 such that every
node of S1 is of degree r + 1, and also for each subset of nodes of S1 , the inequality (37) holds. Now,
consider a spanning subgraph G 0 of the graph G that includes only all edges of G10 , and also r + 1 random
edges among all edges that are connected to v1 . It is clear that G 0 satisfies all of the desired properties
mentioned in the statement of the theorem.
In order to complete the proof of Theorem 6, we need the following lemma as it was mentioned before.
Lemma 12. Consider a bipartite graph G with the two sets of nodes, T1 with x nodes and T2 with x+r +y
nodes, where x, y, r ∈ N. Suppose that for each subset of the nodes of T1 we have
|N (S)|≥ |S|+r.

(51)

Moreover, assume that there exists a subset of nodes S0 of T2 such that |S0 |= x, and also for every subset
of nodes S of T1 we have |N (S) ∩ S0 |≥ |S|. Assume that there exists a spanning subgraph G0 of G such
that every node of T1 is of degree r + 1, and also for each subset of nodes of T1 , the inequality (51) holds.
Then, there exists a spanning subgraph G 0 of G such that every node of T1 is of degree r + 1, and also
for each subset of nodes of T1 , the inequality (51) holds and in addition, G 0 includes a perfect matching
between the nodes in T1 and S0 .
Proof. We prove the lemma using strong induction on x. For x = 1 the lemma is easy to verify. Assume
that the statement of lemma holds for 1 ≤ x ≤ x0 . Then, we only need to show that lemma holds for
the case that x = x0 + 1. There are two scenarios and we prove the statement for these two scenarios
separately as follows.
Scenario 1: There exists a proper and nonempty subset of nodes S1 of T1 such that |N (S1 ) ∩ S0 |= |S1 |:
For simplicity in notation, define S10 , T1 \ S1 . In this scenario, we use the induction hypothesis for
S1 and S10 separately (since |S1 |≤ x0 and |S10 |≤ x0 ). Define the sets S00 = N (S1 ) ∩ S0 and S000 = S0 \ S00 .
Consider the induced subgraph G1 of the graph G where the set of vertices of G1 is T2 ∪ S1 . Assumption
of the lemma results that there exists a spanning subgraph of G1 such that every node of S1 is of degree
r + 1, and also for each subset of nodes of S1 , the inequality (51) holds (by considering all the edges of
the induced subgraph with vertices T2 ∪ S1 that also exist in G0 ). Induction hypothesis results that there
exists a spanning subgraph G00 of G1 such that every node of S1 is of degree r + 1, and also for each
subset of nodes of S1 , the inequality (51) holds and in addition, G00 includes a perfect matching between

41

nodes of S1 and nodes of S00 .
Consider the induced subgraph G10 of the graph G where the set of vertices of G2 is T2 ∪ S10 . Again,
assumption of the lemma results that there exists a spanning subgraph of G10 such that every node of S10
is of degree r + 1, and also for each subset of nodes of S10 , the inequality (51) holds (by considering all
the edges of the induced subgraph with vertices T2 ∪ S10 that also exist in G0 ). Also, observe that since
|N (S1 ) ∩ S0 |= |S1 |, for every subset of nodes S of S10 we have |N (S) ∩ S000 |≥ |S|. As a result, induction
hypothesis results that there exists a spanning subgraph G000 of G10 such that every node of S10 is of degree
r + 1, and also for each subset of nodes of S10 , the inequality (51) holds. In addition, G000 includes a perfect
matching between nodes of S10 and nodes of S000 .
Now, consider a spanning subgraph G 0 of the graph G that only includes all edges of G00 and G000 . It can
be verified that G 0 satisfies all of the desired properties in the statement of the lemma and therefore the
proof is complete for this case.
Scenario 2: For any proper and nonempty subset of nodes of T1 we have |N (S) ∩ S0 |≥ |S|+1:
In this case, consider an arbitrary vertex of T1 and denote it by v0 , and also define S1 = T1 \ {v0 }.
Hence, we have |N (S1 ) ∩ S0 |≥ |S1 |+1 and since for any S we have |N (S) ∩ S0 |≤ |S0 | we conclude
that |N (S1 ) ∩ S0 |= |S1 |+1. Also, according to the assumptions of the lemma we know N (v0 ) ≥ r + 1
and |N (v0 ) ∩ S0 |≥ 1. We choose an arbitrary node among the nodes in |N (v0 ) ∩ S0 | and denote it by
u0 . Construct a graph G000 with nodes T2 ∪ {v0 } and r + 1 edges among edges that are connected to v0
including the edge between v0 and u0 , i.e., (v0 , u0 ).
Now, consider the induced subgraph G1 of the graph G where the set of vertices of G1 is T2 ∪ S1 ,
i.e., all nodes in G except for the node v0 . Assumption of the lemma results that there exists a spanning
subgraph of G1 such that every node of S1 is of degree r + 1, and also for each subset of nodes of S1 ,
the inequality (51) holds (by considering all edges of the induced subgraph with vertices T2 ∪ S1 that also
exist in G0 ). Induction hypothesis results that there exists a spanning subgraph G00 of G1 such that every
node of S1 is of degree r + 1, and also for each subset of nodes of S1 , the inequality (51) holds and in
addition, G00 includes a perfect matching between nodes of S1 and nodes of S0 \ {u0 }.
Finally, consider a spanning subgraph G 0 of the graph G that only includes all edges of G00 and G000 . The
constructed graph G 0 satisfies all of the mentioned properties in the lemma.

42

A PPENDIX C
P ROOF OF C LAIM IN E XAMPLE 5
In the following we show that given the rank-2 sampled matrix in Example 5, there are exactly two
completions. Note that the following decomposition always holds for some values of r1 , r2 , . . . , r6 and
x1 , x2 , . . . , x8 :
1

1

−4

2

0

1

1

− 12

0

0

1

r1

r2

r3

r4

r5

r6

−1
2

=

4
4

1

3
2

−2

×

x1

x2

x3

x4

x5

x6

x7

x8

Note that the 2 × 2 identity matrix in the above decomposition represents canonical basis defined in
Definition 12. The first two rows of U in the above decomposition result the following:
1 = x1 ,

(52a)

1 = x3 ,

(52b)

1
= x4 ,
2

(52c)

−4 = x5 ,

(52d)

2 = x6 ,

(52e)

−1 = x7 .

(52f)

−

Then, the decomposition can be simplified as
0

1

1

2
=

4
4

−2

r1

3
2

r2

r3

r4

r5

r6

×

1

x2

1

− 21

−4

2

−1

x8

43

Therefore, we have following system of equations
0 = r1 − 4r2 ,

(53a)

1 = x2 r1 + 2r2 ,

(53b)

1
2 = − r1 + x8 r2 ,
2

(53c)

1 = r3 − 4r4 ,

(53d)

4 = r3 − r4 ,

(53e)

4 = x2 r5 + 2r6 ,

(53f)

−2 = r5 − r6 ,
3
1
= − r5 + x8 r6 .
2
2

(53g)
(53h)

Observe that r3 = 5 and r4 = 1 can be determined uniquely from (53d) and (53e). Note that r1 = 4r2
and r5 = (r6 − 2) can be concluded from (53a) and (53g), respectively. Then, by substituting r1 ← 4r2
in (53b) and (53c) and substituting r5 ← (r6 − 2) in (53f) and (53h) we obtain:

Similarly, r2 =
substituting r2 ←

2
x8 −2
2
x8 −2

and r6 =
, r6 ←

1 = 4x2 r2 + 2r2 ,

(54a)

2 = −2r2 + x8 r2 ,

(54b)

4 = x2 (r6 − 2) + 2r6 ,

(54c)

1
3
= − (r6 − 2) + x8 r6 .
2
2

(54d)

1
2x8 −1

1
2x8 −1

can be concluded from (54b) and (54d), respectively. Hence,

in (54a) and (54c) results in the following system of equations
x8 = 8x2 + 6,

8x8 − 4 = x2 − 2x2 (2x8 − 1) + 2.

(55a)
(55b)

Finally, (55a) results x8 = 8x2 + 6, and therefore substituting x8 ← 8x2 + 6 in (55b) results
8(8x2 + 6) − 4 = x2 − 2x2 (2(8x2 + 6) − 1) + 2,

(56)

44

which can be simplified as
32x22 + 85x2 + 42 = 0.

(57)

}. Given x2 , all other variables can be determined uniquely recursively as above,
Therefore, x2 ∈ {−2, − 21
32
and the following completions of U can be obtained as the only possible rank-2 completions of U.
1

− 21
32

1

− 12

1

0

−4

2

−1

3
4

0

1

0

1

- 24
5

2

− 32
5

− 58

1

− 41
32

4

− 74

5

1

−8

4

−2

3
2

0

2

1

−2

1

− 12

1

0

−4

2

−1

−10

0

1

0

1

- 12

2

− 23

− 16

1

−8

4

− 25
2

5

1

− 39
21

4

−2

3
2

43
− 21

1
− 21

=

×

1

21
− 32

1

− 12

−4

2

−1

3
4

1

−2

1

− 12

−4

2

−1

−10

and

=

×

R EFERENCES
[1] M. Ashraphijuo, V. Aggarwal, and X. Wang, “A characterization of sampling patterns for low-tucker-rank tensor completion problem,”
in Information Theory (ISIT), 2017 IEEE International Symposium on.

IEEE, 2017, pp. 531–535.

[2] E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski, “Phase retrieval via matrix completion,” SIAM review, vol. 57, no. 2, pp.
225–251, 2015.
[3] H. Ji, C. Liu, Z. Shen, and Y. Xu, “Robust video denoising using low rank matrix completion.” in CVPR.

Citeseer, 2010, pp.

1791–1798.
[4] L. Eldén, Matrix methods in data mining and pattern recognition.

SIAM, 2007, vol. 4.

[5] N. J. Harvey, D. R. Karger, and K. Murota, “Deterministic network coding by matrix completion,” in Proceedings of the sixteenth
annual ACM-SIAM symposium on Discrete algorithms.

Society for Industrial and Applied Mathematics, 2005, pp. 489–498.

[6] L.-H. Lim and P. Comon, “Multiarray signal processing: Tensor decomposition meets compressed sensing,” Comptes Rendus Mecanique,
vol. 338, no. 6, pp. 311–320, 2010.
[7] N. D. Sidiropoulos and A. Kyrillidis, “Multi-way compressed sensing for sparse low-rank tensors,” IEEE Signal Processing Letters,
vol. 19, no. 11, pp. 757–760, 2012.
[8] S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” Inverse Problems,
vol. 27, no. 2, pp. 1–19, 2011.
[9] J. Liu, P. Musialski, P. Wonka, and J. Ye, “Tensor completion for estimating missing values in visual data,” IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 35, no. 1, pp. 208–220, 2013.

45

[10] X.-Y. Liu, S. Aeron, V. Aggarwal, and X. Wang, “Low-tubal-rank tensor completion using alternating minimization,” arXiv
preprint:1610.01690, Oct. 2016.
[11] ——, “Low-tubal-rank tensor completion using alternating minimization,” in SPIE Defense+ Security. International Society for Optics
and Photonics, 2016, pp. 984 809–984 809.
[12] N. Kreimer, A. Stanton, and M. D. Sacchi, “Tensor completion based on nuclear norm minimization for 5D seismic data reconstruction,”
Geophysics, vol. 78, no. 6, pp. V273–V284, 2013.
[13] G. Ely, S. Aeron, N. Hao, M. E. Kilmer et al., “5d and 4d pre-stack seismic data completion using tensor nuclear norm (tnn),” in 2013
SEG Annual Meeting.

Society of Exploration Geophysicists, 2013.

[14] W. Wang, V. Aggarwal, and S. Aeron, “Tensor completion by alternating minimization under the tensor train (TT) model,” arXiv
preprint:1609.05587, Sep. 2016.
[15] X.-Y. Liu, S. Aeron, V. Aggarwal, X. Wang, and M.-Y. Wu, “Tensor completion via adaptive sampling of tensor fibers: Application
to efficient indoor RF fingerprinting,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016,
pp. 2529–2533.
[16] X. Y. Liu, S. Aeron, V. Aggarwal, X. Wang, and M. Y. Wu, “Adaptive sampling of RF fingerprints for fine-grained indoor localization,”
IEEE Transactions on Mobile Computing, vol. 15, no. 10, pp. 2411–2423, Oct. 2016.
[17] V. Aggarwal, A. A. Mahimkar, H. Ma, Z. Zhang, S. Aeron, and W. Willinger, “Inferring smartphone service quality using tensor
methods,” in 12th International Conference on Network and Service Management, Oct.–Nov. 2016.
[18] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in The forty-fifth annual symposium
on Theory of computing.

ACM, 2013, pp. 665–674.

[19] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Foundations of Computational Mathematics, vol. 9,
no. 6, pp. 717–772, 2009.
[20] E. J. Candès and T. Tao, “The power of convex relaxation: Near-optimal matrix completion,” IEEE Transactions on Information Theory,
vol. 56, no. 5, pp. 2053–2080, 2010.
[21] J. F. Cai, E. J. Candès, and Z. Shen, “A singular value thresholding algorithm for matrix completion,” SIAM Journal on Optimization,
vol. 20, no. 4, pp. 1956–1982, 2010.
[22] R. Ge, J. D. Lee, and T. Ma, “Matrix completion has no spurious local minimum,” arXiv preprint:1605.07272, 2016.
[23] T. S. C. HAVE, “A number of approaches to subspace clustering have been proposed in the past two decades.” 2011.
[24] L. Parsons, E. Haque, and H. Liu, “Subspace clustering for high dimensional data: a review,” ACM SIGKDD Explorations Newsletter,
vol. 6, no. 1, pp. 90–105, 2004.
[25] D. Pimentel-Alarcón, L. Balzano, R. Marcia, R. Nowak, and R. Willett, “Group-sparse subspace clustering with missing data.”
[26] D. Pimentel-Alarcón, R. Nowak, and L. Balzano, “On the sample complexity of subspace clustering with missing data,” in IEEE
Workshop on Statistical Signal Processing (SSP), 2014, pp. 280–283.
[27] R. Tomioka, K. Hayashi, and H. Kashima, “Estimation of low-rank tensors via convex optimization,” arXiv preprint:1010.0789, Oct
2010.
[28] M. Signoretto, Q. T. Dinh, L. De Lathauwer, and J. A. Suykens, “Learning with tensors: a framework based on convex optimization
and spectral regularization,” Machine Learning, vol. 94, no. 3, pp. 303–351, 2014.
[29] B. Romera-Paredes and M. Pontil, “A new convex relaxation for tensor completion,” in Advances in Neural Information Processing
Systems, 2013, pp. 2967–2975.
[30] M. Ashraphijuo, R. Madani, and J. Lavaei, “Characterization of rank-constrained feasibility problems via a finite number of convex
programs,” in IEEE 55th Conference on Decision and Control (CDC), 2016, pp. 6544–6550.

46

[31] D. Kressner, M. Steinlechner, and B. Vandereycken, “Low-rank tensor completion by riemannian optimization,” BIT Numerical
Mathematics, vol. 54, no. 2, pp. 447–468, 2014.
[32] A. Krishnamurthy and A. Singh, “Low-rank matrix and tensor completion via adaptive sampling,” in Advances in Neural Information
Processing Systems, 2013, pp. 836–844.
[33] D. Goldfarb and Z. Qin, “Robust low-rank tensor recovery: Models and algorithms,” SIAM Journal on Matrix Analysis and Applications,
vol. 35, no. 1, pp. 225–253, 2014.
[34] B. Recht, “A simpler approach to matrix completion,” Journal of Machine Learning Research, vol. 12, no. Dec, pp. 3413–3430, 2011.
[35] D. Pimentel-Alarcón, N. Boston, and R. Nowak, “A characterization of deterministic sampling patterns for low-rank matrix completion,”
IEEE Journal of Selected Topics in Signal Processing, vol. 10, no. 4, pp. 623–636, 2016.
[36] F. Király, L. Theran, and R. Tomioka, “The algebraic combinatorial approach for low-rank matrix completion,” Machine Learning,
vol. 16, pp. 1391–1436, 2015.
[37] L. Balzano, B. Eriksson, and R. Nowak, “High rank matrix completion and subspace clustering with missing data,” in The conference
on Artificial Intelligence and Statistics (AIStats), 2012.
[38] M. Ashraphijuo, X. Wang, and V. Aggarwal, “Rank determination for low-rank data completion,” Journal of Machine Learning Research,
vol. 18 (98), pp. 1–29, 2017.
[39] D. Pimentel, R. Nowak, and L. Balzano, “On the sample complexity of subspace clustering with missing data,” in IEEE Workshop on
Statistical Signal Processing (SSP).

IEEE, 2014, pp. 280–283.

[40] D. Pimentel-Alarcón, E. R. D. Nowak, and W. EDU, “The information-theoretic requirements of subspace clustering with missing
data,” in International Conference on Machine Learning, 2016.
[41] C. Yang, D. Robinson, and R. Vidal, “Sparse subspace clustering with missing entries,” in International Conference on Machine
Learning (ICML), 2015, pp. 2463–2472.
[42] D. Pimentel-Alarcón, L. Balzano, R. Marcia, R. Nowak, and R. Willett, “Group-sparse subspace clustering with missing data,” in IEEE
Workshop on Statistical Signal Processing (SSP), 2016, pp. 1–5.
[43] T. G. Kolda, “Orthogonal tensor decompositions,” SIAM Journal on Matrix Analysis and Applications, vol. 23, no. 1, pp. 243–255,
2001.
[44] L. Grasedyck, “Hierarchical singular value decomposition of tensors,” SIAM Journal on Matrix Analysis and Applications, vol. 31,
no. 4, pp. 2029–2054, 2010.
[45] D. Kressner, M. Steinlechner, and B. Vandereycken, “Low-rank tensor completion by riemannian optimization,” BIT Numerical
Mathematics, vol. 54, no. 2, pp. 447–468, 2014.
[46] J. Berge and N. Sidiropoulos, “On uniqueness in candecomp/parafac,” Psychometrika, vol. 67, no. 3, pp. 399–409, 2002.
[47] A. Stegeman and N. D. Sidiropoulos, “On kruskals uniqueness condition for the candecomp/parafac decomposition,” Linear Algebra
and its applications, vol. 420, no. 2, pp. 540–552, 2007.
[48] I. V. Oseledets, “Tensor-train decomposition,” SIAM Journal on Scientific Computing, vol. 33, no. 5, pp. 2295–2317, 2011.
[49] S. Holtz, T. Rohwedder, and R. Schneider, “On manifolds of tensors of fixed tt-rank,” Numerische Mathematik, vol. 120, no. 4, pp.
701–731, 2012.
[50] J. Ballani, L. Grasedyck, and M. Kluge, “Black box approximation of tensors in hierarchical Tucker format,” Linear Algebra and its
Applications, vol. 438, no. 2, pp. 639–657, 2013.
[51] W. Hackbusch and S. Kühn, “A new scheme for the tensor representation,” Journal of Fourier Analysis and Applications, vol. 15, no. 5,
pp. 706–722, 2009.

47

[52] M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover, “Third-order tensors as operators on matrices: A theoretical and computational
framework with applications in imaging,” SIAM Journal on Matrix Analysis and Applications, vol. 34, no. 1, pp. 148–172, 2013.
[53] J. D. Carroll and J.-J. Chang, “Analysis of individual differences in multidimensional scaling via an n-way generalization of eckart-young
decomposition,” Psychometrika, vol. 35, no. 3, pp. 283–319, 1970.
[54] L. De Lathauwer, B. De Moor, and J. Vandewalle, “A multilinear singular value decomposition,” SIAM journal on Matrix Analysis and
Applications, vol. 21, no. 4, pp. 1253–1278, 2000.
[55] E. E. Papalexakis, C. Faloutsos, and N. D. Sidiropoulos, “Parcube: Sparse parallelizable tensor decompositions,” in Joint European
Conference on Machine Learning and Knowledge Discovery in Databases.
[56] B. Sturmfels, Solving systems of polynomial equations.

Springer, 2012, pp. 521–536.

American Mathematical Soc., 2002, no. 97.

[57] A. Schaeffer, “Inequalities of a. markoff and s. bernstein for polynomials and related functions,” Bulletin of the American Mathematical
Society, vol. 47, no. 8, pp. 565–579, 1941.
[58] M. Ashraphijuo and X. Wang, “Fundamental conditions for low-cp-rank tensor completion,” Journal of Machine Learning Research,
vol. 18 (63), pp. 1–29, 2017.
[59] S. Janson, “On concentration of probability,” Contemporary combinatorics, vol. 10, no. 3, pp. 1–9, 2002.
[60] H. A. Kierstead, “An effective version of halls theorem,” Proceedings of the American Mathematical Society, vol. 88, no. 1, pp.
124–128, 1983.

