Exact tensor completion with sum-of-squares

Introduction

Algorithms and analyses for matrix and tensor completion come in three flavors:

algorithms analyzed by statistical learning tools like Rademacher complexity [SS05, BM16].

iterative algorithms like alternating minimization [JNS13, Har14, HW14].

algorithms analyzed by constructing dual certificates for convex programming relaxations [CR09, Gro11, Rec11].

While each of these flavors have different benefits, typically only algorithms of the third flavor achieve exact recovery. (The only exceptions to this rule we are aware of are a recent fast algorithm for matrix completion [JN15] and a recent analysis [GLM16] showing that the commonly used non-convex objective function for positive semidefinite matrix completion has no spurious local minima and thus stochastic gradient descent and other popular optimization programs can solve positive semidefinite matrix completion with arbitrary initialization.) For all other algorithms, the analysis exhibits a trade-off between reconstruction error and the required number of observations (even when there is no noise in the input).We remark that this trade-off is a property of the analysis and not necessarily the algorithm. For example, some algorithms of the first flavor are based on the same convex programming relaxations as exact recovery algorithms. Also for iterative algorithm, the trade-off between reconstruction error and number of sample comes from the requirement of the analysis that each iteration uses fresh samples. For these iterative algorithms, the number of samples depends only logarithmically on the desired accuracy, which means that these analyses imply exact recovery if the bit complexity of the entries is small.

A problem similar to matrix and tensor completion is matrix and tensor sensing. The goal is to recover an unknown low rank matrix or tensor from a small number of linear measurements. An interesting phenomenon is that for carefully designed measurements (which actually happen to be rank 1) it is possible to efficiently recover a $3$-tensor of rank $r$ with just $O(r^{2}\cdot n)$ measurements [FS12], which is better than the best bounds for tensor completion when $r\ll n^{0.5}$. We conjecture that for tensor completion from random entries the bound we obtain is up to logarithmic factors best possible among polynomial-time algorithms.

Our algorithm is based on sum-of-squares [Sho87, Par00, Las01], a very general and powerful meta-algorithm studied extensively in many scientific communities (see for example the survey [BS14]). In theoretical computer science, the main research focus has been on the capabilities of sum-of-squares for approximation problems [BBH+12], especially in the context of Khot’s Unique Games Conjecture [Kho02]. More recently, sum-of-squares emerged as a general approach to inference problems that arise in machine learning and have defied other algorithmic techniques. This approach has lead to improved algorithms for tensor decomposition [BKS15, GM15, HSSS16, MSS16], dictionary learning [BKS15, HM16], tensor principal component analysis [HSS15, RRS16, BGL16], planted sparse vectors [BKS14, HSSS16]. An exciting direction is also to understand limitations of sum-of-squares for inference problems on concrete input distributions [MW15, HSS15, BHK+16].

An appealing feature of the sum-of-squares method is that its capabilities and limitations can be understood through the lens of a simple but surprisingly powerful and intuitive restricted proof system called sum-of-squares or Positivstellensatz system [GV01, Gri01a, Gri01b]. A conceptual contribution of this work is to show that seminal results for inference problem like compressed sensing and matrix completion have natural interpretations as identifiability proofs in this system. Furthermore, we show that this interpretation is helpful in order to analyze more challenging inference problems like tensor completion. A promising future direction is to find more examples of inference problems where this lens on inference algorithms and identifiability proofs yields stronger provable guarantees.

A technical contribution of our work is that we develop techniques in order to show that sum-of-squares achieves exact recovery. Most previous works only showed that sum-of-squares gives approximate solutions, which in some cases can be turned to exact solutions by invoking algorithms with local convergence guarantees [GM15, BKS14] or solving successive sum-of-squares relaxations [MSS16].

1 Results

We note that the analysis also shows that the algorithm is robust to inverse polynomial amount of noise in the input (resulting in inverse polynomial amount of error in the output).

We remark that the running time of the algorithm depends polynomially on the bit complexity on $X$.

Techniques

Our goal is to efficiently reconstruct the unknown tensor $X$ from its restriction $X_{\Omega}$ to the entries in $\Omega$. Ignoring computational efficiency, we first ask if this task is information-theoretically possible. More concretely, for a given set of observations $X_{\Omega}$, how can we rule out that there exists another rank-$r$ orthogonal $3$-tensor $X^{\prime}\neq X$ that would give rise to the same observations $X^{\prime}_{\Omega}=X_{\Omega}$?We emphasize that we ask here about the uniqueness of $X$ for a fixed set of entries $\Omega$. This questions differs from asking about the uniqueness for a random set of entries, which could be answered by suitably counting the number of low-rank $3$-tensors.

A priori it is not clear how an answer to this information-theoretic question could be related to the goal of obtaining an efficient algorithm. However, it turns out that the sum-of-squares framework allows us to systematically translate a uniqueness proof to an algorithm that efficiently finds the solution. (In addition, this solution also comes with a short certificate for uniqueness.This certificate is closely related to certificates in the form of dual solutions for convex programming relaxations that are used in the compressed sensing and matrix completion literature.)

Let $\Omega\subseteq[n]^{3}$ be a set of entries and let $X=\sum_{i=1}^{r}\lambda_{i}\cdot u_{i}\otimes v_{i}\otimes w_{i}$ be a 3-tensor with $\lambda_{1},\ldots,\lambda_{r}\geqslant 0$.

in the monomial basis $T$ is supported on $\Omega$ so that $T(x,y,z)=\sum_{(i,j,k)\in\Omega}T_{ijk}\cdot x_{i}y_{j}x_{k}$,

evaluated over unit vectors, the 3-form $T$ is exactly maximized at the points $(u_{i},v_{i},w_{i})$ so that $T(u_{1},v_{1},w_{1})=\dots=T(u_{r},v_{r},w_{r})=1$ and ${T(x,y,z)}<1$ for all unit vectors $(x,y,z)\not\in\{(u_{i},v_{i},w_{i})\mid i\in[r]\}$.

At the same time, using that $T$ is supported on $\Omega$ and the fact that $X_{\Omega}=X^{\prime}_{\Omega}$,

