Spectral algorithms for tensor completion

Introduction

Tensors are increasingly ubiquitous in a variety of statistics and machine learning contexts. Many datasets are arranged according to the values of three or more attributes, giving rise to multi-way tables which can be interpreted as tensors [Mør11]. For instance, consider the collaborative filtering problem in which a group of users provide feedback on the episodes of a certain number of television shows, over an extended time interval. The data is indexed by three attributes — user id, show id, and episode broadcast time — so it is presented as a three-way table (which is a tensor). A second example comes from high-dimensional applications of the moment method [HKZ12]: the $k$-th moments of a multivariate distribution are naturally encoded by a $k$-fold tensor. Some other applications include image inpainting [LMWY13], hyperspectral imaging [LL10, SVdPDMS11], and geophysical imaging [KSS13].

This paper proposes methods for completing $\bm{T}$ from n observed entries, and investigates the minimum number n (as a function of $k,d,r$) required for a non-trivial estimator.

There is already a substantial literature on tensor completion, and we survey here some of the main ideas that have emerged.

Motivated by the success of methods for matrix completion based on nuclear norm relaxations [CR09, Gro11], several papers have studied estimators based on a suitable definition of tensor nuclear norm [YZ15, YZ16]. This tensor norm is np-hard to evaluate [FL16] and therefore this approach does not lead to practical algorithms. Nevertheless these studies provide useful information on the minimum number n of entries required to reconstruct $\bm{T}$ with unbounded computational resources. In particular, it was proved [YZ16] that it suffices to have

with r_{\textup{\tiny\boxplus},\mbox{\tiny\rm max}} the multilinear (or Tucker) rank of $\bm{T}$. Here we use C to denote a constant that can depend on various incoherence parameters; in later sections we will make such factors explicit. The definition of r_{\textup{\tiny\boxplus},\mbox{\tiny\rm max}} is reviewed below; we comment also that r^{1/(k-1)}\leq r_{\textup{\tiny\boxplus},\mbox{\tiny\rm max}}\leq\min\{d,r\} (see (8)). Information-theoretic considerations also indicate that

Tensor unfolding

This remark has been applied several times (e.g. [THK10, TSHK11, LMWY13, GRY11]). It seems to suggest two practically important consequences: (i) the unfolding should be made “as square as possible” by taking $a=\lfloor k/2\rfloor$ and $b=\lceil k/2\rceil$ [MHWG14]; and (ii) unfolding-based algorithms are fundamentally limited to a sample size $\textsf{n}\geq\textsf{C}rd^{\lceil k/2\rceil}$, due to the limitations of matrix completion — this has been suggested by several authors [YZ15, YZ16, BM15], and is further discussed below. One of the main purposes of this paper is to revisit this last insight.

Semidefinite programming hierarchies.

In terms of the number n of observed entries required, the above results indicate a large gap between information-theoretic limits (2) on the one hand, and the requirements of spectral algorithms (3) on the other. Motivated by this gap, Barak and Moitra [BM15] considered the sum-of-squares (sos) hierarchy to design a more powerful polynomial-time algorithm for this problem.

Barak and Moitra consider the completion problem for a tensor $\bm{T}$ of order $k=3$, along with a slightly different notion of rank $r_{\star}(\bm{T})$. (It is a relaxation of the tensor nuclear norm of $\bm{T}$, which in turn can be viewed as a relaxation of the rank $r(\bm{T})$ [FL16].) The main result of [BM15] is that the degree-$6$ level of the sos hierarchy succeeds in completing a tensor of order $k=3$ from

entries. Under additional randomness assumptions, it is proved that

entries suffice. Considering the case of bounded rank, the [BM15] result improves (for $k=3$) over earlier results (3) obtained by unfolding, which required $\textsf{n}\geq\textsf{C}rd^{2}(\log d)^{2}$. At the same time it is far from the information-theoretic bound (2), and this remaining gap may be of a fundamental nature: the authors present evidence to suggest that condition (4) is nearly-optimal among polynomial-time algorithms.

2. Main contributions

Let us emphasize that the degree-$6$ sos relaxation requires solving an sdp for a matrix of dimensions $d^{3}\times d^{3}$. This can be done in polynomial time, but practical implementations would hardly scale beyond $d=20$. For this reason we interpret the results of [BM15] as opening (rather than closing) a search for fast tensor completion algorithms. With this motivation, we present the following results in this paper:

We consider the completion problem for symmetric tensors of general order $k\geq 3$, and propose a new estimator which is based on spectral analysis of the unfolded tensor. We show that our estimator succeeds in completing the tensor given

Previous unfolding-based methods have essentially performed matrix completion on the unfolded tensor, a $d^{a}\times d^{b}$ matrix. As we noted above, if $a\leq b$ this necessitates $\textsf{n}\gg rd^{b}$, which is essentially matched by (3). By contrast, our algorithm only seeks to estimate the column space of the unfolding, which requires fewer revealed entries, $\textsf{n}\gg rd^{(a+b)/2}=rd^{k/2}$. Given our estimate of the singular space, we then take advantage of the original tensor structure to estimate the missing entries.

Overcomplete three-tensors

For symmetric tensors of order $k=3$ we can compare our unfolding algorithm with the sos algorithm of [BM15]. Even with crude methods for matrix operations, the unfolding algorithm takes at most $O(d^{5})$ time, as opposed to $O(d^{15})$ for degree-$6$ sos (using generic sdp solvers). Neglecting logarithmic factors, our result matches theirs in the required sample size ((5) versus (6)), but with a significantly worse rank condition: we require $r\ll d^{3/4}$ whereas sos succeeds up to $r\ll d^{3/2}$. Indeed, for third-order tensors which are overcomplete (rank $r\geq d$), we do not expect that any unfolding-based method can succeed — the $d\times d^{2}$ unfolding can have rank at most $d$, and will fail to capture the rank-$r$ tensor structure. Instead, we complement our unfolding algorithm with a more specialized spectral algorithm, which is specifically intended for overcomplete three-tensors; the runtime is $O(d^{6})$. In a certain random tensor model, we show that this second method can succesfully estimate three-tensors from $\textsf{n}\gg rd^{3/2}$ revealed entries, for $d\leq r\ll d^{3/2}$. In the design and analysis of this method we were inspired by some recent work [HSSS15] on the tensor decomposition problem.