Since $X^{\prime}$ minimizes $\sum_{i=1}^{r^{\prime}}\lambda^{\prime}_{i}$, equality has to hold in the previous inequality. It follows that every point $(u^{\prime}_{i},v^{\prime}_{i},w^{\prime}_{i})$ is equal to one of the points $(u_{j},v_{j},w_{j})$, because $T$ is uniquely maximized at the points $\{(u_{i},v_{i},w_{i})\mid i\in[r]\}$. Since we assumed that $\{(u_{i}\otimes v_{i}\otimes w_{i})_{\Omega}\}$ is linearly independent, we can conclude that $X=X^{\prime}$.

When we show that such a 3-linear form $T$ exists, we will actually show something stronger, namely that the second property is not only true but also has a short certificate in form of a “degree-4 sum-of-squares proof”, which we describe next. This certificate also enables us to efficiently recover the missing tensor entries.

Furthermore, we require that the kernel of $M$ is precisely the span of the vectors $\{(u_{i},v_{i}\otimes w_{i})\mid i\in[r]\}$. Let’s see that this matrix $M$ certifies that $T$ has the property that over unit vectors it is exactly maximized at the desired points $(u_{i},v_{i},w_{i})$. Let $u,v,w$ be unit vectors such that $(u,v,w)$ is not a multiple of one of the vectors $(u_{i},v_{i},w_{i})$. Then by orthogonality, both $(u,v\otimes w)$ and $(-u,v\otimes w)$ have non-zero projection on the orthogonal complement of the kernel of $M$. Therefore, the bounds $0<\langle(u,v\otimes w),M(u,v\otimes w)\rangle=2-2p(u,v,w)$ and $0<\langle(-u,v\otimes w),M(-u,v\otimes w)\rangle=2+2p(u,v,w)$ together give the desired conclusion that $\lvert T(u,v,w)\rvert<1$.

The above discussion shows that in order to achieve reconstruction it is enough to show that uniqueness certificates of the form above exist. We show that these certificates exists with high probability if we choose $\Omega$ to be a large enough random subset of entries (under suitable assumptions on $X$). Our existence proof is based on a randomized procedure to construct such a certificate heavily inspired by similar constructions for matrix completion [Gro11, Rec11]. (We note that this construction uses the unknown tensor $X$ and is therefore not “constructive” in the context of the recovery problem.)

every unknown entry $(i,j,k)\not\in\Omega$ satisfies $\langle e_{i},T(e_{j}\otimes e_{k})\rangle=0$,

every index $i\in[r]$ satisfies $u_{i}=T(v_{i}\otimes w_{i})$,

the matrix $\sum_{a=1}^{n}T_{a}\otimes{T_{a}}{}^{\mkern-4.0mu\intercal}-\sum_{i=1}^{r}(v_{i}\otimes w_{i})(v_{i}\otimes w_{i}){}^{\mkern-4.0mu\intercal}$ has spectral norm at most $0.01$.

We note that the uniqueness certificates for matrix completion [Gro11, Rec11] have similar requirements. The key difference is that we need to control the spectral norm of an operator that depends quadratically on the constructed object $T$ (as opposed to a linear dependence in the matrix completion case). Combined with the fact that the construction of $T$ is iterative (about $\log n$ steps), the spectral norm bound unfortunately requires significant technical work. In particular, we cannot apply general matrix concentration inequalities and instead apply the trace moment method. (See Section 5.)

We also note that the fact that the above requirements allow us to construct the certifcate $M$ is not immediate and requires some new ideas about matrix representations of polynomials, which might be useful elsewhere. (See Appendix A.)

Finally, we note that the transformation applied to $T$ in order to obtain the matrix for the third condition above appears in many works about 3-tensors [HSS15, BM16] with the earliest appearance in a work on refutation algorithms for random 3-SAT instances (see [FO07]).

The iterative construction of the linear operator $T$ exactly follows the recipe from matrix completion [Gro11, Rec11]. Let $\mathcal{R}_{\Omega}$ be the projection operator into the linear space of operators $T$ that satify the first requirement. Let $\mathcal{P}_{T}$ be the (affine) projection operator into the affine linear space of operators $T$ that satisfy the second reqirement. We start with $T^{(0)}=X$. At this point we satisfy the second condition. (Also the matrix in the third condition is .) In order to enforce the first condition we apply the operator $\mathcal{R}_{\Omega}$. After this projection, the second condition is most likely no longer satisfied. To enforce the second condition, we apply the affine linear operator $\mathcal{P}_{T}$ and obtain $T^{(1)}=\mathcal{P}_{T}(\mathcal{R}_{\Omega}X)$. The idea is to iterate this construction and show that after a logarithmic number of iterations both the first and second condition are satisfied up to an inverse polynomially small error (which we can correct in a direct way). The main challenge is to show that the iterates obtained in this way satisfy the desired spectral norm bound. (We note that for technical reasons the construction uses fresh randomness $\Omega$ for each iteration like in the matrix completion case [Rec11, Gro11]. Since the number of iterations is logarithmic, the total number of required observations remains the same up to a logarithmic factor.)

Preliminaries

Tensor completion algorithm

In this section, we show that the following algorithm for tensor completion succeeds in recovering the unknown tensor from partial observations assuming the existence of a particular linear operator $T$. We will state conditions on the unknown tensor that imply that such a linear operator exists with high probability if the observed entries are chosen at random. We use essentially the same convex relaxation as in [BM16] but our analysis differs significantly.

We reason about the recovery guarantees of the algorithm in terms of the following notion of certifcate.

the vectors $\{(u_{i}\otimes v_{j}\otimes w_{k})_{\Omega}\mid(i,j,k)\in S\}$ are linearly independent, where $S\subseteq[n]^{3}$ is the set of triples with at least two identical indices from $[r]$,

every entry $(a,b,c)\not\in\Omega$ satisfies $\langle e_{a},T(e_{b}\otimes e_{c})\rangle=0$,

the following matrix has spectral norm at most $0.01$,

where $\{T_{a}\}$ are matrices such that $\langle x,T(y\otimes x)\rangle=\sum_{a=1}^{n}x_{a}\cdot\langle y,T_{a}z\rangle$.

In Section 4.4, we prove that existence of such certifcates implies that the above algorithm successfully recovers the unknown tensor, as formalized by the following theorem.

In Section 4.5, we show that degree-4 certificates are likely to exist when $\Omega$ is a random set of appropriate size.

Taken together the two theorems above imply our main result Theorem 1.1.

Unfortunately the proof of Theorem 4.3 requires extremely technical spectral norm bounds for random matrices.

It turns out that less technical norm bounds suffice if we use degree 6 sum-of-squares relaxations. For this more powerful algorithm, weaker certificates are enough to ensure exact recovery and the proof that these weaker certificates exist with high probability is considerably easier than the proof that degree-4 certificates exist with high probability.

In the following we describe this weaker notion of certificates and state their properties. In the subsequent sections we prove properties of these certificates are enough to imply our main result Theorem 1.1.

the vectors $\{(u_{i}\otimes v_{i}\otimes w_{i})_{\Omega}\}_{i\in[r]}$ are linearly independent,

every entry $(a,b,c)\not\in\Omega$ satisfies $\langle T,(e_{a}\otimes e_{b}\otimes e_{c})\rangle=0$,

where $T^{\prime}=T-\sum_{i=1}^{r}u_{i}\otimes v_{i}\otimes w_{i}$ and $\varepsilon>0$ is an absolute constant (say $\varepsilon=10^{-6}$).

In the following sections we prove that higher-degree certificates imply that Section 4.1 successfully recovers the desired tensor and that they exist with high probability for random $\Omega$ of appropriate size.

2 Higher-degree certificates imply exact recovery

We are to show that a higher-degree certificate in the sense of Definition 4.4 implies that Section 4.1 reconstructs the partially observed tensor exactly. A key step of this proof is the following lemma about expectation values of higher degree pseudo-distributions.

To prove this lemma it will be useful to introduce the sum-of-squares proof system. Before doing that let us observe that the lemma indeed allows us to prove that Section 4.1 works.

By Lemma 4.5 and the optimality of $\mu$, it follows that

We will change coordinates such that $u_{i}=v_{i}=w_{i}=e_{i}$ is the $i$-th coordinate vector for every $i\in[n]$. Then, the conditions on $T$ in Definition 4.4 imply that

where $T^{\prime}$ is a 3-linear form with the property that $T^{\prime}(x,x,x)$ does not contain squares (i.e. is multilinear). Furthermore, the conditions imply the following SOS proofs for $T^{\prime}$:

$\emptyset\vdash_{4}T^{\prime}(x,y,z)\leqslant\varepsilon\cdot\left(\lVert x\rVert+\lVert y\rVert^{2}\cdot\lVert z\rVert^{2}\right)$,

$\emptyset\vdash_{4}T^{\prime}(x,y,z)\leqslant\varepsilon\cdot\left(\lVert y\rVert+\lVert x\rVert^{2}\cdot\lVert z\rVert^{2}\right)$,

$\emptyset\vdash_{4}T^{\prime}(x,y,z)\leqslant\varepsilon\cdot\left(\lVert z\rVert+\lVert x\rVert^{2}\cdot\lVert y\rVert^{2}\right)$.

The following lemma gives an upper bound on one of the parts in Eq. 4.7.

For $\mathcal{A}=\{\lVert y\rVert^{2}=1\}$, the following inequality has a degree-6 sum-of-squares proof,

We bound the left-hand side in the lemma as follows,

We can further bound $\sum_{i}y_{i}^{2}z_{i}^{2}$ as follows,

We can prove a different bound on $\sum_{i}y_{i}^{2}z_{i}^{2}$ as follows,

By combining these three inequalities, we obtain the inequality

By symmetry between $z$ and $x$, the same inequality holds with $x$ and $z$ exchanged. Combining these symmetric inequalities, we obtain the desired inequality

It remains to bound the second part in Eq. 4.7, which the following lemma achieves.

$A\vdash_{6}T^{\prime}(x,y,z)\leqslant\frac{3\varepsilon}{2}\sum_{i}{\sum_{j\neq i}{y^{2}_{i}\left(x^{2}_{j}+z^{2}_{j}+\frac{1}{2}y^{2}_{j}(||x||^{2}+||z||^{2})\right)}}$

It is enough to show the following inequality for all $i\in[n]$,

By symmetry it suffices to consider the case $i=1$. Let $x^{\prime}=x-x_{1}\cdot e_{1}$, $y^{\prime}=y-y_{1}\cdot e_{1}$, and $z^{\prime}=z-z_{1}\cdot e_{1}$. We observe that

$\mathcal{A}\vdash_{4}T^{\prime}({x_{1}}e_{1},y^{\prime},z^{\prime})\leqslant\frac{\varepsilon}{2}\left(x^{2}_{1}||y^{\prime}||^{2}+||z^{\prime}||^{2}\right)\leqslant\frac{\varepsilon}{2}\sum_{j\neq 1}(y^{2}_{j}||x||^{2}+z^{2}_{j})$

$\mathcal{A}\vdash_{4}T^{\prime}(x^{\prime},y_{1}{e_{1}},z^{\prime})\leqslant\frac{\varepsilon}{2}\left(||x^{\prime}||^{2}{y^{2}_{1}}+||z^{\prime}||^{2}\right)\leqslant\frac{\varepsilon}{2}\sum_{j\neq 1}(x^{2}_{j}+z^{2}_{j})$

$\mathcal{A}\vdash_{4}T^{\prime}(x^{\prime},y^{\prime},z_{1}{e_{1}})\leqslant\frac{\varepsilon}{2}\left(z^{2}_{1}||y^{\prime}||^{2}+||x^{\prime}||^{2}\right)\leqslant\frac{\varepsilon}{2}\sum_{j\neq 1}(y^{2}_{j}||z||^{2}+x^{2}_{j})$