3. Organization of the paper

In Section 2 we review some definitions and notations. We then state our main results on tensor completion: Section 3 presents the unfolding-based algorithm, and Section 4 presents the more specialized algorithm for overcomplete three-tensors. In Section 5 we illustrate our results with some numerical simulations. As noted above, for our unfolding algorithm we study the column spaces of partially revealed matrices with large aspect ratio; our results on this are presented in Section 6.

Preliminaries

Between two tensors (of any order $k\geq 1$) we use $\otimes$ to denote the tensor product. Between two tensors in the same space we use $\odot$ to denote the Hadamard (entrywise) product. For instance,

We use angle brackets $\langle\cdot,\cdot\rangle$ to denote the standard euclidean scalar product — regardless of whether the objects involved are vectors, matrices, or tensors. For example, if $X,Y$ are two $d_{1}\times d_{2}$ matrices, then we use $\langle X,Y\rangle$ to denote the scalar product between $X$ and $Y$ as $(d_{1}d_{2})$-dimensional vectors. The euclidean norm of a vector $v$ will be denoted $\|v\|=\langle v,v\rangle^{1/2}$. The Frobenius norm of a $d_{1}\times d_{2}$ matrix $X$ is $\|X\|_{\textup{F}}=\langle X,X\rangle^{1/2}$; it is the euclidean norm of $X$ regarded as an $(d_{1}d_{2})$-dimensional vector. Likewise the Frobenius norm of a tensor $\bm{T}$ is $\|\bm{T}\|_{\textup{F}}=\langle\bm{T},\bm{T}\rangle^{1/2}$. For a $d_{1}\times d_{2}$ matrix $X$ we write $\|X\|_{\textup{op}}$ for its spectral norm (operator norm). Finally, we let $\|X\|_{\infty}$ denote the maximum entry size of $X$.

In the special case $k=2$ and $d_{1}=d_{2}=d$, we let

where $\textup{{D}}=\{(i,i):1\leq i\leq d\}$ is the set of diagonal entries.

2. Notions of tensor rank

We omit the argument $\bm{T}$ whenever it is clear from the context.

A different notion of rank, which is also common in the literature, is given by considering — for each $1\leq i\leq k$ — the matrix $X^{(i)}\equiv\textup{{unfold}}^{(i)}(\bm{T})$ of dimensions $d_{i}\times((d_{1}\cdots d_{k})/d_{i})$, with entries

where ${\underline{\smash{u}}}_{-i}$ is ${\underline{\smash{u}}}$ without its $i$-th index. Write $\operatorname{\textsf{span}}^{(i)}(\bm{T})$ for the column space of $X^{(i)}$, and define

The multilinear rank or Tucker rank of $\bm{T}$ is defined as r_{\textup{\tiny\boxplus},\mbox{\tiny\rm max}}(\bm{T})=\max\{r_{\textup{\tiny\boxplus},i}(\bm{T}):1\leq i\leq k\}. Again, we omit the argument $\bm{T}$ whenever it is clear from the context. It is clear from the definition that r_{\textup{\tiny\boxplus},i}\leq\max\{r,d_{i}\}. On the other hand we have

we prove this fact in the appendix (Lemma 13).

Tensor completion via unfolding

Our algorithm takes as input the set of indices E and the partially observed tensor $\bm{Y}=\Pi_{\textup{{E}}}(\bm{T})$. It also takes a threshold value $\lambda_{\star}$, which can be interpreted as a regularization parameter. In Theorem 1 we provide an explicit prescription for $\lambda_{\star}$ (see (12)).

Tensor completion via unfolding. Input: E, $\bm{Y}$, $\lambda_{\star}$.

Sample splitting. Partition the observed entries E in two disjoint subsets $\textup{{E}}_{1},\textup{{E}}_{2}$ uniformly at random, subject to $|\textup{{E}}_{1}|=|\textup{{E}}_{2}|=\textsf{n}/2$. Let $\delta_{1}\equiv\textsf{n}/(2d^{k})$. Denote by $\bm{Y}_{1}=\Pi_{\textup{{E}}_{1}}(\bm{Y})$, $\bm{Y}_{2}=\Pi_{\textup{{E}}_{2}}(\bm{Y})$ the corresponding partially observed tensors.

Tensor unfolding. Set $a=\lfloor k/2\rfloor$, $b=\lceil k/2\rceil$, and let $Z=\textup{{unfold}}^{a\times b}(\bm{Y}_{1})$. Use $Z$ to define

Let $\delta_{2}=\delta_{1}/(1-\delta_{1})$, and let ${\widehat{\bm{T}}}\equiv\bm{Y}_{1}+(\delta_{2})^{-1}\bm{Y}_{2}$. Return the tensor $\widehat{\bm{T}}^{\star}={\mathcal{Q}}({\widehat{\bm{T}}})$.

As we already commented, our algorithm differs from standard unfolding-based methods in that it does not seek to directly complete the tensor matricization, but only to estimate its left singular space. Completion is done by a “denoising” procedure which uses this singular space estimate, but also takes advantage of the original tensor structure.

2. Rank and incoherence assumptions

We will analyze the performance of Algorithm 1 subject to rank and incoherence conditions which we now describe. In particular, we allow for a slightly less restrictive notion of rank.

$\operatorname{\textup{{rank}}}X\leq\textup{{r}}$;

$d^{k}\|X\|_{\infty}^{2}\leq\alpha\|X\|_{\textup{F}}^{2}$;

$\mu\|X\|_{\textup{F}}^{2}=\textup{{r}}\|X\|_{\textup{op}}^{2}$.

Note that T1 and T2 are inequalities but T3 is an equality.

A few comments are in order. First of all, note that r_{\textup{\tiny\boxplus},\mbox{\tiny\rm max}}(\bm{T})\leq\textup{{r}}(\bm{T})\leq r(\bm{T}), which means that T1 is less restrictive than the assumption $r(\bm{T})\leq\textup{{r}}$. Next, since $\|X\|_{\infty}^{2}\leq\|X\|_{\textup{F}}^{2}\leq d^{k}\|X\|_{\infty}^{2}$, we can assume $1\leq\alpha\leq d^{k}$; it is standard in the literature to assume that $\alpha$ is not too large. Lastly, since $\|X\|_{\textup{op}}^{2}\leq\|X\|_{\textup{F}}^{2}\leq\textup{{r}}\|X\|_{\textup{op}}^{2}$, we can assume $1\leq\mu\leq\textup{{r}}$.