$\mathcal{A}\vdash_{4}T^{\prime}(x^{\prime},y^{\prime},z^{\prime})\leqslant\frac{\varepsilon}{2}\left(||x^{\prime}||^{2}||y^{\prime}||^{2}+||z^{\prime}||^{2}\right)\leqslant\frac{\varepsilon}{2}\sum_{j\neq 1}(x^{2}_{j}+z^{2}_{j})$

where the absolute constant hidden by $O(\cdot)$ notation is at most $10$. Therefore for $\varepsilon<1/100$, as we assumed in Definition 4.4, we get a SOS proof of the inequality,

This SOS proof implies that that every degree-6 pseudo-distribution $\mu(x,y,z)$ with $\mu\models\mathcal{A}$ satisfies the desired inequality,

3 Constructing the certificate T𝑇T

In this section we give a procedure for constructing the certificate $T$. This construction is directly inspired by the construction of the dual certificate in [Gro11, Rec11] (sometimes called quantum golfing). We will then prove that $T$ satisfies all of the conditions for a higher-degree certificate of $\Omega$. In Section 4.5 we will show that $T$ also satisfies the conditions for a degree-4 certificate for $\Omega$.

where $\Omega_{1},\ldots,\Omega_{k}$ are iid samples from the same distribution as $\Omega$.

By induction, we can show the following lemma about linear constraints that the constructed stensors $T^{(k)}$ satisfy.

For every $k\geqslant 1$, the tensor $T^{(k)}$ satisfies $(T)_{\Omega}=T$ and

Here, $P(P\bar{R}_{\Omega_{k}})\cdots(P\bar{R}_{\Omega_{1}})[X]$ is an error term that decreases geometrically. In the parameter regime of Theorem 4.3, the norm of this term is $n^{-\omega(1)}$ for some $k=(\log n)^{O(1)}$.

The following lemma shows that it is possible to correct such small errors. This lemma also implies that the linear independence condition in Definition 4.1 is satisfied with high probability. (Therefore, we can ignore this condition in the following.)

Let $S\subseteq[n]^{3}$ be such that $P$ is the projector to the vectors $u_{i}\otimes v_{j}\otimes w_{k}$ with $(i,j,k)\in S$. By construction of $P$ we have $\lvert S\rvert\leqslant 3rn$. In order to show the conclusion of the lemma it is enough to show that the vectors $(u_{i}\otimes v_{j}\otimes w_{k})_{\Omega}$ with $(i,j,k)\in S$ are well-conditioned in the sense that the ratio of the largest and smallest singular value is $O(1)$. This fact follows from standard matrix concentration inequalities. See Lemma 4.12. ∎

The main technical challenge is to show that the construction satisfies the condition that the following degree 4 polynomials are sums of squares (where $T^{\prime}=T-X$).