With these definitions, we can now state our result on the guarantees of Algorithm 1. Define

Then, in the regime $32(k\log d)^{12}\alpha\textup{{r}}\mu^{1/2}d^{k/2}\leq\textsf{n}\leq(k\log d)^{16}\alpha\textup{{r}}\mu^{2}d^{b}$, we have

Overcomplete random three-tensors

In this section we describe our algorithm for overcomplete three-tensors, and state its guarantees for a certain random tensor model. Proofs are in Appendix D.

Algorithm 1 of Section 3 is limited to tensors $\bm{T}$ with rank $r\ll r_{\max}$, as defined in (11). As we already noted above, this particular condition is most likely suboptimal. However, among all algorithms of this type (i.e., based on spectral analysis of the unfolded tensor), we expect that a fundamental barrier is $r\ll d^{\lfloor k/2\rfloor}$. Beyond this point, the unfolded tensor has nearly full rank, and we do not expect the projector $Q$ to have helpful denoising properties.

Motivated by these gaps, in this section we develop a different completion algorithm for the case $k=3$, which avoids unfolding and relies instead on a certain “contraction” of the tensor with itself. This was motivated by ideas developed in [HSSS15] for the tensor decomposition problem. Under a natural model of random symmetric low-rank tensors, we prove that in the regime $d\leq r\ll d^{3/2}$, our algorithm succeeds in completing the tensor based on $\textsf{n}\gg rd^{3/2}$ observed entries.

The algorithm takes as input the set of observed indices E, the partially observed tensor $\bm{Y}=\Pi_{\textup{{E}}}\bm{T}$, and a threshold value $\lambda_{\star}$. In Theorem 2 we provide an explicit prescription for $\lambda_{\star}$.

Completion for three-tensors via contraction. Input: $\textup{{E}},\bm{Y},\lambda_{\star}$.

Sample splitting. Let $\delta$ be defined by the relation $1-(1-\delta)^{3}=|\textup{{E}}|/d^{3}$. Take subsets $\textup{{I}},\textup{{J}},\textup{{K}}\subset\textup{{E}}$ which are uniformly random subject to the following conditions: each I, J, K has size $d^{3}\delta$; each pairwise intersection $\textup{{I}}\cap\textup{{J}}$, $\textup{{I}}\cap\textup{{K}}$, $\textup{{J}}\cap\textup{{K}}$ has size $d^{3}\delta^{2}$; the triple intersection $\textup{{I}}\cap\textup{{J}}\cap\textup{{K}}$ has size $d^{3}\delta^{3}$. (This implies, in particular, that $\textup{{I}}\cup\textup{{J}}\cup\textup{{K}}=\textup{{E}}$.) Denote the corresponding partially observed tensors $\dot{\bm{Y}}=\Pi_{\textup{{I}}}\bm{T}$, $\ddot{\bm{Y}}=\Pi_{\textup{{J}}}\bm{T}$, and $\dddot{\bm{Y}}=\Pi_{\textup{{K}}}\bm{T}$.

Tensor contraction. Let $W$ be the $d^{2}\times d^{2}$ matrix with entries

2. Random tensor model

We analyze Algorithm 2 in a random model:

(symmetric) $x$ is equidistributed as $-x$;

Note Assumption 2 has a slight abuse of notation, since the tensor (15) can have, in general, rank smaller than $r$. However, in the regime of interest, we expect the rank of $\bm{T}$ to be close to $r$ with high probability.

If one uses crude matrix calculations (not taking advantage of the sparsity or low rank of the matrices involved), we estimate the runtimes of our methods as follows. In Algorithm 1, computing the matrix $B$ of (9) takes time $O(d^{k+b})$; finding its eigendecomposition takes time $O(d^{3a})$; and the denoising step can be done in time $O(d^{k+a})$. Thus the overall runtime is $O(d^{k+b})$, which for $k=3$ becomes $O(d^{5})$. In Algorithm 2, computing the matrix $W$ of (14) takes time $O(d^{5})$; finding its singular value decomposition takes time $O(d^{6})$; and the denoising step can be done in time $O(d^{4})$. Thus the overall runtime is $O(d^{6})$; so Algorithm 1 is preferable when the rank is low.

Numerical illustration

We illustrate our results with numerical simulations of random tensors

where $\widehat{\bm{T}}^{\star}$ is the output of the completion algorithm.

Figure 1 reports the performance of our unfolding method (Algorithm 1) in the undercomplete regime, taking $r=4$. We plot the normalized mean square error (19) estimated by averaging over $100$ independent random realizations of $\bm{T}$ and of the set E of revealed entries. We set the threshold parameter

— this choice was guided by the prescription (12) of Theorem 1, as follows: in the present setting, we have $X=\textup{{unfold}}^{1\times 2}(\bm{T})$. If we write $f\sim g$ to indicate $\lim_{d\to\infty}f(d)/g(d)=1$, then

Therefore $X$ satisfies Assumption 1 with $\textup{{r}}=r$, $\mu\sim 1$, and $\alpha\sim(2\log d)^{3}/r$. Our choice of the parameter $\lambda_{\star}$ is obtained by substituting these into (12). After some trial and error, we chose the factor $3$ in (20) instead of logarithmic factors, which appeared to be overly pessimistic for moderate values of $d$.

2. Performance of spectral algorithm for overcomplete tensors

Figure 2 reports the performance of our spectral method for the overcomplete regime (Algorithm 2), taking $r/d=1.2$. We set $\lambda_{\star}$ according to the prescription (16) of Theorem 2. For each value of $d$, the MSE appears to decrease rapidly with n. The plots (for various values of $d$) of the MSE versus the rescaled sample size $\textsf{n}/(rd^{3/2})$ appears to approach a limiting curve. This suggests that the threshold for our method to succeed in reconstruction occurs around $\textsf{n}=rd^{3/2}$, which is consistent with the bound of our Theorem 2.

Column spaces of partially revealed wide matrices

In this section we present our results on the column spaces of partially revealed $d_{1}\times d_{2}$ matrices. As mentioned above, these results are the main input to the proof of Theorem 1. The conclusions obtained in this section are most interesting for the regime $d_{1}\ll d_{2}$.

$d_{1}\cdot\max_{i}\|X^{\sf t}e_{i}\|^{2}\leq\lambda\|X\|_{\textup{op}}^{2}$;

$d_{2}\cdot\max_{j}\|Xe_{j}\|^{2}\leq\rho\|X\|_{\textup{op}}^{2}$; and

$d_{1}d_{2}\cdot\max_{i,j}|X_{i,j}|^{2}\leq\lambda\gamma\rho\|X\|_{\textup{op}}^{2}$,

where $1\leq i\leq d_{1}$ and $1\leq j\leq d_{2}$.

It is easily seen (cf. Lemma 10) that one can assume without loss of generality $1/d_{1}\leq\lambda\leq d_{1}$, $1/d_{2}\leq\rho\leq d_{2}$, $1\leq\lambda\gamma\rho\leq d_{1}d_{2}$. To motivate the above condition, we observe that it can be deduced as a consequence of a standard incoherence assumption, that we recall below.

If $M$ is a $d\times r$ matrix whose columns form an orthonormal basis of $W$, then we can express $P_{W}=MM^{\sf t}$, so that

We denote $\textup{{coher}}_{M}\equiv\textup{{coher}}_{W}$.

We refer to [CR09] for further discussion of this coherence condition, which has become fairly standard in the literature. We now give two illustrations for Assumption 3:

Derivation of Assumption 3 from Definition 2. Suppose $X$ is $d_{2}\times d_{2}$ with singular value decomposition $UDV^{\sf t}$, where $U^{\sf t}U=I_{\textup{{r}}}=V^{\sf t}V$ and $D$ is diagonal. One can then easily verify that $X$ is $(\lambda,\gamma,\rho)$-incoherent with

(see Lemma 9 for the proof). That is to say, imposing Assumption 3 with $\lambda=\rho=c\textup{{r}}$ and $\gamma=1$ is less restrictive than imposing that $X$ is of rank r with $c$-incoherent singular vectors.

Derivation of Assumption 3 from Assumption 1. Alternatively, suppose $X$ satisfies an entrywise bound $d_{1}d_{2}\|X\|_{\infty}^{2}\leq\bar{\varpi}\|X\|_{\textup{op}}^{2}$. It is then trivial to verify that $X$ is $(\lambda,\gamma,\rho)$-incoherent with

In Assumption 1, conditions T2 and T3 together imply (with $d_{1}=d^{a}$ and $d_{2}=d^{b}$)

so we have (22) with $\bar{\varpi}=\alpha\textup{{r}}/\mu$. That is to say, imposing Assumption 3 with $\lambda=\rho=1/\gamma=\alpha\textup{{r}}/\mu$ is less restrictive than imposing Assumption 1 with parameters $(\textup{{r}},\alpha,\mu)$.

In the tensor completion problem we work with the second scenario (22).

2. Estimation error

We now state our main result on column space estimation for partially revealed matrices.

with probability at least $1-4d_{1}\exp\{-\tfrac{1}{8}\log(d_{1}d_{2})^{2}\}$.

In the setting of Theorem 3, assume additionally that $(\lambda\gamma^{2}\rho d_{1}d_{2}/t)^{1/2}\leq\textsf{n}\leq t\lambda d_{2}$ and $\gamma\rho\leq td_{2}$. Then the error bound (24) simplifies to

From our perspective, the most interesting application of the above is as follows. Recalling (21), suppose the $d_{1}\times d_{2}$ matrix $X$ is $(\lambda,\gamma,\rho)$-incoherent with $\lambda=\rho=cr$ and $\gamma=1$. Consider Corollary 3 with $t=1$: then the conditions reduce to $cr\leq(d_{2})^{1/2}$ and $cr(d_{1}d_{2})^{1/2}\leq\textsf{n}\leq crd_{2}$, where the latter can only be satisfied if $d_{1}\leq d_{2}$. With these conditions, Corollary 3 says that the column space of $X$ can be well approximated by the top eigenvectors of the matrix $\widehat{B}$, provided we saw (roughly) $\textsf{n}\gg r(d_{1}d_{2})^{1/2}$ entries. We emphasize that this result implies, for $d_{1}\ll d_{2}$, a wide regime of sample sizes

from which we can obtain a good estimate of the sample space, even though it is impossible to complete the matrix (in the sense of Frobenius norm approximation). In this regime, the column space estimate can be useful for (partial) matrix completion: if $Q$ approximates projection onto the left column space of $X$, and $y$ is a column of $\Pi_{\textup{{E}}}X$ containing $d\delta^{\prime}\gg r$ observed entries, then $Qy/\delta^{\prime}$ is a good estimate of the corresponding column of $X$.

Acknowledgements

This research was partially supported by NSF grant CCF-1319979 (A.M.) and NSF MSPRF grant DMS-1401123 (N.S.).

References

Appendix A Standard matrix inequalities

Suppose that $\mathcal{A}$ and $\mathcal{B}$ are positive semidefinite matrices, with singular value decompositions

Suppose $\|\mathcal{A}-\mathcal{B}\|_{\textup{op}}\leq\epsilon$, and that the maximum diagonal entry of $\Sigma_{\circ}$ is at most $\sigma$ while the minimum diagonal entry of $\Lambda$ is at least $\sigma+\delta>0$. Then

Denote $\sigma^{2}$ as in (26). Then, for all $t\geq 0$,

Let $(Z_{ij})$ be a family of matrices, and let $(\mathfrak{s}_{i})$ and $(\mathfrak{t}_{i})$ be sequences of independent symmetric random signs. There is an absolute constant $C$ such that for all $t\geq 0$,

Appendix B Column space estimation with large aspect ratios

In this appendix, we prove our matrix completion result, Theorem 3. Before passing to the actual proof, we will establish some properties of the incoherence condition, Assumption 3.

We begin by proving some easy observations regarding our matrix incoherence conditions (Assumption 3).

which implies that M2 can only be satisfied with $d_{2}\rho\geq 1$, and likewise M1 can only be satisfied with $d_{1}\lambda\geq 1$. Lastly, we have

so M3 can only be satisfied with $\lambda\gamma\rho\geq 1$. This concludes the justification of (28). ∎