We show how to prove the first statement, the other statements can be proved with symmetrical arguments. To prove the first statement, we decompose $T^{\prime}$ into pieces of the form $(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$, $P^{\prime}(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ (where $P^{\prime}$ is a part of $P$), or $E$. For each piece $A$, we prove a norm bound $\lVert\sum_{a}{A_{a}\otimes A_{a}^{T}}\rVert\leqslant B$. Since $\sum_{a}{A_{a}\otimes A_{a}^{T}}$ represents the same polynomial as ${A}{}^{\mkern-4.0mu\intercal}A$, this proves that $B\lVert y\rVert^{2}\lVert z\rVert^{2}-{(y\otimes z)}{}^{\mkern-4.0mu\intercal}{A}{}^{\mkern-4.0mu\intercal}A(y\otimes z)$ is a degree 4 sum of squares. Now note that ${(y\otimes z)}{}^{\mkern-4.0mu\intercal}{A}{}^{\mkern-4.0mu\intercal}A(y\otimes z)-\sqrt{B}{x}{}^{\mkern-4.0mu\intercal}A(y\otimes z)-\sqrt{B}{(y\otimes z)}{}^{\mkern-4.0mu\intercal}{A}{}^{\mkern-4.0mu\intercal}x+B\lVert x\rVert^{2}$ is also a sum of squares. Combining these equations and scaling we have that $\lVert x\rVert^{2}+\lVert y\rVert^{2}\lVert z\rVert^{2}-\frac{2}{\sqrt{B}}{x}{}^{\mkern-4.0mu\intercal}A(y\otimes z)$ is a degree 4 sum of squares.

Thus, it is sufficient to prove norm bounds on $\lVert\sum_{a}{A_{a}\otimes A_{a}^{T}}\rVert$. We have an appropriate bound in the case when $A=E$ because $E$ has very small Frobenius norm. For the cases when $A=(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ or $A=P(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$, we use the following theorem

Let $A=(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ or $P^{\prime}(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ where $P^{\prime}$ is a part of $P$. There is an absolute constant $C$ such that for any $\alpha>1$ and $\beta>0$,

as long as $m>C\alpha\beta\mu^{\frac{3}{2}}rn^{1.5}\cdot\log(n)$ and $m>C\alpha\beta\mu^{2}rn\log(n)$.

This theorem follows directly from combining Proposition 5.10, Theorem 6.1, Theorem 7.1, and Theorem 8.1. ∎

In this section, we prove a spectral norm bound that allows us to correct error terms that are left at the end of the construction. The proof uses the by now standard Matrix Bernstein concentration inequality. Similar proofs appear in the matrix completion literature [Gro11, Rec11].

Let $S\subseteq[n]^{3}$. Suppose $m=\mu\lvert S\rvert(\log n)^{C}$ for an absolute constant $C\geqslant 1$. Then with probability $1-n^{\omega(1)}$ over the choice of $\Omega$, the vectors $(u_{i}\otimes v_{j}\otimes w_{k})_{\Omega}$ for $(i,j,k)\in S$ are well-conditioned in the sense that the ratio between the largest and smallest singular value is at most $1.1$.

For $s=(i,j,k)\in S$, let $y_{s}=u_{i}\otimes v_{j}\otimes w_{k}$. Let $\Omega=\{\omega_{1},\ldots,\omega_{m}\}$, where $\omega_{1},\ldots,\omega\in[n]^{3}$ are sampled uniformly at random with replacement. Let $A$ be the $S$-by-$S$ Gram matrix of the vectors $(y_{s})_{\Omega}$. Then, $A$ is the sum of $m$ identically distributed rank-1 matrices $A_{i}$,

4 Degree-4 certificates imply exact recovery

In this section we prove Theorem 4.2. We need the following technical lemma, which we prove in Appendix A.

We can now prove that certificates in the sense of Definition 4.1 imply that our algorithm successfully recoves the unknown tensor.

Let $T$ be a certificate in the sense of Definition 4.1.

Let $T_{a}$ be matrices such that $\langle x,T(x\otimes y)\rangle=\sum_{a}x_{a}\cdot T_{a}(y,z)$. Since $\lVert x\rVert^{2}+\sum_{a=1}^{n}T_{a}(y,z)^{2}-2\langle x,T(y\otimes z)\rangle=\lVert x-T(y\otimes z)\rVert$ is a sum of squares of polynomials, it will be enough to find a positive semidefinite matrix that represents the polynomial $\lVert y\rVert^{2}\cdot\lVert z\rVert^{2}-\sum_{a=1}^{n}T_{a}(y,z)^{2}$. (This step is a polynomial version of the Schur complement condition for positive semidefiniteness.) Let $R$ be the following linear operator

$R$ satisfies the requirement of Lemma 4.13.

Consider $\langle(v_{j}\otimes w_{k}),R(v_{j}\otimes w_{j})\rangle$. Since $v_{j}$ is repeated, the value of this expression will be the same if we replace $R$ by an $R_{2}$ which represents the same polynomial. Thus, we can replace $R$ by $R_{2}=\sum_{a=1}^{n}{{T_{a}}{}^{\mkern-4.0mu\intercal}T_{a}}-\sum_{i=1}^{r}(v_{i}\otimes w_{i})(v_{i}\otimes w_{i}){}^{\mkern-4.0mu\intercal}={T}{}^{\mkern-4.0mu\intercal}T-\sum_{i=1}^{r}(v_{i}\otimes w_{i})(v_{i}\otimes w_{i}){}^{\mkern-4.0mu\intercal}$

We now observe that $\langle(v_{j}\otimes w_{k}),R_{2}(v_{j}\otimes w_{j})\rangle=\langle(v_{j}\otimes w_{k}),{T}{}^{\mkern-4.0mu\intercal}(u_{j})-(v_{j}\otimes w_{j})\rangle=0$. By a symmetrical proof, $\langle(v_{j}\otimes w_{k}),R(v_{k}\otimes w_{k})\rangle=0$ as well. ∎

By Lemma Lemma 4.13, there exists a self-adjoint linear operator $R^{\prime}$ that represents the same polynomial as $R$, has spectral norm $\lVert R^{\prime}\rVert\leqslant 10\lVert R\rVert\leqslant 0.1$, and sends all vectors $v_{i}\otimes w_{i}$ to . Since $R^{\prime}$ sends all vectors $v_{i}\otimes w_{i}$ to and $\lVert R^{\prime}\rVert\leqslant 0.1$, the following matrix

has $r$ eigenvalues of value $1$ (corresponding to the space spanned by $v_{i}\otimes w_{i}$) and all other eigenvalues are at most $0.1$ (because the non-zero eigenvalues of $R^{\prime}$ have eigenvectors orthogonal to all $v_{i}\otimes w_{i}$). At the same time, $R^{\prime\prime}$ represents the following polynomial,

Let $P$ be a positive semidefinite matrix that represents the polynomial $\lVert x\rVert^{2}+\sum_{a=1}^{n}T_{a}(y,z)^{2}-2\langle x,T(y\otimes z)\rangle$ (such a matrix exists because the polynomial is a sum of squares). We choose $M$ as follows

We conclude that $\langle M,Y\rangle=0$, which means that the range of $Y$ is contained in the kernel of $M$. Therefore, $Y=\sum_{i,j=1}^{r}\gamma_{i,j}\cdot(u_{i},v_{i}\otimes w_{i}){(u_{j},v_{j}\otimes w_{j})}{}^{\mkern-4.0mu\intercal}$ for scalars $\{\gamma_{i,j}\}$. We claim that the multipliers must satisfy $\gamma_{i,i}=\lambda_{i}$ and $\gamma_{i,j}=0$ for all $i\neq j\in[r]$. Indeed since $\mu$ matches the observations in $\Omega$,

Since the vectors $(u_{i}\otimes v_{j}\otimes w_{j})_{\Omega}$ are linearly independent, we conclude that $\gamma_{i,j}=\lambda_{i}\cdot\delta_{ij}$ as desired. (This linear independence was one of the requirements of the certificate in Definition 4.1.) ∎

5 Degree-4 certificates exist with high probability

In this section we show that our certificate $T$ in fact satisfies the conditions for a degree-4 certificate, proving Theorem 4.3.

We use the same construction as in Section 4.3. The main, remaining technical challenge for Theorem 4.3 is to show that the construction satisfies the spectral norm condition of Definition 4.1. This spectral norm bound follows from the following theorem which we give a proof sketch for in Appendix B.

Let $A=(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ or $P(\bar{R}_{\Omega_{l}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ and let $B=(\bar{R}_{\Omega_{l^{\prime}}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$ or $P(\bar{R}_{\Omega_{l^{\prime}}}P)\cdots(\bar{R}_{\Omega_{1}}P)(\bar{R}_{\Omega_{0}}X)$. There is an absolute constant $C$ such that for any $\alpha>1$ and $\beta>0$,

as long as $m>C\alpha\beta\mu^{\frac{3}{2}}rn^{1.5}\cdot\log(n)$ and $m>C\alpha\beta\mu^{2}rn\log(n)$.

If it were true in general that $||\sum_{a}{A_{a}\otimes B^{T}_{a}}||\leqslant\sqrt{||\sum_{a}{A_{a}\otimes A^{T}_{a}}||}\sqrt{||\sum_{a}{B_{a}\otimes B^{T}_{a}}||}$ then it would be sufficient to use Theorem 4.11 and we would not need to prove Theorem 4.15. Unfortunately, this is not true in general.

That said, it may be possible to show that even if we do not know directly that $||\sum_{a}{A_{a}\otimes B^{T}_{a}}||$ is small, since $||\sum_{a}{A_{a}\otimes A^{T}_{a}}||$ and $||\sum_{a}{B_{a}\otimes B^{T}_{a}}||$ are both small there must be some alternative matrix representation of $\sum_{a}{A_{a}\otimes B^{T}_{a}}$ which has small norm, and this is sufficient. We leave it as an open problem whether this can be done.

We have now all ingredients to prove Theorem 4.3.

Let $k=(\log n)^{C}$ for some absolute constant $C\geqslant 1$. Let $E=(-1)^{k}P(P\bar{R}_{\Omega_{k}})\cdots(P\bar{R}_{\Omega_{1}})[X]$. By Lemma 4.10 there exists $Y$ with $(Y)_{\Omega}=Y$ and $P[Y]=E$ such that $\lVert Y\rVert_{F}\leqslant O(1)\lVert E\rVert$. We let $T=T^{(k)}+Y$. This tensor satisfies the desired linear constraints $(T)_{\Omega}=T$ and $P[T]=X$. Since $E$ has the form of the matrices in Theorem 4.15, the bound in Theorem 4.15 implies $\lVert E\rVert_{F}\leqslant 2^{-k}\cdot n^{10}\leqslant n^{-C+10}$. (Here, we use that the norm in the conclusion of Theorem 4.15 is within a factor of $n^{10}$ of the Frobenius norm.)

We are to prove that the following matrix has spectral norm bounded by $0.01$,

Matrix norm bound techniques

In this section, we describe the techniques that we will use to prove probabilistic norm bounds on matrices of the form $Y=\sum_{a}{(\bar{R}_{\Omega}A)_{a}\otimes(\bar{R}_{\Omega}A)^{T}_{a}}$. We will prove these norm bounds using the trace moment method, which obtains probabilistic bounds on the norm of a matrix $Y$ from bounds on the expected value of $tr((YY^{T})^{q})$ for sufficiently large $q$. This will require analyzing $tr((YY^{T})^{q})$, which will take the form of a sum of products, where the terms in the product are either entries of $A$ or terms of the form $\bar{R}_{\Omega}(a,b,c)$ where $\bar{R}_{\Omega}(a,b,c)=\frac{n^{3}}{m}-1$ if $(a,b,c)\in\Omega$ and $-1$ otherwise. To analyze $tr((YY^{T})^{q})$, we will group products together which have the same expected behavior on the $\bar{R}_{\Omega}(a,b,c)$ terms, forming smaller sums of products. For each of these sums, we can then use the same bound on the expected behavior of the $\bar{R}_{\Omega}(a,b,c)$ terms for each product in the sum. This allows us to move this bound outside of the sum, leaving us with a sum of products of entries of $A$. We will then bound the value of these sums by carefully choosing the order in which we sum over the indices.

In the reainder of this section and in the next two sections, we allow for our tensors to have asymmetric dimensions. We account for this with the following definitions.

We define $n_{1}$ to the dimension of the $u$ vectors, $n_{2}$ to be the dimension of the $v$ vectors, and $n_{3}$ to be the dimension of the $w$ vectors. We define $n_{max}=\max{\{n_{1},n_{2},n_{3}\}}$

We use the trace moment method through the following proposition and corollary.

For any random matrix $Y$, for any integer $q\geqslant 1$ and any $\varepsilon>0$,

By Markov’s inequality, for all integers $q\geqslant 1$ and all $\varepsilon>0$

The result now follows from the observation that if $||Y||>\sqrt[2q]{\frac{E\left[tr((YY^{T})^{q})\right]}{\varepsilon}}$ then $tr((YY^{T})^{q})>\frac{E\left[tr((YY^{T})^{q})\right]}{\varepsilon}$. ∎

For a given $p\geqslant 1$, $r\geqslant 0$, $n>0$, and $B>0$, for a random matrix $Y$, if $E\left[tr\left((YY^{T})^{q}\right)\right]\leqslant({q^{p}}B)^{2q}n^{r}$ for all integers $q>1$ then for all $\beta>0$,

We take $\varepsilon=n^{-\beta}$ and we choose $q$ to minimize $\sqrt[2q]{\frac{({q^{p}}B)^{2q}n^{r}}{\varepsilon}}=B{q^{p}}n^{\frac{r+\beta}{2q}}$. Setting the derivative of this expression to we obtain that $(\frac{p}{q}-\frac{r+\beta}{2q^{2}}\ln{n})B{q^{p}}n^{\frac{r+\beta}{2q}}=0$, so we want $q=\frac{r+\beta}{2p}\ln{n}$. However, $q$ must be an integer, so we instead take $q=\lceil{\frac{r+\beta}{2p}\ln{n}}\rceil$. With this $q$, we have that

Applying Proposition 5.2 with $q$, we obtain that

2 Partitioning by intersection pattern

As discussed at the beginning of the section, $E\left[tr((YY^{T})^{q})\right]$ will be a sum of products, where part of these products will be of the form $\prod_{i=1}^{2q^{\prime}}{\bar{R}_{\Omega}(a_{i},b_{i},c_{i})}$. Here, $q^{\prime}$ may or may not be equal to $q$, in fact we will often have $q^{\prime}=2q$ because each $Y$ will contribute two terms of the form $\bar{R}_{\Omega}(a,b,c)$ to the product. To handle this part of the product, we partition the terms of our sum based on the intersection pattern of which triples $(a_{i},b_{i},c_{i})$ are equal to each other. Fixing an intersection pattern determines the expected value of $\prod_{i=1}^{2q^{\prime}}{\bar{R}_{\Omega}(a_{i},b_{i},c_{i})}$.

We define an intersection pattern to be a set of equalities and inequalities satisfying the following conditions

All of the equalities and inequalities are of the form $(a_{i_{1}},b_{i_{1}},c_{i_{1}})=(a_{i_{2}},b_{i_{2}},c_{i_{2}})$ or $(a_{i_{1}},b_{i_{1}},c_{i_{1}})\neq(a_{i_{2}},b_{i_{2}},c_{i_{2}})$, respectively.

For every $i_{1},i_{2}$, either $(a_{i_{1}},b_{i_{1}},c_{i_{1}})=(a_{i_{2}},b_{i_{2}},c_{i_{2}})$ is in the intersection pattern or $(a_{i_{1}},b_{i_{1}},c_{i_{1}})\neq(a_{i_{2}},b_{i_{2}},c_{i_{2}})$ is in the intersection pattern

All of the equalities and inequalities are consistent with each other, i.e. there exist values of $(a_{1},b_{1},c_{1}),\cdots,(a_{2q},b_{2q},c_{2q})$ satisfying all of the equalities and inequalities in the intersection pattern.

$E\left[\bar{R}_{\Omega}(a,b,c)\right]=0$

For all $k>1$, $E\left[\left(\bar{R}_{\Omega}(a,b,c)\right)^{k}\right]\leqslant\left(\frac{{n_{1}}{n_{2}}{n_{3}}}{m}\right)^{k-1}$

For a given intersection pattern, if there is any triple $(a,b,c)$ which appears exactly once, $E\left[\prod_{i=1}^{2q^{\prime}}{\bar{R}_{\Omega}(a_{i},b_{i},c_{i})}\right]=0$. Otherwise, letting $z$ be the number of distinct triples, $E\left[\prod_{i=1}^{2q^{\prime}}{\bar{R}_{\Omega}(a_{i},b_{i},c_{i})}\right]\leqslant\left(\frac{{n_{1}}{n_{2}}{n_{3}}}{m}\right)^{2q^{\prime}-z}$

for a given intersection pattern, let $(a_{i_{1}},b_{i_{1}},c_{i_{1}}),\cdots,(a_{i_{z}},b_{i_{z}},c_{i_{z}})$ be the distinct triples and let $c_{j}$ be the number of times the triple $(a_{i_{j}},b_{i_{j}},c_{i_{j}})$ appears. We have that

If $c_{j}=1$ for any $j$ then this expression is . Otherwise,

3 Bounding sums of products of tensor entries

In this subsection, we describe how to bound the sum of products of tensor entries we obtain for a given intersection pattern after moving our bound on the expected value of the $\bar{R}_{\Omega}(a,b,c)$ terms outside the sum. We represent such a product with a hypergraph as follows.

Given a set of distinct indices and a set of tensor entries on those indices, let $H$ be the hypergraph with one vertex for each distinct index and one hyperedge for each tensor entry, where the hyperedge consists of all indices contained in the tensor entry. If the tenor entry appears to the pth power, we take this hyperedge with multiplicity $p$.

With this definition in mind, we will first preprocess our products.

We will preprocess the tensor entries so that every entry appears to an even power using the inequality $|ab|\leqslant\frac{1}{2}(a^{2}+b^{2})$. This has the effect of taking two hyperedges of our choice in $H$ and replacing them with one doubled hyperedge or the other (we have to consider both possibilities). Note that this step makes all of our terms positive and can only increase their magnitude, so the result will be an upper bound on our actual sum.

We will add the missing terms to our sum so that for we sum over every possibility for the distinct indices (even the possibilities which make several of these indices equal and would put us in a different intersection pattern). Note that this can only increase our sum.

It is important that we first bound the expected value of the $\bar{R}_{\Omega}(a,b,c)$ terms and move this bound outside of our sum before adding the missing terms to the sum.

After preprocessing our products, our strategy will be as follows. We will sum over the indices, removing the corresponding vertices from $H$. As we do this, we will apply appropriate bounds on squared tensor entries, removing the corresponding doubled hyperedge from $H$. To obtain these bounds, we observe that we can bound the average square of our tensor entries in terms of the number of indices we are averaging over.

We say that an order 3 tensor $A$ of dimensions $n_{1}\times n_{2}\times n_{3}$ is $(B,r,\mu)$-bounded if the following bounds are true

$\max_{a,b,c}{\{A^{2}_{abc}\}}\leqslant Br$

$\max{\{\max_{b,c}{\{\frac{1}{n_{1}}\sum_{a}{A^{2}_{abc}}\}},\max_{a,c}{\{\frac{1}{n_{2}}\sum_{b}{A^{2}_{abc}}\}},\max_{a,b}{\{\frac{1}{n_{3}}\sum_{c}{A^{2}_{abc}}\}}\}}\leqslant\frac{B}{\mu}$

$\max{\{\max_{c}{\{\frac{1}{{n_{1}}{n_{2}}}\sum_{a,b}{A^{2}_{abc}}\}},\max_{b}{\{\frac{1}{{n_{1}}{n_{3}}}\sum_{a,c}{A^{2}_{abc}}\}},\max_{a}{\{\frac{1}{{n_{2}}{n_{3}}}\sum_{b,c}{A^{2}_{abc}}\}}\}}\leqslant\frac{B}{\mu^{2}}$

$\frac{1}{{n_{1}}{n_{2}}{n_{3}}}\sum_{a,b,c}{A^{2}_{abc}}\leqslant\frac{B}{\mu^{3}}$

More generally, we say that a tensor $A$ is $(B,r,\mu)$-bounded if the following is true

The maximum value of an entry of $A$ squared is at most $Br$

Every index which we average over decreases our upper bound by a factor of $\mu$

If we are averaging over at least one index then we can delete the factor of $r$ in our bound.

Since $r$ and $\mu$ will always be the same, we write $B$-bounded rather than $(B,r,\mu)$-bounded

To give a sense of why these are the correct type of bounds to use, we now show that $X$ is $\left(\frac{r\mu^{3}}{{n_{1}}{n_{2}}{n_{3}}}\right)$-bounded. In Section 7, we will use an iterative argument to show that with high probability, similar bounds hold for all of the tensors $A$ we will be considering.

$X$ is $\left(\frac{r\mu^{3}}{{n_{1}}{n_{2}}{n_{3}}}\right)$-bounded

Recall that $X=\sum_{i=1}^{r}{u_{i}\otimes v_{i}\otimes w_{i}}$ where the vectors $\{u_{i}\}$ are orthonormal, the vectors $\{v_{i}\}$ are orthonormal, and the vectors $\{w_{i}\}$ are orthonormal. Also recall that for all $i,a,b,c$, $u^{2}_{ia}\leqslant\frac{\mu}{n_{1}}$, $v^{2}_{ib}\leqslant\frac{\mu}{n_{2}}$, and $w^{2}_{ic}\leqslant\frac{\mu}{n_{3}}$. We now have the following bounds:

The other bounds where we sum over one index follow by symmetrical arguments.

The other bounds where we sum over two indices follow by symmetrical arguments.

With these kinds of bounds in mind, we bound sums of products of tensor entries as follows. We note that we can always apply the entrywise bound for a squared tensor entry. However, to apply any of the other bounds, we must be able to sum over an index or indices where the only term in our product which depends on this index or indices is the squared tensor entry. This can be described in terms of the hypergraph $H$ as follows.

Given a hyperedge $e$ in $H$, define $b(e)$ to the the minimal $B$ such that the tensor entry corresponding to $e$ is $B$-bounded.

We say that a vertex is free in $H$ if it contained in only one hyperedge and this hyperedge appears with multiplicity two.

We can apply our bounds in the following ways.

We can always choose a hyperedge $e$ of $H$, use the entrywise bound of $rb(e)$ on the corresponding squared tensor entry (note the extra factor of $r$), and reduce the multiplicity of $e$ by two.

If there is a free vertex incident with a doubled hyperedge $e$ in $H$, we can sum over all free vertices which are incident with $e$ using the corresponding bound then delete these vertices and the doubled hyperedge $e$ from $H$. When we do this, we obtain a factor of

The factors of $n_{1},n_{2},n_{3}$ appear because we are summing over these indices and the factors of $\frac{1}{\mu}$ appear because each index we sum over reduces the bound on the average value by a factor of $\mu$.

If we apply these bounds repeatedly until there are no tensor entries/hyperedges left to bound, our final bound on a single sum of products of tensor entries will be

To prove our final upper bound, we will argue that we can always apply these bounds in such a way that the number of times we need to use an entrywise bound is sufficiently small.

4 Counting intersection patterns

There will be one more factor in our final bound. This factor will come from the number of possible intersection patterns with a given number $z$ of distinct triples $(a,b,c)$.

The total number of intersection patterns on $2q^{\prime}$ triples with $z$ distinct triples $(a,b,c)$ such that every triple $(a,b,c)$ has multiplicity at least two is at most ${\binom{2q^{\prime}}{z}}z^{2q^{\prime}-z}\leqslant 2^{2q^{\prime}}{q^{\prime}}^{2q^{\prime}-z}$

To determine which triples $(a,b,c)$ are equal to each other, it is sufficient to decide which triples are distinct from all previous triples (there are ${\binom{2q^{\prime}}{z}}$ choices for this) and for the remaining $2q^{\prime}-z$ triples, which of the $z$ distinct triples they are equal to (there are $z^{2q^{\prime}-z}$ choices for this). ∎

In this section, we implement the techniques described in Section 5 to probabilistically bound $||\bar{R}_{\Omega}A\otimes(\bar{R}_{\Omega}A)^{T}||$. In particular, we prove the following theorem.

If $A$ is $B$-bounded, $C\geqslant 1$, and

$m>10000C(2+\beta)^{2}{n_{max}}r\mu^{2}\ln{n_{max}}$

$m>10000C(2+\beta)^{2}{r}\sqrt{n_{1}}\max{\{n_{2},n_{3}\}}\mu^{\frac{3}{2}}\ln{n_{max}}\geqslant 10000C(2+\beta)^{2}{r}\sqrt{{n_{1}}{n_{2}}{n_{3}}}\mu^{\frac{3}{2}}\ln{n_{max}}$

${\mu}r\leqslant\min{\{n_{1},n_{2},n_{3}\}}$

then defining $Y=\bar{R}_{\Omega}A\otimes(\bar{R}_{\Omega}A)^{T}$,

$m>10000C(2+\beta)^{2}{n_{max}}r\mu^{2}\ln{n_{max}}$

$m>10000C(2+\beta)^{2}{r}\sqrt{n_{1}}\max{\{n_{2},n_{3}\}}\mu^{\frac{3}{2}}\ln{n_{max}}\geqslant 10000C(2+\beta)^{2}{r}\sqrt{{n_{1}}{n_{2}}{n_{3}}}\mu^{\frac{3}{2}}\ln{n_{max}}$

${\mu}r\leqslant\min{\{n_{1},n_{2},n_{3}\}}$

This follows immediately from Theorem 6.1 and the fact that $X$ is $\left(\frac{r\mu^{3}}{{n_{1}}{n_{2}}{n_{3}}}\right)$-bounded. ∎

To prove Theorem 6.1, we break up $Y$ into four parts and then prove probabilistic norm bounds for each part.

Define $(Y_{1})_{bcb^{\prime}c^{\prime}}=Y_{bcb^{\prime}c^{\prime}}$ if $b=b^{\prime}$, $c=c^{\prime}$ and otherwise.

Define $(Y_{2})_{bcb^{\prime}c^{\prime}}=Y_{bcb^{\prime}c^{\prime}}$ if $b=b^{\prime}$, $c\neq c^{\prime}$ and otherwise.

Define $(Y_{3})_{bcb^{\prime}c^{\prime}}=Y_{bcb^{\prime}c^{\prime}}$ if $b\neq b^{\prime}$, $c=c^{\prime}$ and otherwise.

Define $(Y_{4})_{bcb^{\prime}c^{\prime}}=Y_{bcb^{\prime}c^{\prime}}$ if $b\neq b^{\prime}$, $c\neq c^{\prime}$ and otherwise.

We have that $Y_{bcb^{\prime}c^{\prime}}=\sum_{a}{\bar{R}_{\Omega}(a,b,c^{\prime})\bar{R}_{\Omega}(a,b^{\prime},c)A_{abc^{\prime}}A_{ab^{\prime}c}}$. To see the structure of $({Y_{j}}Y_{j}^{T})^{q}$, we now compute ${Y_{j}}Y_{j}^{T}$.