B.2. Proof of matrix estimation results

(The second inequality follows from the assumptions, while the third follows from Lemma 10.) We shall apply Proposition 6 to bound the spectral norm of

provided $t\geq t_{\max}\equiv(\log(d_{1}d_{2}))^{4}\max\{t_{1},t_{2},t_{3},t_{4}\}\|X\|_{\textup{op}}^{2}$ for

From (32) we have $t_{\max}\geq\beta_{\star}\geq d_{2}q$. It follows from Proposition 6 that

where $D$ is the $d_{1}\times d_{1}$ diagonal matrix with entries

We then note $\|XWX^{\sf t}\|_{\textup{op}}\leq\|X\|_{\textup{op}}^{2}\|W\|_{\textup{op}}\leq\rho\|X\|_{\textup{op}}^{4}/d_{2}$, while

having made use of Lemma 10 and (29). If we set $\beta_{\star}=\max\{\sigma,R\}$ and $\beta=(\log(d_{1}d_{1}))^{2}\beta_{\star}$, then

Next note that for $t\geq\max\{\sigma,R\}$ we have $\min\{t^{2}/\sigma^{2},t/R\}\geq t/\max\{\sigma,R\}$, so

Appendix C Tensor completion via unfolding

In this section we prove Theorem 1. In the original model, we observe exactly $\delta=|\textup{{E}}|/d^{k}$ fraction of the entries, uniformly at random. For convenience we now introduce the Bernoulli model where each entry is observed independently with chance $\delta$. Our results for the Bernoulli model transfer to the original model by a standard argument, which we provide below.

Let $Q$ be the orthogonal projection onto the span of onto the eigenspace of $B$ for eigenvalues $\geq\lambda_{\star}$. If $a=\lfloor k/2\rfloor$, then we can use $Q$ to define ${\mathcal{Q}}$ as in (10). Then let

We will consider $\widehat{\bm{T}}^{\star}$ with threshold $\lambda_{\star}=\lambda_{\star}(t)$ as given by (35).

Then, with $\smash{\widehat{\bm{T}}^{\star}}$ as above, we have

with probability at least $1-3d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$.

Let us discuss the choice of $t$ in Theorem 4. We wish to have a small error $\|\bm{T}-\widehat{\bm{T}}^{\star}\|_{\textup{F}}$, while ensuring that condition (36) is satisfied. First note that (36) cannot be satisifed at all unless we have $t^{1/2}\geq 32(k\log d)^{4}/d^{k/2-a}$. If we take $\epsilon\leq 1$ and set

then Theorem 4 gives $\|\bm{T}-\widehat{\bm{T}}^{\star}\|_{\textup{F}}\leq\epsilon\|\bm{T}\|_{\textup{F}}$. This choice of $\delta$ automatically satisfies the lower bound of (36). To satisfy the upper bound we require

Since $a\leq k/2$ and we aim for $\epsilon\leq 1/(k\log d)$ in the worse case, we shall set $t^{1/2}=(k\log d)^{8}\mu^{3/2}$. With this choice, (36) simplifies to

and we obtain $\|\bm{T}-\widehat{\bm{T}}^{\star}\|_{\textup{F}}\leq\epsilon\|\bm{T}\|_{\textup{F}}$ with

Then, as noted previously, the result of Theorem 4 (for the Bernoulli model) implies the result of Theorem 1 (for the original model) by a well-known argument:

The bound of Theorem 4 fails with probability tending to zero more rapidly than any polynomial of $d$. On the other hand, by construction, the probability of the event $|\textup{{E}}_{1}|=|\textup{{E}}_{2}|=\textsf{n}/2$ is lower bounded by a polynomial in n, so the result follows. ∎

We begin with a proof of our earlier remark (8); note however that this bound is not used in the proof of Theorems 1 or 4.

It follows from the decomposition $X^{(1)}=UV^{\sf t}$ that

which verifies the inductive hypothesis and proves the claim. ∎

The remainder of this section is devoted to the proof of Theorem 4.

lies in the kernel of $A_{1}$. Then $v=(A_{2}-A_{1})v$, so $\|v\|\leq\|A_{1}-A_{2}\|_{\textup{op}}\|v\|$. Since $\|A_{1}-A_{2}\|_{\textup{op}}<1$, it follows that $v=0$, a contradiction. It follows that the vectors $A_{1}x_{j}$ are linearly independent, which proves $\operatorname{\textup{{rank}}}A_{2}=r\leq\operatorname{\textup{{rank}}}A_{1}$ as claimed. ∎

with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$.

Recalling (22), the matrix $X$ is $(\lambda,\gamma,\rho)$-incoherent with $\lambda=\rho=1/\gamma=\bar{\varpi}$. The claim then follows by applying Corollary 3 (an additional factor $4$ in the bound arises since $\delta=2\delta_{1}$). ∎

with probability at least $1-(d_{1}+d_{2})\exp\{-\tfrac{3}{8}t\}$.

The claimed bound follows by the matrix Bernstein inequality (Proposition 4). ∎

C.2. Projection of original tensor

Recalling (10) and (34), we now compare the original tensor $\bm{T}$ and its projection $\bm{T}^{\star}={\mathcal{Q}}(\bm{T})$.

In particular, if $a=\lfloor k/2\rfloor$ then $\operatorname{\textup{{rank}}}{\mathcal{Q}}\leq r_{\circ}(k,\operatorname{\textup{{rank}}}X,d)$ where (cf. (10))

Let $P$ be the orthogonal projection onto the eigenspace of $XX^{\sf t}$ corresponding to eigenvalues $\geq 2\lambda_{\star}$; and note $\operatorname{\textup{{rank}}}(PQ)\leq\operatorname{\textup{{rank}}}P\leq\operatorname{\textup{{rank}}}X$. From Wedin’s theorem (Proposition 5),

which is less than one by assumption. Applying Lemma 14 then gives

proving the first assertion. The claimed bound on $\operatorname{\textup{{rank}}}{\mathcal{Q}}$ follows immediately from the fact that $\operatorname{\textup{{rank}}}(M_{1}\otimes M_{2})=\operatorname{\textup{{rank}}}(M_{1})\operatorname{\textup{{rank}}}(M_{2})$. ∎

Recall $X=\textup{{unfold}}^{a\times b}(\bm{T})$. By the triangle inequality and the assumed symmetry of $\bm{T}$, we have

where the maximum is taken over all $d^{b}\times d^{b}$ matrices $M$ with $\|M\|_{\textup{op}}\leq 1$. Then, with $P$ as in the proof of Lemma 17, we can expand,

and bound separately the two terms on the right-hand side. For the first term we have

from the definition of $P$. For the second term we have (cf. (59))

The claimed bound follows by noting that the matrix $(I^{(a)}-Q)XM$ has rank upper bounded by $\operatorname{\textup{{rank}}}X$, so its Frobenius norm is at most $(\operatorname{\textup{{rank}}}X)^{1/2}$ times its spectral norm. ∎

In view of Lemma 18, it is natural to optimize over the parameter $\lambda_{\star}$ by setting

Of course, in the application we have in mind, we cannot do this because $X$ is unknown. However, if the (known) matrix $B$ is sufficiently close to $XX^{\sf t}$, we can achieve a near-optimal bound by defining $\lambda_{\star}$ in terms of $B$ alone, without reference to $X$. In summary, we have:

with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$.

Since $t\geq 1$ and $\varpi=\alpha\textup{{r}}/\mu\geq 1$ (Remark 1), it follows from (36) that

Together with T2 and T3, we see that the conditions of Lemma 15 are satisfied with $\bar{\varpi}=\varpi$. It follows that, with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$,

where the last inequality is from (36). Therefore $\tfrac{3}{4}\|X\|_{\textup{op}}^{2}\leq\|B\|_{\textup{op}}\leq\tfrac{5}{4}\|X\|_{\textup{op}}^{2}$, so

(So far, it was not necessary for $\bm{T}$ to be symmetric.) Next, substituting (39) into the bound of Lemma 18 (and making use of the symmetry of $\bm{T}$) we find

where the last inequality is from T1. Finally, applying T3 and recalling $\|X\|_{\textup{F}}=\|\bm{T}\|_{\textup{F}}$, we conclude $\|\bm{T}-\bm{T}^{\star}\|_{\textup{F}}\leq 9\mu^{1/2}\eta(t)^{1/3}\|\bm{T}\|_{\textup{F}}$. The claim follows by recalling the definition of $\eta(t)$ from (35). ∎

C.3. Projection of observed tensor

Again recalling (10) and (34), we next compare $\bm{T}^{\star}={\mathcal{Q}}(\bm{T})$, (the projection of the original tensor) with $\widehat{\bm{T}}^{\star}={\mathcal{Q}}({\widehat{\bm{T}}})$ (the projection of the observed tensor).

with probability at least $1-d^{k}\exp\{-\tfrac{3}{8}(k\log d)^{2}\}$ conditional on $\textup{{E}}_{1}$.

Let $\bm{F}=\bm{T}-{\widehat{\bm{T}}}$; it follows from the definitions that $\bm{F}$ has entries

If $F=\textup{{unfold}}^{a\times b}(\bm{F})$ then we have

The claimed bound then follows from Lemma 16 (and using $2\delta_{2}\geq\delta$). ∎

In the setting of Lemma 20, suppose $\bm{T}$ satisfies T2 and T3, as well as

Then, conditional on $\textup{{E}}_{1}$, and with $\vartheta\equiv\alpha\textup{{r}}/(d^{k/2}\delta)$, we have

with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$.

Combining with (40) and substituting into Lemma 20 gives the claim. ∎

with probability at least $1-2d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$.

Fix $a=\lfloor k/2\rfloor$ and $b=\lceil k/2\rceil$. Recalling the proof of Corollary 19, with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$ the bounds (39) hold, in which case Lemma 17 gives $\operatorname{\textup{{rank}}}Q\leq\operatorname{\textup{{rank}}}X$. We also have $\operatorname{\textup{{rank}}}X\leq\textup{{r}}$ by T1. From (10), ${\mathcal{Q}}=A_{1}\otimes A_{2}$ where $A_{1}=Q$ and

As in the proof of Lemma 20 denote $\bm{F}=\bm{T}-{\widehat{\bm{T}}}$, and $F=\textup{{unfold}}^{a\times b}(\bm{F})$. Then $\bm{T}^{\star}-\widehat{\bm{T}}^{\star}={\mathcal{Q}}(\bm{F})$, and the matrix $\textup{{unfold}}^{a\times b}(\bm{T}^{\star}-\widehat{\bm{T}}^{\star})=A_{1}F(A_{2})^{\sf t}$ has rank upper bounded by the rank of $A_{1}=Q$. We have seen that with high probability $\operatorname{\textup{{rank}}}Q\leq\textup{{r}}$ — on this event,

Condition (40) is satisfied by our assumptions, so we can apply Corollary 21: conditional on $\textup{{E}}_{1}$ it holds with probability $\geq 1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$ that the right-hand side above is

where the last step uses T3. The claim follows since $\|X\|_{\textup{F}}=\|\bm{T}\|_{\textup{F}}$. ∎

The result now follows straightforwardly by collecting the estimates obtained above. By our assumptions on $\delta$ and r, the conditions of Corollaries 19 and 22 are satisfied. By Corollary 19, it holds with probability at least $1-d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$ that

By Corollary 22, it holds with probability at least $1-2d^{k}\exp\{-\tfrac{1}{8}(k\log d)^{2}\}$ that

Appendix D Overcomplete random three-tensors

In this section we prove Theorem 2. We have an underlying tensor

Equivalently, writing $A_{s}\equiv a_{s}(a_{s})^{\sf t}$, we have

where $G^{\textup{diag}}$ denotes the contribution from the diagonal terms $s=t$, while $G^{\textup{cross}}$ denotes the remaining contribution from pairs $s\neq t$.

As in the proof of Theorem 1, we work under a Bernoulli model for the partially observed tensor: define three $d\times d\times d$ arrays of i.i.d. ${\rm Ber}(\delta)$ random variables, denoted $I,J,K$. Define $\dot{\bm{Y}}=\bm{T}\odot I$, $\ddot{\bm{Y}}=\bm{T}\odot J$, $\dddot{\bm{Y}}=\bm{T}\odot K$. The observed version of $G$ is (cf. (14))

Throughout this Appendix, we use $f(d,r)\lesssim g(d,r)$ if $f(d,r)\leq(\log d)^{C}g(d,r)$ for some constant $C$, and $f(d,r)\asymp g(d,r)$ if $f(d,r)\lesssim g(d,r)$ and $g(d,r)\lesssim f(d,r)$.

Then it holds with very high probability that (cf. (17))

Theorem 2 is deduced from Theorem 5 in the same way that Theorem 1 is deduced from Theorem 4. ∎

We now collect some basic estimates on random vectors satisfying condition A3, which we repeat here for convenience:

Such vectors will be termed “$(\tau^{2}/d)$-subgaussian.”

where the first inequality holds for all $0\leq\psi<d$, and the second holds for all $0\leq\psi\leq d/2$.

which proves the first inequality by setting $\psi=2\lambda\tau^{2}$. Next note that for $0\leq t\leq 1/2$ we have $-\log(1-t)\leq t(1+t)$. The second inequality then follows, with $t=\psi/d$. ∎

Recall that if $Z$ is a non-negative random variable with finite mean, then

Therefore, for any $0\leq\theta\leq L$ we can bound

Setting $L=\tau^{2}(1+\psi/d)$ and rearranging gives

where the last inequality is by optimizing over $0\leq\psi\leq d/2$. Next consider (45), where we again set $L=\tau^{2}(1+\psi/d)$ with $0\leq\psi\leq d/2$, but now take $\theta\leq 1-1/(\log d)$. It follows from (46) that $(L-\theta)^{-1}\leq O((\log d)/L)\leq O((\log d)/\tau^{2})$. Substituting into (45) gives

where the last step is by optimizing over $0\leq\psi\leq d/2$ as before. This proves the first claim.

Applying Lemma 23 with $d=1$ gives (assuming $\theta<\min\{1,L\}$ and $0\leq\psi<1$)

If we take $\psi=2/3$, $L=\beta\tau^{2}\geq 1$, and $\theta\leq\min\{L,1\}/100$, then

where the last inequality is by taking $\beta=8+3\log(\tau^{2})$, and recalling $\theta\leq 1/100$. This proves the second claim. ∎

The following bound is very well known (see for instance [Ver12, Theorem 5.39]); we include the short proof here in order to have an explicit dependence on $\tau$.

Denote $x=a_{s}$ and consider $Z=xx^{t}-I/d$. Recalling (63), we have $\|Z\|_{\textup{op}}\leq 2\tau^{2}$ with very high probability. Write $A\preccurlyeq B$ to denote that $B-A$ is positive semidefinite. It holds for any constant $M\geq 0$ that

Taking norms (and applying the triangle inequality and Jensen’s inequality) gives

where the last inequality holds for sufficiently large $d$ by another application of (63). Combining with the truncated Bernstein bound (Proposition 6) gives, with very high probability,

The claimed bound follows by using the triangle inequality. ∎

D.2. Observation of contracted tensor, diagonal component

The key technical step in our result is the following estimate on $W$.

The observed version $W$ of $G$ can be decomposed analogously:

where, for each $s,t\leq r$, we define the $d^{2}\times d^{2}$ matrix

Since $W-G^{\textup{diag}}=(W^{\textup{diag}}-G^{\textup{diag}})+W^{\textup{cross}}$, the triangle inequality gives the claimed bound. ∎

We now prove (48) and (49). These proofs are slightly involved, and may not offer much insight on a casual reading. We supplement these proofs with an analysis of $G^{\textup{diag}}$ and $G^{\textup{cross}}$, given in Appendix E. In particular, our analysis of $W^{\textup{cross}}$ is modelled after the analysis of $G^{\textup{cross}}$ (which is easier, and corresponds to the special case $\delta=1$). Appendix E is not needed for the proof of Theorem 2 but may supply some intuition. We now turn to the analysis of

Recalling the definition (51), we conclude that with very high probability

Combining with (52) and the truncated Bernstein bound (Proposition 6) gives

D.3. Observation of contracted tensor, cross component

where $C_{st}$ is as in (47) and $A_{st}\equiv A_{s}\otimes A_{t}$.

By the symmetry assumption A1 and the matrix decoupling inequality (Proposition 8), it suffices to prove the bound of Proposition 28 for

in place of $W^{\textup{cross}}$. Recalling the notation $E_{ij}\equiv e_{i}(e_{j})^{\sf t}$, we have

where $C_{(ij)st}$ and $C_{st(fg)}$ are $d\times d$ matrices with entries

After some straightforward manipulations we find

with very high probability. The claimed bound follows from the triangle inequality. ∎

In the setting of Proposition 28, the matrix $W^{(ij)}$ of (55) satisfies

Fix $i,j$ and abbreviate $\Gamma_{st}\equiv C_{(ij)st}$, so $\Gamma_{st}$ is a $d\times d$ matrix with entries

It follows from the standard Bernstein inequality that, with very high probability,

Now denote $W_{st}\equiv\Gamma_{st}\odot A_{t}$, and note that

We can express $W_{st}=(\operatorname{\textup{{diag}}}a_{t})\Gamma_{st}(\operatorname{\textup{{diag}}}a_{t})$, so, with very high probability,

Conditional on $a_{s},I,J$, then the $W_{st}$ (indexed by $t\in[r]\setminus s$) are independent. For $f,g\leq d$ we have

where the last bound holds with very high probability over $a_{s},I,J$. Off the diagonal ($f\neq g$) we must have $\{u,v\}=\{f,g\}$, so

where the last bound holds with very high probability over $a_{s},J$. Then, with very high probability over $I$, the number of non-zero entries in $\Sigma_{st}$ is $\lesssim\max\{1,(d\delta)^{2}\}$, so

Combining the diagonal and off-diagonal estimates gives altogether

Combining with (57) and the truncated Bernstein bound (Proposition 6) gives

It then follows from the matrix Rademacher bound (Proposition 7) that

with very high probability. Combining with Lemma 25 gives

The claimed bound then follows using the assumptions $r\leq d^{2}$ and $\delta^{2}\max\{r,d\}\geq 1$. ∎

where the bound holds with very high probability over $J$, and the last step uses (53). The same argument as in Lemma 29 gives (using $r\leq d^{2}$ and $\max\{r,d\}\delta^{2}\geq 1$)

with very high probability. Combining the above estimates with the truncated matrix Bernstein inequality (Proposition 6) gives the claimed bound. ∎

D.4. Tensor completion algorithm

Recall $G=G^{\textup{diag}}+G^{\textup{cross}}$ from (42), and $W=W^{\textup{diag}}+W^{\textup{cross}}$ from (43). We have from Proposition 26 that, with very high probability,

Recall from (43) the formation of $W$ using indicators $I,J$. Let $K$ be an independent copy of $I$, and let ${\widehat{\bm{T}}}$ denote the tensor with entries $({\widehat{\bm{T}}})_{ijk}=\delta^{-1}K_{ijk}\bm{T}_{ijk}$. Define the estimator

In what follows we will show that $\widehat{\bm{T}}^{\star}$ is close to $\bm{T}$ in Frobenius norm, where

Recalling the proof of Proposition 33, we have

so altogether $\|\bm{T}\|_{\textup{F}}\asymp r^{1/2}$.

Denote $\theta_{st}\equiv\langle\bar{P}(a_{s}\otimes a_{s}),\bar{P}(a_{t}\otimes a_{t})\rangle$. By definition, $\|\bar{P}G^{\textup{diag}}\bar{P}\|_{\textup{op}}\leq 2\eta$, so

Let $(\mathfrak{s}_{s})_{s\leq r}$ be a collection of symmetric random signs: by assumption A1, the original tensor $\bm{T}$ is equidistributed as

Note that $\bm{T}$ and $\bm{T}^{\textup{sgn}}$ map to the same $G^{\textup{diag}}$, so the projection matrix $P$ is independent of the signs $\mathfrak{s}_{s}$. Therefore $\|\bm{T}(I_{d}\otimes\bar{P})\|_{\textup{F}}^{2}$ is equidistributed as

Recall from (61) that $|\theta_{ss}|\leq\eta^{1/2}\|a_{s}\|$, so the first term is $\lesssim\eta^{1/2}r$. Meanwhile, by combining (61) with the decoupling inequality and the Rademacher bound, the second term is $\lesssim\eta^{1/2}(r/d)^{1/2}$. The claimed bound follows. ∎

Since $\bar{Q}$ is a projection matrix we have $\|\bar{Q}\|_{\textup{op}}\leq 1$, so

by Lemma 31. Recall from (59) that $\|P\bar{Q}\|_{\textup{op}}\leq\epsilon/\eta\ll 1$; we then have

Lemma 14 gives $\operatorname{\textup{{rank}}}Q\leq r$, and combining with Lemma 16 gives

The result follows by setting $\eta$ equal to the parameter $\lambda_{\star}$ of the theorem statement, and then recalling the bound on $\epsilon$ from (58). ∎

Appendix E Remarks on contracted tensor

This section supplements Appendix D by analyzing $G$ (of (42)). As noted above, the estimates below are not required for the proof of Theorem 2. We include them because they may supply some intuition, and may be useful for related problems such as tensor decomposition.

For this component, we have a slightly better estimate if we make the additional assumption that $\tau^{2}\leq 21/20$. This is due to the following

Applying this corollary, we obtain the following estimates for the spectral norm of $G^{\textup{diag}}$:

There exists an absolute constant $c$ such that, with very high probability,

Suppose additionally that A3 is satisfied with $\tau^{2}\leq 21/20$; and that $(\log r)/(\log d)$ stays bounded away from infinity as well as from zero. Then there exists an absolute constant $c$ such that, with very high probability,

For any $s$ such that $a_{s}\neq 0$ we have

Since $r$ grows at least polynomially in $d$, Lemma 24 gives $\max_{s}\|a_{s}\|\geq 1-O(1)/\log d$. This implies the result of (a). Turning to the proof of (b), we will lower bound

From Lemma 23, if $x$ is $(\tau^{2}/d)$-subgaussian, then

so that $\langle x,v\rangle^{2}\leq(\log d)^{6/5}$ with very high probability. Taking a union bound over $r$ (and using that $r$ is at most polynomial in $d$), we conclude that the event

occurs with very high probability. Combining these gives for all $s\leq r$ that

In what follows, we use $c_{i}$ to denote positive absolute constants. By Lemma 24, since $r$ grows polynomially in $d$, the event

occurs with very high probability. Combining these gives for all $s\leq r$ that

By Corollary 32, using the additional assumption $\tau^{2}\leq 21/20$, the event

also occurs with very high probability. It follows that for all $s\leq r$,

Combining with the lower bound from (a) gives the result of (b). ∎

E.2. Contracted tensor, cross component

Recalling (42), we now turn to showing that

has smaller spectral norm than $G^{\textup{diag}}$. We follow a similar argument from [HSSS15, Propn. 5.5].

Recall the notation $A_{s}\equiv a_{s}(a_{s})^{\sf t}$. Let $(\mathfrak{s}_{s},\mathfrak{t}_{s})_{s\leq r}$ be a collection of i.i.d. symmetric random signs. By the symmetry assumption A1, $a_{s}$ is equidistributed as $\mathfrak{s}_{s}a_{s}$ where the $\mathfrak{s}_{s}$ are independent symmetric random signs, so $G^{\textup{cross}}$ is equidistributed as

In view of the decoupling inequality (Proposition 8), it is enough to prove the claimed bound for the matrix $G^{\textup{sgn}}$, which is defined as above but with $\mathfrak{t}_{t}$ in place of $\mathfrak{s}_{t}$. To this end, let us first bound the spectral norm of

Conditional on $a_{s}$, the summands $G_{st}\equiv\mathfrak{t}_{t}\langle a_{s},a_{t}\rangle A_{t}$ are independent with zero mean. Recalling (63) and (64), conditional on $a_{s}$ it holds with very high probability that

Next, arguing similarly as in the proof of Lemma 25, we have

It follows using the truncated Bernstein bound (Proposition 6) that, with very high probability,

for all $s\leq r$. It also holds with very high probability that $\max_{s}\|a_{s}\|^{2}\leq 2\tau^{2}$. Now consider

— recalling the matrix Rademacher bound (Proposition 7), we shall bound

Each $(A_{s}\otimes G_{s})(A_{s}\otimes G_{s})^{\sf t}$ is positive semidefinite, so

By the preceding estimates together with Lemma 25,

with very high probability. The claimed result follows by conditioning on the event that the above bound holds, and then applying Proposition 7. ∎